Máquinas de Turing: Uma máquina pode escrever para um número finito de células de memória, mas não parou?

Question

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!

Answer 1

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.