Mortalidad (teoría de la computabilidad)

En la teoría de la computabilidad , el problema de la mortalidad es un problema de decisión relacionado con el problema de la detención . En el caso de las máquinas de Turing , el problema de la detención puede enunciarse de la siguiente manera: dada una máquina de Turing y una palabra, se decide si la máquina se detiene cuando se ejecuta con la palabra dada.

Por el contrario, el problema de mortalidad de las máquinas de Turing pregunta si todas las ejecuciones de la máquina, a partir de cualquier configuración , se detienen.

En la declaración anterior, una configuración especifica tanto el estado de la máquina (no necesariamente su estado inicial), su posición en la cinta y el contenido de la cinta. Si bien generalmente asumimos que en la configuración inicial todas las celdas de la cinta, salvo un número finito, están en blanco, en el problema de la mortalidad la cinta puede tener contenido arbitrario, incluidos infinitos símbolos que no están en blanco escritos en ella.

Philip K. Hooper demostró en 1966 ^[1] que el problema de la mortalidad es indecidible . Esto es cierto tanto para una máquina con una cinta infinita en ambas direcciones como para una máquina con una cinta semi-infinita. Obsérvese que este resultado no se sigue directamente del conocido problema de la función total (¿Se detiene una máquina dada para cada entrada?), ya que este último problema solo concierne a cálculos válidos (que comienzan con una configuración inicial).

La variante en la que sólo se consideran configuraciones finitas también es indecidible, como demuestra Herman ^[2], que la llama "el problema de la detención uniforme". Demuestra que el problema no sólo es indecidible, sino también -completo . ${\displaystyle \Pi _{2}^{0}}$

Modelos adicionales

Naturalmente, el problema puede reformularse para cualquier modelo computacional en el que existan nociones de "configuración" y "transición". Un miembro del modelo será mortal si no existe una configuración que conduzca a una cadena infinita de transiciones. Se ha demostrado que el problema de la mortalidad es indecidible para:

• Sistemas Semi-Thue y algoritmos de Markov . ^[1]
• Máquinas contadoras ^[3]
• Sistemas dinámicos sobre o o , para , donde la función de transición es lineal por partes ^{[4] [5]} (aquí, se selecciona un punto arbitrario, por ejemplo, el origen, como estado de detención). ${\displaystyle {\mathbb {R} }^{n}}$ ${\displaystyle {\mathbb {Q} }^{n}}$ ${\displaystyle {\mathbb {Z} }^{n}}$ ${\displaystyle n\geq 2}$

Referencias

1. Hooper, P. "La indecidibilidad del problema de la inmortalidad de la máquina de Turing". Journal of Symbolic Logic . 31 (2): 219–234. doi :10.2307/2269811.
2. Herman, Gabor. "Una solución simple del problema de detención uniforme". Journal of Symbolic Logic . 34 (4): 639–640. doi :10.2307/2270856.
3. Kurtz, Stuart A.; Simon, Janos (2007). "La indecidibilidad del problema generalizado de Collatz". Conferencia internacional sobre teoría y aplicaciones de modelos de computación, TAMC 2007. doi : 10.1007/978-3-540-72504-6_49.
4. Blondel, Vincent D.; Bournez, Olivier; Koiran, Pascal; Papadimitriou, Christos H.; Tsitsiklis, John N. (28 de marzo de 2001). "Decidir la estabilidad y la mortalidad de sistemas dinámicos afines por partes" (PDF) . Ciencias de la Computación Teórica . 255 (1): 687–696. doi : 10.1016/S0304-3975(00)00399-6 . ISSN  0304-3975.
5. Ben-Amram, Amir M. (1 de enero de 2015). "Mortalidad de funciones afines iteradas por partes sobre los números enteros: decidibilidad y complejidad" . Computability . 4 (1): 19–56. doi :10.3233/COM-150032. ISSN  2211-3568.