Teoria de la computabilidad

TEORIA DE LA COMPUTABILIDAD
El propósito inicial de la teoría de la computabilidad es hacer precisa la noción intuitiva de función calculable; esto es, una función cuyos valores pueden ser calculados de forma automática o efectiva mediante un algoritmo. Así podemos obtener una comprensión más clara de esta idea intuitiva; y solo de esta forma podemos explorar matemáticamente el concepto decomputabilidad y los conceptos relacionadas con ella, tales como decibilidad, etc... Surge así una teoría que producirá resultados positivos y negativos (estamos pensando en resultados de no computabilidad o de indecibilidad).
La teoría de la computabilidad puede caracterizarse, desde el punto de vista de las C.C., como la búsqueda de respuestas para las siguientes preguntas: 1)¿Qué pueden hacer losordenadores (sin restricciones de espacio, tiempo o dinero )?; 2) ¿Cuales son las limitaciones inherentes a los métodos automáticos de cálculo?.
Que problemas resuelve?
No todos los problemas pueden ser resueltos. Un problema indecidible es uno que no puede ser resuelto con un algoritmo aún si se dispone de espacio y tiempo ilimitado. Actualmente se conocen muchos problemas indecidibles, comopor 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 (ver Tesis de Church-Turing).
* El Problema de la parada, que se define así: Dado un programa y su entrada, decidir si ese programaterminará 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 es computable aunque sí que está bien definido.HISTORIA
El primer paso en la búsqueda de las respuestas a estas preguntas está en el estudio de los modelos de computación que serán los que nos harán preciso el concepto de algoritmo. Los modelos abstractos de computación tienen su origen en los años 30, bastante antes de que existieran los ordenadores modernos, en el trabajo de los lógicos Church, Gödel, Kleene, Post, y Turing. Estos primerostrabajos han tenido una profunda influencia no solo en el desarrollo teórico de las C.C., sino que muchos aspectos de la práctica de la computación que son ahora lugar común de los informáticos, fueron presagiados por ellos; incluyendo la existencia de ordenadores de propósito general, la posibilidad de interpretar programas, la dualidad entre software y hardware, y la representación de lenguajes porestructuras formales basados en reglas de producción.
El punto de partida de estos primeros trabajos fueron las cuestiones fundamentales que D. Hilbert formuló en 1928, durante el transcurso de un congreso internacional:
1.- ¿Son completas las matemáticas, en el sentido de que pueda probarse o no cada aseveración matemática?
2.- ¿Son las matemáticas consistentes, en el sentido de que no puedaprobarse simultaneamente una aseveración y su negación ?
3.- ¿Son las matemáticas decidibles, en el sentido de que exista un método definido que se pueda aplicar a cualquier aseveración matemática, y que determine si dicha aseveración es cierta?.
La meta de Hilbert era crear un sistema matemático formal "completo" y "consistente", en el que todas las aseveraciones pudieran plantearse conprecisión. Su idea era encontrar un algoritmo que determinara la verdad o falsedad de cualquier proposición en el sistema formal. A este problema le llamó el `Entscheidungsproblem'. Si Hilbert hubiera podido cumplir su objetivo, cualquier problema que estuviera bien definido se resolvería simplemente al ejecutar dicho algoritmo.
Por desgracia para Hilbert, en la década de 1930 se produjeron una...