Problema de la parada

El problema de la parada o problema de la detenció per a màquines de Turing consistix en lo següent: donada una Màquina de Turing $M$ i una paraula $w$, determinar si $M$ terminarà en un número finito de passos quan és eixecutada usant $w$ com a senya d'entrada. Alan Turing, en el seu famós artícul On Computable Numbers, with an Application to the Entscheidungsproblem (1936), va demostrar que el problema de la parada de la Màquina de Turing és indecidible (no computable o no recursivo), en el sentit de que cap màquina de Turing lo pot resoldre.

Rellevància en la pràctica

En eixecutar un conjunt de programes, est pot terminar despuix d'un número finito de passos o pot no terminar mai. En la pràctica, este últim cas es manifesta com a programes que es queden «travats» o que entren a un bucle infinit. Per esta raó seria de gran utilitat resoldre la següent pregunta en la pràctica:

Conéixer si existix el programa P és, en térmens resumits, el problema de la parada.

No obstant cal fer notar que el saber popular sobre este problema fa pensar que mai és possible demostrar que un programa termina. Açò és fals.

Lo que s'afirma és que no existix una manera automàtica computable de saber si tots els programes possibles terminen. No es nega que existixca la prova per a programes concrets. De fet, la construcció de proves per a programes concrets és un pas obligatori per a demostrar el seu correctitud.

El procediment per a construir estes proves no és automàtic; no obstant, existixen heurístiques que faciliten trobar les proves dels programes. L'àrea de coneiximent que estudia la construcció sistemàtica de proves es denomina Anàlisis de Terminació.

L'evaluació o eixecució del programa en les entrades no obstant no constituïx una prova de que sempre termine, sino de que en les circumstàncies de l'eixecució, va terminar.

Irresolubilidad del problema

La irresolubilidad del problema es pot mostrar de vàries formes, pero en essència totes equivalen a un argument diagonal de Cantor. A continuació es mostra l'argument en térmens moderns de programació:

Supongam que este problema sí es pot resoldre algoritmicamente; llavors hi ha un programa, que cridarem Termina, que cada volta que se li suministra el còdic d'un programa p i les seues senyes d'entrada x, fa un número finito d'operacions i respon «True» quan el programa termina o «False» quan el programa mai termina. En llenguage Python:

def Termina(p, x):
    Supongam que ací es troba un còdic maravellós que soluciona el problema de la parada
    Esta funció retorna True si p(x) termina o False en un atre cas

Baixe la suposició de que existix este programa, es pot usar com subrutina d'un atre programa més gran, al que cridarem «Diagonal» (en referència a la diagonal de Cantor). Este programa rebrà com a senya d'entrada el còdic d'un programa qualsevol w, i usarà el programa Termina per a decidir si el programa w termina quan se li suministra ella mateixa com a entrada (no hi ha res de rar en açò, puix en la pràctica hi ha programes com els compiladorés que poden suministrar-se a sí mateixos com a senya d'entrada). A continuació, Diagonal fa lo opost: Si w termina llavors Diagonal entra en un cicle infinit i si w entra en un cicle infinit llavors Diagonal termina. En llenguage Python:

def Diagonal(w):
    if Termina(w, w):
        while True: pass Esta instrucció és un bucle infinit

Resumint, el programa Diagonal està dissenyat per a tindre la següent propietat (entenga's la flecha com «sempre i quan»):

$𝐷𝑖𝑎𝑔𝑜𝑛𝑎𝑙\mathit{(}𝑤\mathit{)}\text{ termina}⟺𝑤\mathit{(}𝑤\mathit{)}\text{ nunca termina}$

Com a w pot ser el còdic de qualsevol programa, particularment pot ser el del mateix Diagonal:

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

En este cas es té $w=Diagonal$, i per lo tant

$𝐷𝑖𝑎𝑔𝑜𝑛𝑎𝑙\mathit{(}𝐷𝑖𝑎𝑔𝑜𝑛𝑎𝑙\mathit{)}\text{ termina}⟺𝐷𝑖𝑎𝑔𝑜𝑛𝑎𝑙\mathit{(}𝐷𝑖𝑎𝑔𝑜𝑛𝑎𝑙\mathit{)}\text{ nunca termina}$

És dir que baixe la suposició de que existix l'algoritme Termina s'aplega a la paradòxica conclusió de que hi ha una instrucció que termina sempre i quan no termine. Com esta conclusió és absurda, llavors no pot existir l'algoritme Termina; és dir que és impossible resoldre el problema de la parada algorítmicament.

Vore també

• Constant de Chaitin