Problema de la parada

De Wikipedia, la enciclopedia libre

Este artículo o sección tiene un estilo difícil de entender para los lectores interesados en el tema. Si tienes capacidad, por favor edítalo, contribuye a hacerlo más accesible para el público general, sin eliminar los detalles técnicos que interesan a los especialistas.

El problema de la parada o problema de la detención para Máquinas de Turing consiste en lo siguiente: dada una Máquina de Turing M y una palabra w, determinar si M se detendrá cuando es ejecutada usando w como dato de entrada. Alan Turing, en su famoso artículo "On Computable Numbers, with an Application to the Entscheidungsproblem" (1936), demostró que el problema de la parada de la Máquina de Turing es indecidible.

[editar] Idea de la demostración

Hablando formalmente, Turing demostró que este problema es indecidible en términos de máquinas de Turing. Para tener una idea más natural (y por simplicidad hablando en término de pseudocódigo) haremos una pequeña demostración por una reducción a lo absurdo:

Supongamos que existe una máquina de turing Mhp(Mk,T) que recibe:

  una máquina de turing (Mk)
  y una cadena (T)

y determina si al ejecutar Mk con T en la cinta para o no para.

Ahora bien, definamos Ml(Mk) como una máquina de turing que recibe una máquina de turing (Mk) y realiza Mhp(Mk,Mk) y si es cierto, entonces Ml(Mk) se para, sino Ml(Mk) termina.

Ahora hagamos Mhp(Ml(Ml)), es decir, que dada nuesta máquina de turing inicial, comprobamos la entrada Ml(Ml), y esto último es aplicar a la segunda máquina ella misma:

  Si Mhp(Ml(Ml)) es cierto es porque (Ml(Ml)) termina, entonces Mhp(Ml(Ml)) es cierto, pero por construcción de Ml, termina cuando Mhp(Ml(Ml)) es falso.
  Si Mhp(Ml(Ml)) es falso, es porque (Ml(Ml)) no termina, pero por construcción (Ml(Ml)) se cuelga cuando Mhp(Ml(Ml)) es cierto.

Por ende, llegamos una contradicción, por lo que no existe la máquina de turing Mhp.