Mostra la font per a 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:<ref>{{Ref-llibre|cognom=Immerman|nom=Neil|títol=Computability and Complexity|url=https://plato.stanford.edu/archives/spr2016/entries/computability/|edició=Spring 2016|data=2016|editorial=Metaphysics Research Lab, Stanford University}}</ref>

: ''donada una descripció d'un [[Programa informàtic|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àquina de Turing|màquines de Turing]].<ref>{{Ref-publicació|cognom=Turing|nom=A. M.|article=On Computable Numbers, with an Application to the Entscheidungsproblem|publicació=Proceedings of the London Mathematical Society|llengua=en|url=https://londmathsoc.onlinelibrary.wiley.com/doi/abs/10.1112/plms/s2-42.1.230|volum=s2-42|exemplar=1|data=1937|pàgines=230–265|doi=10.1112/plms/s2-42.1.230|issn=0024-6115}}</ref>

==Descripció formal==
Una forma possible de definició formal del problema de la parada és el següent:<ref>{{Ref-llibre|cognom=Michael,|nom=Sipser,|títol=Introduction to the theory of computation|url=https://www.worldcat.org/oclc/35558950|data=1997|editorial=PWS Pub. Co|lloc=Boston|isbn=053494728X}}</ref>

Donat un [[nombre de Gödel]] <math>\varphi</math> de [[Funció computable|funcions computables]],

amb <math>\langle i, x \rangle</math> les [[Funcions de còpia de Cantor]], 

el conjunt <math>K_{\varphi}^{0} := \{ \langle i, x \rangle | \varphi_i(x) \ \mathrm{existeix} \}</math> 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 [[Conjunt enumerable recursivament|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 [[Alonzo Church|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.<ref>{{Ref-publicació|cognom=Church|nom=Alonzo|article=An Unsolvable Problem of Elementary Number Theory|publicació=American Journal of Mathematics|url=http://www.jstor.org/stable/2371045|volum=58|exemplar=2|data=1936|pàgines=345–363|doi=10.2307/2371045}}</ref>

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 [[nombre natural|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 [[Constant de Chaitin|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 dóna 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ística|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òmat linial limitat|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 <code>para(p, i)</code> 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 <code>problema</code> que fa servir <code>para</code> 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 <code>para</code>, passant-li ''s'' tant com descripció de programa i com a dades d'entrada pel programa. Si <code>para</code> retorna '''cert''', llavors <code>problema</code> es queda executant-se per sempre; si no, <code>problema</code> retorna '''cert'''. Com que tots els programes es poden representar mitjançant cadenes de caràcters, existeix una cadena ''t'' que representa el programa <code>problema</code>. <code>problema(t)</code> s'aturarà?
Considerant els dos casos:
# Si <code>problema(t)</code> s'atura, ha de ser perquè <code>para(t,t)</code> ha retornat '''fals''', però això voldria dir que <code>problema(t)</code> no s'hauria d'haver aturat.
# Si <code>problema(t)</code> no s'atura mai, és perquè o bé <code>para</code> no s'atura, o bé perquè ha retornat '''cert'''. Això voldria dir que o bé <code>para</code> no funciona per a totes les entrades vàlides, o bé que <code>problema</code> s'hauria d'haver parat.

En qualsevol cas es pot concloure que <code>para</code> 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 <code>para(p, i)</code>, amb tots els possibles valors de ''p'' a cada fila, i cada valor possible d'''i'' a les columnes, aleshores els valors de <code>para(s, s)</code> 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ó <code>problema</code> és concebuda de forma que <code>para(t, i)</code> é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. 

== Referències ==
{{Referències}}{{Autoritat}}

[[Categoria:Computabilitat]]
[[Categoria:Màquines de Turing]]