Discusión:Problema de la parada

Nueva idea de demostracion

Sea $M_{0}$ una maquina que al funcionar con $w$ ejecuta una maquina $M_{1}$ ocupando como entrada $M_{0}$

se debe tener en cuenta siempre que $M_{0}$ se ejecuta teniendo como entrada a si misma

--- si $M_{1}$ termina, entonces

  $M_{0}$ no se detiene; sino (termina) 
  $M_{0}$ termina normalmente

---

(basico) si $M_{1}$ temina normalmente entonces $M_{0}$ nunca termina!! si $M_{0}$ temina normalmente entonces $M_{1}$ nunca termina!!

(mas dificil) $M_{1}$ termina si y solo si $M_{0}$ termina con la entrada de $M_{0}$ si y solo si $M_{1}$ no termina con la entrada $M_{0}$ si y solo si $M_{1}$ no termina $M_{0}$

llegando por supuesto a un absurdo por lo que se demuestra que es imposible construir una maquina de turing que determine si una maquina de turing determinada terminara su ejecucion algun dia. --Bagheera (discusión) 02:22 10 ene 2009 (UTC)

No comprendo del todo

Bueno si lo entiendo un poco, seria más facil comenzar a hablar sobre lo que es una maquina turing, a pesar de que ya exista el articulo.

Escritor de la demostración

Yo escribí esto hace un tiempo 1 año aprox. y nunca más volvi a entrar a este artículo... y si.. me pareció difícil de comprender. Creo que una notación en estilo pseudocódigo sería más clara, olvidandonos de las máquinas de turing, aunque no sería formal del todo se entendería la idea. Si alguien está de acuerdo... que me avise por aca que lo reescribo más sencillo. Saludos --Lechuck2008 (discusión) 07:48 29 ago 2009 (UTC)

Alguien que este de acuerdo, me aleje un poco de las matematicas subyacentes al tema, sin embargo creo, que es un tema complicado de explicar, y mientras mas simple.. mejor --Bagheera (discusión)

Y si tuviera solución ...

Suponemos que existe la función Termina( p, x ) del ejemplo que nos dice verdadero si p(x) termina o falso en el caso contrario . Y sabemos por el ejemplo que Diagonal( w ) termina <=> w(w) nunca termina. y por tanto es una paradoja e irresoluble... Pero y si Termina no pudiese resolver cualquier p(x), ... , solo el conjunto A = { p(x) - Termina(p,x) } , "El conjunto de los problemas menos Termina". De tal modo que si queremos ver si "Termina" Termina( p, x ) no podamos , que es en realidad la paradoja. Como simil, se asemejaria a un espejo, el espejo no se refleja a si mismo , solo al resto de los objetos. Asi que tendríamos el conjunto A = { todos los problemas - Termina() } , Termina(). T* = A + Termina() ... Por los Teoremas de incompletitud de Godel... Ningun sistema consistente se puede usar para demostrarse a sí mismo.

=> Esto implicaria que dentro del conjunto T* podría haber mas algoritmos excluyentes (espejo) la cuestion es con respecto a que otros algoritmos... hanllel :-)

Solución:

Dada una máquina M de Turing y una palabra w como entrada de la máquina, la máquina nunca parará en un número finito de pasos. Pues la razón de ser de la misma, es la interpretación de los símbolos que le lleguen a su entrada. Y no el algoritmo generado por la combinación de su programación y los datos de entrada. A la pregunta de si es posible saber si un algoritmo cumple con su función la respuesta es, si, mediante una consecución de objetivos. A la pregunta de si existe un algoritmo genérico que aplicado a una máquina de Turing establezca sus objetivos la respuesta es no. Los objetivos de un algoritmo no forman parte de él, van más allá. Como el objetivo de la propia existencia de la máquina M o de sus palabras de entrada.

hanllel :-)

Falacia

Modifico la explicación falaz de las consecuencias prácticas con contenido que facilmente podreis contrastar en la wikipedia inglesa, y que (ahora si) está libre de toda intencionalidad política.

Para mas adelante, sabed que no es lo mismo:

   - no se puede probar ninguno.
   - no se pueden probar todos.

¿Falacias políticas?

Creo que la siguiente frase no aporta nada al artículo. ¿Qué sabiduria popular? Y en especial, ¿qué falacias políticas intencionadas? Habría que eliminarla:

"Sin embargo hay que hacer notar que la sabiduría popular acerca de este problema hace pensar que nunca es posible demostrar que un programa termina. Esto es absolutamente falso, y procede de la negación errónea de un causal, y de otras falacias políticas intencionadas."