Problema de la parada

En teoria de la computabilitat el problema de la parada és un problema de decisió que es pot formular de forma informal:

donada una descripció d'un programa i el seu estat inicial, determinar si el programa, quan executa aquesta entrada, s'atura (completa). L'alternativa és que funciona per sempre sense aturar-se

Alan Turing va provar el 1936 que un algorisme general per resoldre el problema de la parada per totes les possibles parelles programa-entrades no pot existir. Es diu que el problema de la parada és indecidible amb màquines de Turing.

Descripció formal

Una forma possible de definició formal del problema de la parada és el següent:

Donat un nombre de Gödel $\varphi$ de funcions computables,

amb $\langle i,x\rangle$ les Funcions de còpia de Cantor,

el conjunt $K_{\varphi }^{0}:=\{\langle i,x\rangle |\varphi _{i}(x)\ \mathrm {existeix} \}$ i s'anomena "el conjunt d'aturada".

El problema de decidir si el conjunt d'aturada és recursiu o no s'anomena el problema de l'aturada. Encara que el conjunt és recursivament enumerable, el problema de la parada no es pot resoldre per funcions computables.

Són possibles altres formulacions equivalents, per exemple usant màquina de Turing.

Importància i conseqüències

La importància històrica del problema de la parada recau en el fet que va ser un dels primers problemes a provar-se que eren indecidibles (La demostració de Turing es publicà el maig del 1936, i la demostració de Church de la indecidibilitat d'un problema en el càlcul lambda s'havia publicat l'abril del 1936). Més endavant, molts altres problemes s'han descrit; el mètode habitual per provar que un problema és indecidible és mitjançant la tècnica de la reducció. Per fer-ho, es demostra que si es trobés una solució al nou problema, es podria fer servir per decidir un problema indecidible (transformant-lo en instàncies del nou problema). Com que se sap que no existeix un mètode per decidir l'antic problema, tampoc cap mètode pot decidir el nou problema.

Una conseqüència de la indecidibilitat del problema de la parada és que no pot existir un algorisme general que decideixi si una afirmació sobre nombres naturals és certa o no. La raó és que la proposició que afirma que un cert algorisme acabarà donat una certa entrada es pot convertir en una afirmació equivalent sobre nombres naturals. Si es tingués un algorisme que pogués resoldre qualsevol afirmació sobre els nombres naturals, podria resoldre aquest en particular; però això determinaria si el problema original s'atura, el que és impossible, ja que el problema de la parada és indecidible.

Una altra conseqüència de la indecidibilitat del problema de la parada és el teorema de Rice que diu que la veritat de qualsevol afirmació no trivial sobre la funció que és definida per un algorisme és indecidible. Per exemple, el problema de decisió "aquest algorisme pararà per l'entrada 0" és indecidible. Noteu que aquest teorema parla sobre la funció definida per l'algorisme i no per l'algorisme mateix. És possible, per exemple, decidir si un algorisme acabarà en 100 passos, però aquesta no és l'afirmació sobre la funció que és definida per l'algorisme.

Gregory Chaitin ha definit una probabilitat d'aturada, un tipus de nombre real que informalment es diu que representa la probabilitat que un programa aleatori s'aturi. Aquests nombres tenen el mateix Grau de Turing que el problema de la parada.

Mentre que la demostració de Turing afirma que no pot existir un mètode general o algorisme per determinar si un algorisme s'atura, instàncies individuals d'aquest problema poden ser susceptibles d'atacar. Donat un algorisme específic, sovint es pot veure fàcilment que s'aturarà per qualsevol entrada, i sovint se'n dona una demostració parcial. Però cadascuna d'aquestes demostracions necessita nous arguments: no existeix un mètode mecànic general per determinar si un algorisme en una màquina de Turing acaba. Tot i això, hi ha algunes heurístiques que es poden usar de forma automàtica per intentar construir una demostració, cosa que succeeix sovint en programes típics.

Hi ha un altre punt a tenir en compte. La indecibilitat del problema de la parada recau en el fet que els algorismes poden tenir emmagatzemament infinit: en qualsevol moment, només es poden guardar un nombre finit d'objectes, però sempre se'n poden guardar més i mai s'esgota la memòria. Però els computadors actuals no són equivalents a una màquina de Turing, en canvi són autòmats lineals limitats, ja que la seva memòria i emmagatzemament extern són limitats. El problema de la parada per programes executant-se en aquestes màquines es pot resoldre amb un algorisme general força simple. Es tracta d'executar el programa, i veure si sobrepassa la capacitat de la memòria de la màquina.

Esbós de demostració

La demostració es fa per reducció a l'absurd. Es comença per triar un llenguatge de programació, de manera que s'associa cada programa amb almenys una cadena de caràcters. Llavors se suposa que algú presenta un programa para(p, i) que retorna cert si p descriu un programa que s'atura que se li passa com a entrada la cadena i, i retorna fals altrament. Es pot construir un altre programa problema que fa servir para com a subrutina:

funció problema(cadena s)
si para(s, s)
funciona per sempre
si no
retorna cert

Aquest programa pren una cadena s com a argument i executa el programa para, passant-li s tant com descripció de programa i com a dades d'entrada pel programa. Si para retorna cert, llavors problema es queda executant-se per sempre; si no, problema retorna cert. Com que tots els programes es poden representar mitjançant cadenes de caràcters, existeix una cadena t que representa el programa problema. problema(t) s'aturarà? Considerant els dos casos:

1. Si problema(t) s'atura, ha de ser perquè para(t,t) ha retornat fals, però això voldria dir que problema(t) no s'hauria d'haver aturat.
2. Si problema(t) no s'atura mai, és perquè o bé para no s'atura, o bé perquè ha retornat cert. Això voldria dir que o bé para no funciona per a totes les entrades vàlides, o bé que problema s'hauria d'haver parat.

En qualsevol cas es pot concloure que para no ha donat la resposta correcta, contradient l'afirmació inicial. Com que el mateix raonament es pot aplicar a qualsevol programa que es pugui presentar com a solució al problema de la parada, no pot haver-hi solució.

Aquesta solució clàssica s'anomena demostració diagonal, anomenada així perquè si s'imagina una quadrícula contenint tots els valors de para(p, i), amb tots els possibles valors de p a cada fila, i cada valor possible d'i a les columnes, aleshores els valors de para(s, s) estan a la diagonal d'aquesta quadrícula. La demostració es pot canviar per la pregunta: a quina fila de la quadrícula li correspon la cadena t? La resposta és que la funció problema és concebuda de forma que para(t, i) és diferent a cada fila en almenys una posició: en concret, la diagonal principal, on t=i. Això contradiu el requeriment de què la quadrícula conté una fila per a cada valor possible de p, i per tant constitueix una demostració per reducció a l'absurd que el problema de la parada és indecidible.