Funciones computables y no computables

hola

REDUCIBILIDAD

Funciones 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 no computables. 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 muchos añ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 para grupos.

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ías ló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 de las 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 como consecuencia 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 de una

...