Diferencia entre revisiones de «La tesis de Church-Turing/Introducción»

Contenido eliminado Contenido añadido
Sin resumen de edición
Sin resumen de edición
Línea 22:
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, bastabastaba con encontrar un sólo problema matemático que carezcacareciera 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. puestoEste quehecho se encuentra muy relacionadarelacionado 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, pero que se encuentran relacionados con la filosofía, son:
 
* La existencia de problemas absolutamente insolubles
Línea 36:
== La computabilidad Turing ==
 
Otro de los resultados más importantes de esta teoría es la existencia de las máquinas universales de Turing,. estoEstos es,modelos máquinas queteóricos simulan ser una máquina de Turing recibiendo en su entrada (en la cinta), todo lo relativo aal la máquinamodelo a imitar, perosin queembargo tienenposeen un conjunto finito que no debe ser modificado.
 
La máquina puede recibir como información de entrada instrucciones o estados de la misma.
De esta forma se reafirma la creencia, principalmente de aquellas personas que trabajan con computadores digitales, de que es posible imaginar y crear un ordenador de próposito general. Esto nos permitiría utilizar dicho ordenador en cualquier tipo de computador digital determinístico que podamos concebir.
 
En 1930, la computabilidad Turing permitió clasificar las funciones para las que existen algoritmos. Pero elEl dilema (laera tesis o conjetura) erasaber si, habiendo probado que habíaexistían problemas no resolubles por la Máquina de Turing, porque carecían de resoluciónsolución algorítmica,algoritmica sio había también algunopor que, aunesta teniéndolo, tampocono podía ser computado por ellaresolverlos.
 
Por tanto la cuestión es saber si la intuición humana supera o no la capacidad de una máquina de Turing.
En esencia, lo único que se intenta decir es que las instrucciones que la máquina de algún modo recibe indicando la manera en que se va a tratar la información de entrada, puede introducirse como estados de la máquina o como entrada para la cinta.
 
En 1930, la computabilidad Turing permitió clasificar las funciones para las que existen algoritmos. Pero el dilema (la tesis o conjetura) era si, habiendo probado que había problemas no resolubles por la Máquina de Turing porque carecían de resolución algorítmica, si había también alguno que, aun teniéndolo, tampoco podía ser computado por ella.
 
Dado que será la intuición o creatividad humana la que lo intente probar, todo se resumía en saber si la computación intuitiva superaba a la de Turing.