La tesis de Church-Turing/Introducción
En primer lugar vamos a introducir el concepto de teoría de la computabilidad, para ayudarnos a comprender este artículo.
Nociones Básicas acerca de la Teoría de la Computabilidad
editarLa Teoría de la Computabilidad está compuesta por los siguientes niveles:
- Primer nivel: divide los problemas en tres clases:
- Primer tipo:Problemas imposibles, no tienen solución.
- Segundo tipo: Problemas ejecutables solo si disponemos de recursos ilimitados.
- Tercer tipo:Problemas que se pueden ejecutarse sin necesidad de recursos ilimitados.
- Segundo nivel: se clasifican en función del tiempo que tardan en ejecutarse. Se conocen con el nombre de problemas indecidibles, impracticables o solucionables.
- Tercer nivel: comprende aquellos problemas que por ejemplo requiere un tiempo linealmente proporcional a su tamaño.
La incompletitud
editarUna de las preguntas que Hilbert planteó fue si las matemáticas eran completas, es decir: si cada proposición podía ser demostrada o refutada dentro de las matemáticas.
Gödel teorizó sobre la incompletitud de los sistemas axiomáticos, pero, tras varios intentos, fue Alan Turing quien apoyó esta teoría con la creación de su máquina, minuciosamente ideada para que pudiera interpretar cualquier algoritmo, y que sin embargo tenía problemas fuera de su alcance.
Para demostrar este hecho, bastaba con encontrar un sólo problema matemático que careciera de solución algorítmica.
La teoría de la computabilidad es conocida, también, como la teoría de las funciones recursivas. Esta disciplina contempla la existencia de procedimientos puramente mecánicos para resolver diferentes problemas.
Aunque esta teoría pertenece, principalmente, al campo de las matemáticas puras, es especialmente importante para aquellos que no son matemáticos. Este hecho se encuentra muy relacionado tanto con determinadas cuestiones filosóficas como con la teoría de los computadores digitales.
Algunos de los resultados que se encuentran englobados dentro de la teoría de la computabilidad son:
- La existencia de problemas absolutamente insolubles
- Teorema de la incompletitud de Gödel
La computabilidad Turing
editarOtro de los resultados más importantes de esta teoría es la existencia de las máquinas universales de Turing. Estos modelos teóricos simulan ser una máquina de Turing recibiendo en su entrada, todo lo relativo al modelo a imitar, sin embargo poseen un conjunto finito que no debe ser modificado.
La máquina puede recibir como información de entrada instrucciones o estados de la misma.
En 1930, la computabilidad Turing permitió clasificar las funciones para las que existen algoritmos. El dilema era saber si existían problemas no resolubles por la Máquina de Turing, porque carecían de solución algoritmica o por que esta no podía resolverlos.
Por tanto la cuestión es saber si la intuición humana supera o no la capacidad de una máquina de Turing.