Computabilidad y decidibilidad

Abstract

Algoritmos En el siglo nueve, el califa Abdullah al-Ma'mün ibn Harun estableció en Bagdag una “casa de la sabiduría“, una institución de investigación que invitaba a sabios académicos. Entre los primeros académicos se encontraba Muhammad ibn Musa al-Khwárízmt. Él escribió varios trabajos, entre los cuales se encuen¬tra “Algoritmi de numero Indorum“, nombre en latín pues el original en árabe ya no existe. En este texto, cada hoja comenzaba con la frase “dixit algoritmi“ que significa “así lo dijo al-Khwarizmi. De esta manera, un matemático del siglo VII dio su nombre al concepto central de la ciencia de la computación. A través del trabajo de al-Khwarizmi las técnicas de la aritmética fueron conocidas en Europa como algorismo y el nombre permaneció, como algoritmo para denotar a un procedimiento para resolver un problema en un número finito de pasos. Sin embargo, algoritmos han existido desde mucho antes de que exista una palabra que los describa. Una vez descubierto un método rutinario para obtener la solución de un problema, no es sorpresa que tal 'receta' fuera compartida a otros para usarse. Los algoritmos no están confinados a la matemática, por ejemplo, los Babilonios los usaban para aplicar leyes, algunas culturas los usaban para predecir el futuro; y actualmente se usan en medicina para diagnosticar enfermedades» y en la cocina a manera de recetas. El décimo problema de Hilbert En 1900, el matemático alemán David Hilbert, en el congreso internacional de matemáticos en París, presentó una lista de 23 problemas, en esa época aún por resolverse. El décimo problema propuesto dictaba lo siguiente1 10. Determinación de la solubilidad de ecuaciones diofanticas. Dada una ecuación diofántica con cualquier número de incógnitas y con coeficientes numéricos racionales enteros: Idear un proceso con el cual pueda determinarse, en un número finito de operaciones, si la ecuación es resoluble en números racionales enteros. Pese a que Hilbert no creía en la existencia de problemas insolubles, el décimo problema de Hilbert fue resuelto negativamente gracias al trabajo conjunto de Martín Davis, Julia Robinson y Yuri Matija-seviC [Matijascvic, 1970, Davis et al., 1961, Robinson, 1969]. Estos probaron que, de hecho, no existe algoritmo {en el sentido formal dado por Church y Turing) tal que, para cualquier ecuación diofántica, determine si esta tiene soluciones enteras. Problemas de este tipo se denominan indecidibles. La existencia de estos problemas muestra un límite a la capacidad humana de resolver problemas mediante un computador, al igual que el teorema de incompletitud de Godel muestra un límite del razonamiento lógico humano para demostrar afirmaciones. Computabilidad en la década de 1930 No es posible resolver este problema sin una definición formal de proceso. Es así que este problema inició el estudio de la teoría de la computabilidad, desarrollada por Godel, Church, Turing, Post, Kleene, etc., comenzando en la década de 1930, Dicha teoría está relacionada fuertemente con la lógica. Los dos logros más importantes en esta área fueron dados por el descubrimiento de la incompletitud por Godel [Godel, 1931] y la definición de computabilidad, dada independientemente por Church [Church, 1936], al definir el cálculo, y por Turing [Turing, 1936] al definir las máquinas de Turing. El teorema de incompletitud de Godel dio una respuesta parcial al segundo problema de Hilbert2, mientras que Church y Turing intentaron dar definiciones formales de computabilidad para obtener una función incomputable, usando la técnica de Godel. Mas adelante, Godel y Kleene introdujeron el concepto defunción p-recursiva que resulta coincidir con los conceptos previos de computabilidad de Church y Turing. Objetivo y plan de trabajo El objetivo de este trabajo es presentar un estudio formal de computabilidad, haciendo énfasis en las máquinas de Turing, así como de decidibilidad. El fundamento teórico usado a lo largo del trabajo estará dado en el capítulo 1. Esto consta de teoría de conjuntos, relaciones y funciones, así como también la teoría de cadenas y lenguajes, En el capítulo 2 introduciremos las nociones de computabilidad de Turing, Church y Godel-Kleene, así como la relación existente con la noción usual de algoritmos. En este caso, enfatizaremos el estudio de las máquinas de Turing. Presentaremos además un ejemplo de función no computable, según las nociones mencionadas. En el capítulo 3, estudiamos La decidibilidad de lenguajes y de problemas, y presentaremos ejemplos de lenguajes y problemas no decidibles. Finalmente, en el apéndice presentamos transcripciones de los artículos originales de Church y Turing.