13.3: El problema de la detención

Template:MathJaxZach

Supongamos que hemos arreglado algunas descripciones finitas de máquinas Turing. Usando estos, podemos enumerar las máquinas Turing a través de sus descripciones, digamos, ordenadas por el orden lexicográfico. Cada máquina Turing recibe así un índice: su lugar en la enumeración\(M_1\),,\(M_2\)\(M_3\),... de descripciones de máquinas Turing.

Sabemos que debe haber funciones no computables de Turing: el conjunto de descripciones de máquinas Turing, y por lo tanto, el conjunto de máquinas Turing, es enumerable, pero el conjunto de todas las funciones de\(\Nat\) a no lo\(\Nat\) es. Pero también podemos encontrar ejemplos específicos de función no computable. Una de esas funciones es la función de detención.

Definición\(\PageIndex{1}\): Halting function

La función de detención\(h\) se define como\[h(e,n) = \begin{cases} \text{0} & \text{if machine $M_e$ does not halt for input $n$} \\ \text{1} & \text{if machine $M_e$ halts for input $n$} \end{cases}\nonumber\]

Definición\(\PageIndex{2}\): Halting problem

El problema de la detención es el problema de determinar (para cualquier\(e\),\(n\)) si la máquina Turing\(M_e\) se detiene por una entrada de\(n\) golpes.

Mostramos que no\(h\) es Turing-computable al mostrar que una función relacionada,\(s\), no es Turing-computable. Esta prueba se basa en el hecho de que cualquier cosa que pueda ser calculada por una máquina Turing se puede calcular usando solo dos símbolos:\(\TMblank\) y\(\TMstroke\), y el hecho de que dos máquinas Turing se pueden enganchar juntas para crear una sola máquina.

Definición\(\PageIndex{3}\)

La función\(s\) se define como\[s(e) = \begin{cases} \text{0} & \text{if machine $M_e$ does not halt for input $e$} \\ \text{1} & \text{if machine $M_e$ halts for input $e$} \end{cases}\nonumber\]

Lema\(\PageIndex{1}\)

La función no\(s\) es Turing computable.

Comprobante. Suponemos, por contradicción, que la función\(s\) es Turing computable. Entonces habría una máquina de Turing\(S\) que computa\(s\). Podemos suponer, sin pérdida de generalidad, que cuando se\(S\) detiene, lo hace mientras escanea el primer cuadrado. Esta máquina se puede “conectar” a otra máquina\(J\), que se detiene si se inicia en una cinta en blanco (es decir, si lee\(\TMblank\) en el estado inicial mientras escanea el cuadrado a la derecha del símbolo de fin de cinta), y de lo contrario se desvía hacia la derecha, sin parar nunca. \(S \concat J\), la máquina creada enganchando\(S\) a\(J\), es una máquina de Turing, por lo que es\(M_e\) para algunos\(e\) (es decir, aparece en algún lugar de la enumeración). Empezar\(M_e\) con una entrada de\(e\)\(\TMstroke\) s. hay dos posibilidades: o\(M_e\) se detiene o no se detiene.

1. Supongamos que\(M_e\) se detiene por una entrada de\(e\)\(\TMstroke\) s. entonces\(s(e) = 1\). Entonces\(S\), cuando se inicia\(e\), se detiene con un solo\(\TMstroke\) como salida en la cinta. Después\(J\) comienza con una\(\TMstroke\) en la cinta. En ese caso\(J\) no se detiene. Pero\(M_e\) es la máquina\(S \concat J\), por lo que debería hacer exactamente lo que\(S\)\(J\) seguiría haría. Entonces\(M_e\) no se puede detener por una entrada de\(e\)\(\TMstroke\)'s.

2. Ahora supongamos que\(M_e\) no se detiene por una entrada de\(e\)\(\TMstroke\) s. entonces\(s(e) = 0\), y\(S\), cuando se inicia en la entrada\(e\), se detiene con una cinta en blanco. \(J\), cuando se inicia con una cinta en blanco, se detiene inmediatamente. Nuevamente,\(M_e\) hace lo que\(S\)\(J\) seguiría haría, así que\(M_e\) hay que parar para una entrada de\(e\)\(\TMstroke\)'s.

Esto demuestra que no puede haber una máquina Turing\(S\): no\(s\) es Turing computable. ◻

Teorema\(\PageIndex{1}\): Unsolvability of the Halting Problem

El problema de la detención es irresoluble, es decir, la función no\(h\) es Turing computable.

Comprobante. Supongamos que Turing\(h\) era computable, digamos, por una máquina de Turing\(H\). Podríamos usar\(H\) para construir una máquina Turing que compute\(s\): Primero, hacer una copia de la entrada (separada por un espacio en blanco). Después, regresa al principio, y corre\(H\). Claramente podemos hacer una máquina que haga lo primero, y si\(H\) existiera, podríamos “conectarla” a una máquina duplicadora modificada para obtener una nueva máquina que determinaría si se\(M_e\) detiene en la entrada\(e\), es decir, calcula \(s\). Pero ya hemos demostrado que tal máquina no puede existir. De ahí\(h\) que tampoco sea Turing computable. ◻

Problema\(\PageIndex{1}\)

El problema de Three Halting (3-Halt) es el problema de dar un procedimiento de decisión para determinar si una Máquina Turing elegida arbitrariamente se detiene o no para una entrada de tres golpes en una cinta que de otro modo estaría en blanco. Demuestre que el problema de 3-Halt es irresoluble.

Problema\(\PageIndex{2}\)

Demostrar que si el problema de detención es solucionable para la máquina Turing\(M_e\) y los pares de entrada y\(n\) dónde\(e \neq n\), entonces también es solucionable para los casos donde\(e = n\).

Problema\(\PageIndex{3}\)

Demostramos que el problema de detención es irresoluble si la entrada es un número\(e\), que identifica una máquina Turing\(M_e\) a través de una enumaración de todas las máquinas Turing. ¿Y si permitimos la descripción de las máquinas Turing de la sección 13.2 directamente como entrada? (Esto requeriría un alfabeto más grande, por supuesto). ¿Puede haber una máquina Turing que decida el problema de la detención pero tome como entrada descripciones de máquinas Turing en lugar de índices? Explique por qué o por qué no.