Lenguajes decidibles

DECIBILIDAD

Problemas computables y no computables

El identificar los problemas que son computables y los que no lo son tiene un considerable interés, pues indica el alcance y los límites de la computabilidad, y así demuestra los límites teóricos de los ordenadores. Además de las cuestiones sobre algoritmos, se han encontrado numerosos problemas menos "generales" que han resultado ser nocomputables. La mayoría de las demostraciones de no computabilidad se basan en el método de la diagonal. Como ejemplos de estos problemas podemos citar:
1.- El problema de la palabra para Grupos.- Dado un subconjunto S de elementos de un grupo G, se trata de decidir si una expresión compuesta por elementos de S y con las operaciones del grupo es igual al elemento neutro del grupo. Durante muchosaños se buscaron ejemplos de grupos finitamente presentados para los que este problema fuese indecidible. La existencia de uno de estos grupos fué encontrada por Novikov en 1955 y por Boone en 1957. En el algebra moderna hay abundantes ejemplos de interesantes problemas no computables; una gran cantidad de ellos sobre propiedades de palabras o generadores semejantes al problema de la palabra paragrupos.
2.- Décimo problema de Hilbert. Una ecuación diofántica es la ecuación de los ceros enteros de un polinomio con coeficientes enteros. El décimo problema de Hilbert, propuesto en 1900, pregunta si hay un procedimiento efectivo que determine si una ecuación diofántica tiene o no solución. Y. Matiyasevich demostró en 1970 que este problema no tiene solución.
3.- Decibilidad de las teoríaslógicas. El desarrollo de la teoría de la computabilidad ha ido íntimamente ligado al desarrollo de la lógica matemática. Esto ha sido así porque la decibilidad de los distintos sistemas lógicos es una cuestión fundamental. Es bastante fácil ver que el cálculo proposicional es decidible. Church y Turing demostraron en 1936 que el cálculo de predicados no era decidible. Por otro lado, para cada una delas distintas teorías se ha ido estudiando su posible decibilidad. Como ejemplo más ilustrativo, Tarski demostró que la teoría de los números reales era decidible.
Por otro lado, son muchos los problemas interesantes que se han demostrado computables. Todas las funciones construidas por recursividad primitiva o minimalización a partir de funciones calculables resultan ser calculables comoconsecuencia de los trabajos de Church y Turing. Pero además, otras funciones más complejamente definidas también son computables, siendo el resultado más significativo en relación con esta cuestión el dado por el siguiente teorema:
Primer teorema de Recursión. Todo operador entre funciones calculables que sea recursivo (esto es que se defina la imagen de f mediante una función calculable en términos deuna parte finita de f), tiene una función parcial computable que es el menor punto fijo, es decir, esta función es un punto fijo y cualquier otro punto fijo del operador es una extension de esa función.
Este teorema recibe su nombre porque podemos definir una función mediante una ecuación recursiva más general que la permitida por la recursividad primitiva, a saber donde [pic]es un operadorrecursivo. El primer teorema de recursión nos dice que esta definición es posible; hay una función recursiva que satisface esta ecuación. Como en matemáticas se requiere que la definición sea unívoca, se dice que dicha ecuación define el menor punto fijo del operador [pic]. Así, y de acuerdo al primer teorema de recursión, la clase de las funciones calculables es cerrada bajo una muy general forma dedefinición por recursión.
A menudo se utiliza la técnica de reducir un problema a otro para comprobar si tiene o no solución efectiva. La estratégia en el caso de la respuesta negativa es la siguiente, si se reduce de forma efectiva un problema sin solución efectiva a otro problema (mediante una función calculable), entonces este nuevo problema tampoco tendrá solución efectiva. La razón es muy...