Carrera:
Informática
Semestre:
5to.
Semestre
Materia:
Trabajo:
Maestro:
Alumno:
En 1928 se había publicado un
pequeño texto de lógica de Hilbert y Ackermann.... El libro enfatizaba la
lógica de primer orden.... Los autores mostraron cómo las varias partes de las
matemáticas podían ser formalizadas dentro de la lógica de primer orden y daban
un conjunto sencillo de reglas de prueba para hacer las inferencias lógicas.
Hacían notar que toda inferencia que podía ser realizada de acuerdo con las
reglas de prueba era también válida, en el sentido de que en una estructura
matemática en que todas las premisas son verdaderas, la conclusión es también
verdadera.... Un problema levantado por Hilbert y Ackermann en su tratado era
el problema decisorio, el problema de encontrar un algoritmo que determine si
una inferencia propuesta determinada es válida.... Este problema es equivalente
a buscar un algoritmo para determinar si una conclusión particular puede
derivarse de ciertas premisas usando las reglas de prueba Hilbert- Ackermann.
El problema decisorio fue llamado "el principal problema de la lógica
matemática", porque un algoritmo para el problema decisorio podría, en
principio, ser usado para contestar cualquier pregunta matemática: sería
suficiente emplear una formulación en lógica de primer orden de la rama de las matemáticas
pertinente a la cuestión bajo consideración. La atención de Alan Turing fue
atraída hacia el problema decisorio ... y pronto vio cómo resolver el problema
en la negativa. Esto es, Turing mostró que no hay algoritmo alguno para
resolver el problema decisorio. Las herramientas que Turing desarrolló para
este propósito han resultado ser absolutamente fundamentales para la
informática.
Si una
solución positiva al problema decisorio llevaría a algoritmos para resolver
todas las cuestiones matemáticas, entonces se sigue que si existe incluso un
solo problema que no tiene solución algorítmica, entonces el mismo problema
decisorio no puede tener solución algorítmica. Ahora bien, la noción intuitiva
de algoritmo sirve perfectamente bien cuando lo que necesitamos
verificar es que algún procedimiento propuesto de verdad constituye una
solución positiva a un problema dado. Sin embargo, si permanecemos en este
nivel intuitivo, no podríamos esperar probar que algún problema no tiene
solución algorítmica. Para estar seguros de que ningún algoritmo funcionará,
parece necesario hacer un reconocimiento de la clase de todos los algoritmos
posibles. Esa es la tarea que se impuso Turing. Comenzó con un ser humano,
quien realizaría los pasos sucesivos requeridos por algún algoritmo; esto es,
Turing propuso considerar el comportamiento de un "computador". Aquí
la palabra computador se refiere a una persona que realiza una
computación; así era como Turing (y todo el mundo) usaba la palabra en 1935.
Turing procedió por una secuencia de simplificaciones, cada una de las cuales
podía verse que no planteaba ninguna diferencia esencial, para obtener su
caracterización de computabilidad.
La teoría
de la computabilidad y la no computabilidad es usualmente llamada la teoría de las
funciones recursivas. Esta materia concierne la existencia de procedimientos
puramente mecánicos para resolver varios problemas. Aunque la teoría es una
rama de las matemáticas puras, es, por su pertinencia en relación con ciertas
cuestiones filosóficas y la teoría de los computadores digitales, de interés
potencial para los no matemáticos. La existencia de problemas absolutamente
insolubles y el teorema de la incompletabilidad de Gödel están entre los
resultados en teoría de la computabilidad que tienen significación filosófica.
La existencia de máquinas universales de Turing, otro resultado de la teoría,
confirma la creencia de aquellos que trabajan con computadoras digitales de que
es posible construir un computador digital de propósito general en el cual se
pueda programar (dentro de limitaciones de tiempo y memoria) cualquier problema
que pudiera programarse para cualquier computador digital determinístico
concebible. Este aserto se oye a veces en su forma reforzada: cualquier cosa
que puede hacerse completamente precisa puede ser programada para una
computadora digital de propósito general. Sin embargo, en esta forma el aserto
es falso.
La gran importancia del concepto de
recursividad general (o computabilidad de Turing) ... [es que] con este concepto
se ha tenido éxito por primera vez en dar una definición absoluta de una noción
epistemológica importante, a saber sin dependencia de un formalismo
determinado.
La
creciente percepción de que una solución al problema decisorio produciría un
procedimiento para solucionar muchos (si no todos) los problemas matemáticos
significó que algunos matemáticos, especialmente von Neumann, se convencieran
de que no podía haber tal solución; una creencia que llegó a ser casi una
certidumbre cuando Gödel publicó [su famoso artículo en] 1931. Para fundar esa
certidumbre, sin embargo, era esencial poner límites precisos a
"eficazmente calculable". Esto (combinado con un interés natural por
el cálculo mecánico) era lo que estaba en la atmósfera que Turing respiraba....
Turing mostró que el cálculo puede descomponerse en la iteración (controlada
por un "programa") de operaciones concretas extremadamente simples;
tan concretas que pueden fácilmente ser descritas en términos de mecanismos
(físicos).
La
computabilidad Turing fue una de tres maneras equivalentes de caracterizar
exactamente las funciones para las cuales existen algoritmos que aparecieron en
los años mil novecientos treinta. Los conceptos usados en las otras dos fueron
la definibilidad lambda de Church-Kleene (desarrollada en la Universidad de
Princeton en 1932 y 1933) y la recursividad general de Herbrand-Gödel
(presentada por Gödel en sus conferencias de 1934 en el Instituto de Estudios
Avanzados en Princeton). Su equivalencia la estableció Kleene en 1936....
En general, el problema
decisorio para una propiedad es soluble si existe una prueba mecánica (=
una rutina computacional, un procedimiento eficaz) que, aplicado a cualquier
objeto de la suerte apropiada, eventualmente clasifica ese objeto correctamente
como un caso positivo o negativo de tal propiedad ("eventualmente"
significa aquí "después de un número finito de pasos"). Una prueba
positiva para una propiedad es una prueba mecánica que eventualmente clasifica
como positivos todos y solo sus casos positivos. Una prueba negativa es aquella
que eventualmente clasifica como negativos todos y solo los casos negativos. Si
ambas pruebas, positiva y negativa, para la propiedad existen, entonces y solo
entonces el problema decisorio para tal propiedad es soluble; siendo así que
cualquier objeto apropiado será o bien un caso positivo o un caso negativo, si
uno está equipado con ambas clases de prueba, puede aplicar ambas al objeto
dividiendo el tiempo de modo que se alternen los pasos de las dos pruebas y
así, eventualmente, descubriremos qué clase de caso es el objeto
(conversamente, cualquier prueba que clasifica eventualmente en forma correcta
cualquier objeto o bien como caso positivo o bien como caso negativo cuenta
como una prueba positiva y negativa). Aquí las propiedades que nos interesan
son validez y satisfabilidad, y los "objetos de la suerte apropiada"
son enunciados en la notación de la lógica de primer orden.
El
problema del procedimiento decisorio ... fue propuesto en los años veinte como
el de encontrar un procedimiento algorítmico general para resolver todas las
cuestiones matemáticas, y por ese medio declarar el concepto de verdad
matemática como idéntico al de prueba o axiomaticidad. Este programa de
investigación sufrió un golpe fatal tan temprano como 1931, cuando Kurt Gödel
probó su célebre teorema sobre la incompletabilidad de la aritmética.
En este
contexto, los algoritmos son concebidos como procedimientos computacionales
eficaces para resolver problemas, a saber, conjuntos de instrucciones que
proveen vías mecánicas por medio de las cuales contestar cualquiera de una
clase de preguntas. Tales instrucciones son concebidas como que no requieren
pensamiento "creativo" en su ejecución, puesto que, en principio, es
siempre posible construir una máquina para llevar a efecto un conjunto de
instrucciones o preparar un programa por medio del cual alguna computadora
digital del tamaño adecuado pueda llevarlas a cabo.
En el
teorema de la incompletitud de Gödel, se asocian números a los enunciados y los
enunciados sobre otros enunciados se traducen a enunciados sobre números. Se
pueden decir cosas como esta: "el enunciado del sistema S cuyo
número es n no puede probarse en el sistema S", lo cual es
un enunciado sobre el número n. Ahora bien, puede mostrarse que existe
un número k tal que el significado del enunciado cuyo número es k
resulta ser "el enunciado cuyo número es k carece de prueba en el
sistema S". Así pues, hemos obtenido un enunciado verdadero pero
que no puede probarse.
Podemos
dar una caracterización matemática de una clase de objetos como "máquinas
Turing". Podemos también caracterizar matemáticamente una clase de
funciones numéricas, las funciones computadas por las máquinas Turing: son las
llamadas funciones computables, y se propone que se identifican con el
concepto intuitivo de funciones eficazmente calculables que en esta forma
adquiere una definición precisa.
Una
función parcialmente computable puede ser pensada como la que posee un
algoritmo que nos permite computar su valor para elementos de su dominio, pero
que nos tendrá computando eternamente si intentamos obtener un valor funcional
para un elemento que no está en su dominio, sin asegurarnos nunca que no
obtendremos un valor. En otras palabras, cuando es posible una respuesta, el
algoritmo la provee; cuando no es posible, el algoritmo nos mantiene buscando
la respuesta en vano por un tiempo infinito.
La
situación [de la identificación de calculabilidad eficaz con computabilidad] es
análoga a la de sustituir un concepto vago, con potente atractivo intuitivo,
por un concepto matemático exacto.... En tal caso no tiene sentido, por
supuesto, pedir una prueba matemática de la equivalencia de los dos conceptos;
la misma vaguedad del concepto intuitivo lo impide. Sin embargo, es posible
presentar argumentos con poderoso atractivo intuitivo, que tienden a hacer la
identificación sumamente razonable.
Diferentes
personas hicieron propuestas más o menos al mismo tiempo (1936),
independientemente unas de otras, para identificar el concepto de función
eficazmente calculable con varios conceptos precisos. En esta conexión vale la
pena mencionar la noción de definibilidad lambda de Church, la noción de
recursividad general de Herbrand-Gödel-Kleene, la noción de computabilidad
de Turing..., la noción de definibilidad-1 de Post.... Se demostró que
todas estas nociones son equivalentes.
Esto
agregó mucha fuerza al punto de vista, que llegó a conocerse como la Tesis
Church-Turing, de que la máquina Turing (o su equivalente) de hecho define lo
que, matemáticamente, entendemos por un procedimiento algorítmico (o eficaz o
recursivo o mecánico).