computabilidad

Universidad de Guadalajara
Centro Universitario
de Ciencias Exactas e Ingenierías
“Computabilidad”
Materia:
Teoría de la Computación.



Computabilidad.
La Computabilidad estudia los problemas de decisión que pueden ser resueltos con un algoritmo o equivalentemente con una Máquina de Turing. La teoría de la computabilidad se interesa a cuatro preguntas:
¿Qué problemas puede resolveruna Máquina de Turing?
¿Qué otros formalismos equivalen a las Máquinas de Turing?
¿Qué problemas requieren Máquinas más poderosas?
¿Qué problemas requieren Máquinas menos poderosas?
La teoría de la complejidad computacional clasifica las funciones computables según el uso que hacen de diversos recursos en diversos tipos de máquina.
Antecedentes.
El origen de los modelos abstractos decomputación se encuadra en los años '30 (antes de que existieran los ordenadores modernos), para el trabajo de los lógicos Alonzo Church, Kurt Gödel, Stephen Kleene, Emil Leon Post, y Alan Turing. Estos trabajos iníciales han tenido una profunda influencia, tanto en el desarrollo teórico como en abundantes aspectos de la práctica de la computación; previendo incluso la existencia de ordenadores depropósito general, la posibilidad de interpretar programas, la dualidad entre software y hardware, y la representación de lenguajes por estructuras formales basados en reglas de producción.
El punto inicial de estos primeros trabajos fueron las cuestiones fundamentales que David Hilbert formuló en 1900, durante el transcurso de un congreso internacional.
Lo que Hilbert pretendía era crear un sistemamatemático formal completo y consistente en el cual, todas las aseveraciones fueran planteadas con precisión. Su intención era encontrar un algoritmo que determinara la verdad o falsedad de cualquier proposición en el sistema formal. Al problema en cuestión se le denominó Entscheidungsproblem. En caso de que Hilbert hubiese cumplido su objetivo, cualquier problema bien definido se resolveríasimplemente al ejecutar dicho algoritmo.
Pero fueron otros los que mediante una serie de investigaciones mostraron que esto no era posible. En contra de esta idea K. Gödel sacó a la luz su conocido Primer Teorema de Incompletitud. Este viene a expresar que todo sistema de primer orden consistente que contenga los teoremas de la aritmética y cuyo conjunto de axiomas sea recursivo no es completo. Gödelconstruyó una fórmula que es satisfactoria pero que no puede ser probada en el sistema.

Como consecuencia, no es posible encontrar el sistema formal deseado por Hilbert en el marco de la lógica de primer orden, a no ser que se tome un conjunto no recursivo de axiomas.
Una posterior versión, que resulta más general, del Teorema de Incompletitud de Gödel, indica que ningún sistema deductivo quecontenga los teoremas de la aritmética, y con los axiomas recursivamente enumerables puede ser consistente y completo a la vez. Esto hace pensar, a nivel intuitivo, que no va a ser posible definir un sistema formal.
¿Qué Problemas puede Resolver una Máquina de Turing?
No todos los problemas pueden ser resueltos. Un problema indecidible es uno que no puede ser resuelto con un algoritmo aún si sedispone de espacio y tiempo ilimitado. Actualmente se conocen muchos problemas indecidibles, como por ejemplo:
El Entscheidungsproblem (problema de decisión en alemán) que se define como: Dada una frase del cálculo de predicados de primer orden, decidir si ella es un teorema. Church y Turing demostraron independientemente que este problema es indecidible.
El Problema de la parada, que se defineasí: Dado un programa y su entrada, decidir si ese programa terminará para esa entrada o si correrá indefinidamente. Turing demostró que se trata de un problema indecidible.
Un número computable es un número real que puede ser aproximado por un algoritmo con un nivel de exactitud arbitrario. Turing demostró que casi todos los números no son computables. Por ejemplo, la Constante de Chaitin no...