Máquinas de Turing: ¿Puede una máquina escribir a un número finito de celdas de memoria, pero no detenerse?
-
29-09-2020 - |
Pregunta
Estoy tratando de reducir el problema detenerlo para mostrar que otro problema es indecidible.El problema implica un programa que es cierto si una máquina $ m $ escribe a una cantidad arbitraria de memoria, y falso si escribe a una cantidad finita de celdas de memoria.Ahora estoy pensando, ¿está escribiendo a una cantidad finita de células de memoria equivalente a detenerse, o puede haber casos en los que una máquina escriba a una cantidad finita de células de memoria sin detenerse?
¡Gracias de antemano!
Solución
Considere una máquina de Turing que mueve repetidamente su cabeza derecha, luego se fue, luego a la derecha, luego se fue, y así sucesivamente.
Licenciado bajo: CC-BY-SA con atribución
No afiliado a cs.stackexchange