Problema da parada

miniatura|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 grande 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, a á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:
```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:
```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:
{{Ecuación|\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*:
```python
def Diagonal(Diagonal):
     if Termina(Diagonal, Diagonal):
         while True: pass
```
Neste caso tense w=Diagonal, e por tanto{{Ecuación|\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.

centro|240x240px

* 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:

# *Diagonal* emprega a máquina *Copia* para replicar a cadea w, transformándoa en w,w.
# *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.

centro|358x358px
A máquina *Diagonal* está deseñada para cumprir a propiedade:

# Aplícase a codificación da máquina *Diagonal* á propia máquina *Diagonal* (w  como codificación de *Diagonal*).
# Séguese que *Diagonal* para ante si mesma como entrada se e só se *Diagonal* non para ante si mesma como entrada w.
# 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 
* 
* 
* 
* 
* 
### Outros artigos 
* Máquina de Turing