Máquinas de Turing: Uma máquina pode escrever para um número finito de células de memória, mas não parou?
-
29-09-2020 - |
Pergunta
Eu estou tentando reduzir o problema da parada para mostrar outro problema é indecável.O problema envolve um programa que é verdadeiro se uma máquina $ m $ escreve para uma quantidade arbitrária de memória e false se ele escreve para uma quantidade finita de células de memória.Agora estou pensando, está escrevendo para uma quantidade finita de células de memória equivalentes a interromper, ou pode haver casos em que uma máquina escreve para uma quantidade finita de células de memória sem interromper?
Obrigado antecipadamente!
Solução
Considere uma máquina de Turing que move repetidamente a cabeça direita, depois para a esquerda, depois para a direita, depois para a esquerda e assim por diante.
Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange