Problema da parada

Exemplo de máquina de Turing mediante un diagrama de estados.

O problema da parada ou problema da detención para máquinas de Turing foi formulado polo célebre matemático e informático Alan Turing no ano 1935. No seu artigo On Computable Numbers, with an Application to the Entscheidungsproblem (1936), Turing demostrou que o problema era indecidible (non computable ou non recursivo), no sentido de que ningunha máquina de Turing podía resolvelo.

Formulación

Sexa $w_{M}$ unha cadena que describe a máquina de Turing $M$, e $w$ unha cadea sobre o propio alfabeto de $M$. Unha posible solución ao problema da parada sería unha máquina de Turing $H$ que, para calesquera $w_{M}$ e $w$:

• $q_{0}w_{m}w\vdash *x_{1}q_{n}x_{2}$ se $M$ aplicada a $w$ provoca parada.
• $q_{0}w_{m}w\vdash *x_{1}q_{m}x_{2}$ se $M$ aplicada a $w$ non provoca parada.

sendo $q_{n}$,$q_{m}$ estados finais da máquina $H$.

Como non existe máquina de Turing $H$ cun comportamento tal, o problema considérase indecidible.

Ao executar un programa de computación, este pode terminar despois dun número finito de pasos ou non terminar nunca (programas «trabados» ou de bucle infinito, un erro común en programación). Por esta razón, sería de gran utilidade resolver unha pregunta como a que segue na práctica:

Existe un programa P tal que, dado un programa calquera q e uns datos de entrada x, mostre como saída 1 se q con entrada x termina nun número finito de pasos ou 0 se q con x entra nun bucle infinito.

Coñecer se existe dito programa $P$ é, en resumo, o problema da detención que Alan Turing demostrou indecidible.

A primeira conclusión é que non existe unha forma automática computable de saber se todos os programas terminan. A proba pode existir para programas concretos, un paso que, en programación, adoita ser obrigatorio para o correcto funcionamento do código. De feito, o área de Análise de Terminación dos programas de computadora ocúpase de estudar a través de procedementos heurísticos a avaliación de código a través de probas e ferramentas de validación.

Irresolubilidade do problema

O argumento diagonal de Cantor establece que o conxunto dos números reais non é numerable. Dita demostración basta para demostrar que o problema da parada non ten solución.

Se o problema puidese resolverse algoritmicamente; existiría un programa, Termina, que cada vez que recibira o código dun programa p e os seus datos de entrada x, faría un número finito de operacións e respondería «True» ao terminar e «False» se o programa xamais terminase. En linguaxe Python:

def Termina(p, x):
    #Suposto código que resolvería o problema da parada.
    #DEVOLVE True se p(x) termina e False noutro caso.

Baixo a suposición de que existe dito programa, pódese usar como subrutina doutro programa máis grande, Diagonal, que recibiría como dato de entrada o código dun programa calquera w e empregaría o programa Termina para decidir se o programa w termina cando se recibe a si mesmo como entrada. A idea é análoga a programas como os compiladores informáticos que poden recibirse a si mesmos como dato de entrada ou input. Diagonal faría o oposto: se w termina entón Diagonal entra nun ciclo infinito e se w entra nun ciclo infinito entón Diagonal termina. En Python:

def Diagonal(w):
    if Termina(w, w):
        while True: pass #Instrución que simula un bucle infinito

O deseño do programa Diagonal cumpriría a propiedade seguinte:

${\it {{Diagonal}(w){\text{ termina}}\iff w(w){\text{ nunca termina}}}}$

Como w pode ser o código dun programa calquera, particularmente pode ser o do mesmo Diagonal:

def Diagonal(Diagonal):
     if Termina(Diagonal, Diagonal):
         while True: pass

Neste caso tense $w=Diagonal$, e por tanto

${\it {{Diagonal}({\it {{Diagonal}){\text{ termina}}\iff {\it {{Diagonal}({\it {{Diagonal}){\text{ nunca termina}}}}}}}}}}$

A suposición de existencia do algoritmo Termina conduce ao paradoxo de que hai unha instrución que termina coa condición de que non termine. O absurdo impide a existencia do algoritmo Termina; é dicir que é imposible resolver o problema da parada algorítmicamente.

Demostración por construción de máquinas de Turing

Supóñase que o problema da parada ten solución, é dicir:

Existe unha máquina de Turing que é capaz de determinar se outra máquina de Turing parará (terminará) cunha entrada determinada. [Suposto]

Sexa Termina dita máquina (análoga á máquina de Turing $H$).

• Entrada: cadea $w$ e $M$ (ou $w_{M}$) que describe a codificación dunha máquina de Turing $M$.
• Terminación: Termina finalizará en estado de aceptación se para ante as entrada $w$ e $M$, e de non ser así deterase nun estado de rexeitamento.

• Unha nova máquina Copia pode recibir unha cadea aleatoria e repetila, de forma que termine nun estado de aceptación con $w,w$ (repetición da cadea de entrada).

• Unha nova máquina Diagonal recibe de entrada unha cadea, presumiblemente a codificación dunha máquina de Turing $M$.

A execución seguiría o seguinte fluxo:

1. Diagonal emprega a máquina Copia para replicar a cadea $w$, transformándoa en $w,w$.
2. Diagonal traslada o output a Termina para decidir se a máquina para, en nese caso realiza todo o contrario; é dicir, se Termina acepta (fluxo terminado) Diagonal entra en bucle infinito (un só estado que se repite), e ese Termina rechaza entón Diagonal termina en estado de aceptación.

A máquina Diagonal está deseñada para cumprir a propiedade:

Diagonal para ante a entrada $w$ $\iff$ máquina codificada en $w$ non para ante a entrada $w$.

1. Aplícase a codificación da máquina Diagonal á propia máquina Diagonal ($w$ como codificación de Diagonal).
2. Séguese que Diagonal para ante si mesma como entrada se e só se Diagonal non para ante si mesma como entrada $w$.
3. Paradoxo con anteriormente descrito.

Todas as máquinas descritas poden ser construídas coa excepción de Termina. Por redución ao absurdo, a suposta existencia de Termina demóstrase imposible e, por tanto, o problema da parada indecidible (sen solución por parte de ningunha máquina de Turing).

Véxase tamén

Bibliografía

• Sipser, Michael (2005). Introduction to the Theory of Computation (2 ed.). Course Technology. ISBN 978-0534950972. 
• Kelley, Dean (1995). Teoría de Autómatas y Lenguajes Formales. Prentice Hall. ISBN 0-13-497777-7. 
• George S. Boolos, John P. Burgess & Richard C. Jeffrey (2007). Computability and Logic. Cambridge University Press. ISBN 978-0521701464. 
• Linz, P (2001). An Introduction to Formal Languages and Automata. Jones and Bartlett Publishers, Inc. 
• Hopcroft, J.E (2022). Introducción a la Teoría de Autómatas, Lenguajes y Computación. Addison Wesley. 

Outros artigos

• Máquina de Turing