Problema de la Parada

This post is also available in: Inglés

Problema de la Parada

El problema de la parada fue propuesto por Turing por primera vez a principios del siglo XX. Se trata de encontrar una forma de responder sistemáticamente a la pregunta de si un cierto programa informático parará.

Por ejemplo, tomemos un programa de ordenador que calcule 2 + 2. Sabemos que el programa se detendrá cuando nos dé el resultado “4”. También podríamos hacer un programa que buscase el número natural más grande y se detuviera cuando lo hubiera encontrado. Como los números naturales son infinitos, sabemos que ese programa nunca parará.

También podríamos construir otro programa que pasara por cada número par y comprobase si se puede expresar como la suma de dos primos, para finalmente detenerse cuando encontrase uno que no se pudiera expresar así. En este caso, no tenemos forma de saber si el programa se detendrá en algún momento, porque si lo supiéramos habríamos resuelto el problema de la conjetura de Goldbach, que sigue abierto.

Turing se retó a encontrar un algoritmo general que pudiese decidir si un programa cualquiera se parará en algún momento, y demostró que es imposible. No existe ningún algoritmo general que pueda averiguar si un programa cualquiera parará o no. Este resultado está relacionado íntimamente con el teorema de incompletitud de Gödel y puede verse como otra forma de enfocar la misma idea.

Más información en la Wikipedia.org.

Share and Enjoy:
  • Digg
  • del.icio.us
  • Facebook
  • Yahoo! Buzz
  • Twitter
  • Google Bookmarks
  • Bitacoras.com
  • Google Buzz
  • Meneame
  • Reddit
  • RSS

Leave a Reply

You can use these HTML tags

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>