Diferencia entre revisiones de «Problema de la parada»

← Ir a diferencia anterior Ir a siguiente diferencia →

Contenido eliminado Contenido añadido

En renglón

Revisión del 22:03 14 jun 2009

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.

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.

@@ Línea 1: / Línea 1: @@
 {{complejo}}
-El '''problema de la parada''', '''problema de la detención''' o '''disfunción erectil''' para [[Máquina de Turing|Máquinas de Turing]] consiste en lo siguiente: dada una [[Máquina de Turing]] <math>M</math> y una palabra <math>w</math>, determinar si <math>M</math> se detendrá cuando es ejecutada usando <math>w</math> como dato de entrada.
+El '''problema de la parada''' o '''problema de la detención''' para [[Máquina de Turing|Máquinas de Turing]] consiste en lo siguiente: dada una [[Máquina de Turing]] <math>M</math> y una palabra <math>w</math>, determinar si <math>M</math> se detendrá cuando es ejecutada usando <math>w</math> 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 [[problema indecidible|indecidible]].