Decidir se uma máquina de Turing fez um movimento para a esquerda
Ao escrever uma decisão para uma máquina para ver se ela fez um movimento para a esquerda ou não em uma entrada de w , diz-se que, se continuarmos o cálculo para| w | +N+ 1|W|+N+1 1 (NN : número de estados) número de etapas, podemos tomar uma decisão para essa decisão.
Não entendi porque |w | + N+ 1|W|+N+1 1número de etapas. Alguém poderia explicar isso com mais detalhes?
| w ||W| são necessárias etapas para verificar a entrada, se uma movimentação para a esquerda for feita durante essa verificação.
Caso contrário, no final da entrada, a cabeça da máquina de Turing fica na parte em branco da fita (acima do primeiro símbolo em branco após a entrada). Suponha que o estado sejaqEu1 1qEu1 1. Se a máquina de Turing não der um passo à esquerda e permanecer no estadoqEu1 1qEu1 1, ele fará isso para sempre (continuará se movendo na infinita fita em branco no estado qEu1 1qEu1 1) Mas pode se mover para a direita e mudar para o estadoqEu2,Eu1 1≠Eu2qEu2,Eu1 1≠Eu2.
Se você continuar com esse raciocínio, verá que existem apenas duas possibilidades:
ele se move para a esquerda ou
entra em um estado qEuk + jqEuk+j pela segunda vez e, assim, ele fará um loop para sempre: qEuk→qEuk + 1→ . . . →qEuk + j=qEuk→qEuk + 1→ . . .qEuk→qEuk+1 1→...→qEuk+j=qEuk→qEuk+1 1→...
Mas existem apenas NN estados diferentes, para no máximo N+ 1N+1 1 são necessárias mais etapas para detectar esse loop.
Eu acho que isso só funciona com esse número de etapas, se a máquina não puder fazer um movimento "neutro" (por exemplo, ficar) também. Caso contrário, são necessárias mais algumas etapas (dependendo do alfabeto da fitaΓΓ)
— Frafl 09/04
@rafrafl: você está certo (mas a definição padrão da máquina de Turing não inclui a "estadia", mas apenas L / R). No entanto - neste momento - fazer um decisor para esse tipo de TM pode ser um bom exercício para o OP :-)
Obrigado pela sua resposta, mas deixe-me perguntar também: 1) É sempre verdade que a máquina escaneia a entrada até o fim antes de fazer qualquer coisa (quero dizer, não há possibilidade de que a máquina vire à esquerda antes chegando ao final da entrada)? 2) Esse foi o número máximo de etapas para testar, como a máquina pode detectar o movimento esquerdo em cada etapa?
— Msn #
@mahdisaeedi: 1) não, ele pode fazer um movimento para a esquerda durante a varredura de entrada; mas se fizer um movimento para a esquerda, seu decisor para de simulá-lo e pára em SIM. 2) o decisor deve simular a máquina de Turing alvo na entradaWWpasso a passo; mas como escrevi na resposta, é suficiente simulá-lo para| w | + N+ 1|W|+N+1 1passos