Indecibilidad

INDECIBILIDAD

INTRODUCCIÓN

Las técnicas para la demostración de la indecidibilidad de las teorías aparecen habitualmente en matemáticas. Los teoremas fundamentales de indecidibilidad se obtuvieron en la década de 1930 por Church, Turing, Godel y Rosser. Posteriormente se obtuvieron nuevos resultados de indecidibilidad utilizando la idea de Tarski de interpretar unas teorías en otras.
En1935 Alan Turing realiza profundos estudios de lógica, que le llevan al descubrimiento de la indecidibilidad de las matemáticas a través del concepto de lo que hoy conocemos como Máquina de Turing. Este mismo descubrimiento también fue realizado por Alonzo Church que utilizo la Lógica Clásica de Primer Orden el Lambda Cálculo. Dichos artículos se publicaron en fechas diferentes.
Church publicó suartículo en abril de 1936, mientras que el de Turing se publicó en agosto de 1936, asi que tuvo que referenciar el trabajo de Church. Pero desde el primer momento se reconoció que las dos aproximaciones al problema eran totalmente independientes; es decir eran diferentes uno del otro.
Turing se planteó el problema de Hilbert y que éste se podía resolver por una maquina de turing, definiendoasí que era negativo.
La Máquina de Turing (MT) es el paradigma de computación vigente hoy día. Esto nos plantea que cualquier secuencia de instrucciones realizables en tiempo finito en una computadora, es realizado por una Máquina de Turing (MT). En otras palabras esto nos da e entender que un algoritmo en una computadora se realiza por una máquina de Turing.
Dado un enunciado de entrada a unaMT, luego de ser procesado bajo las instrucciones de la máquina, ésta posiblemente proporcione un resultado de salida. El enunciado de entrada es la tarea que se asigna a la computadora y el enunciado de salida es el resultado que entrega, si es el caso.

DESARROLLO
Uno de los usos de la Máquina de Turing fue dar respuesta a un problema planteado por Hilbert: ¿Existe algún proceso definido(algoritmo) que pueda decidir la veracidad de cualquier enunciado matemático? La respuesta fue negativa. Alonzo Church llegó a la misma conclusión utilizando otro método (el lambda cálculo). Se puede denotar la comprensión de esto mediante
Al contrario de lo que pensaban muchos matemáticos de la época que buscaban en el fundamento lógico de las matemáticas, la justificación de intuiciones que nosólo no se vieron refrendadas sino que se demostraron incorrectas. A este revés al que podríamos llamar la indecibilidad de las Matemáticas (más exactamente la indecibilidad de la Lógica Clásica de Primer Orden) (Church-Turing) se unía a otro revés ocurrido sólo cinco años atrás (1931).
En este caso había sido el joven lógico Kurt Gödel quien demostró el teorema de incompletitud, que aplicado a lasMatemáticas nos dice que existen enunciados verdaderos que no pueden demostrarse, daba así al traste con las esperanzas de construir un sistema "perfecto" buscado por matemáticos tan prestigiosos como Bertrand Russel.
Sin embargo el concepto de Máquina de Turing no sólo sirvió para demostrar la indecibilidad sino que estableció reglas claras para lo que se considera computable, estas reglassiguen siendo las mismas en los ordenadores actuales aunque no se basen en el diseño teórico de la Máquina de Turing.

La lógica matemática y el formalismo matemático se desarrollaron hasta culminar en la famosa obra de Russell Y Whitehead Principia Matemática. La "certidumbre" de las matemáticas se volvía cada vez más evasiva hasta que Kurt Godel puso punto final a toda esperanza de obtenersistemas matemáticos rigurosos basados en el método axiomático. Su famoso teorema de 1931 establece que hay cuestiones en matemáticas que son " indecidibles ", es decir, que no se pueden ni demostrar ni refutar a partir de los axiomas.
El principio de indecidibilidad de Turing dice que no es posible escribir un programa que decida si otro programa cualquiera está correctamente escrito. Esto si...