La tesis de Church-Turing

‎‏‎‎‎‎‎‎‎‏‎‎‏‏‎‎‎‎‏‎‎‏‎‎‎‏‏‏‏‏‏‎‏‏‏‏‏‏‎‏‏‎‎‏‎‏‎‎‎‏‎‏‏‏‏‏‎‎‎‎‎‏‎‏‎‎‏‏‏‏‏‏‏‎‏‎‎‏‎‎‎‏‎‎‏‏‏‏‏‎‎‎‏‏‎Cuadro de texto‎‏‎‎‏‎

La tesis de Church-Turing

En 1936, Church logra demostrar que tanto las funciones-definibles como las funciones recursivas de Herbrand-Gödel son equivalentes. Conjetura que este tipo de funciones son las únicas funciones calculables utilizando, para ello, un algoritmo a través de la tesis que lleva su nombre:

"La clase de las funciones que pueden ser calculadas mediante un algoritmo coincide con la clase de las funciones recursivas." (Tesis de Church).

La tercera de las definiciones de función calculable tiene su origen en el matemático inglés [[Turing|Alan Turing], que fue durante un tiempo alumno de Von Neumann, y que leyó los argumentos de Hilbert durante sus estudios en Cambridge. En 1936 Turing publicó uno de sus trabajos más importantes: "Números Computables: Una Aplicación al Entscheidumgsproblem".


Nociones Básicas acerca de la Teoría de la Computabilidad

La 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

Una 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

Otro 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.


Fuente:  http://es.wikibooks.org/w/index.php?title=La_tesis_de_Church-Turing/TextoCompleto&printable=yes

ĉ
José Malaguera,
16 oct. 2009 13:26
Comments