19 Jun
Límites de la Computabilidad
Funciones Incomputables
a) Funciones de Naturales a Naturales Computables
Turing ya demostró que no todas las funciones de números naturales a naturales son computables. Hay más funciones de números naturales a naturales que máquinas de Turing (MT). Puesto que toda MT puede ser codificada por un número natural diferente, hay el mismo número de MT que de números naturales. Pero recordemos que hay más funciones f:N→N que MT.
Dados dos conjuntos A y B, el producto cartesiano de A y B, A × B = {: a∈A y b∈B}. Por el teorema de Cantor sabemos que la cardinalidad de N×N es mayor que la de N. Lo mismo pasa con las funciones de números naturales que son computadas por una MT, puesto que sabemos que son iguales a los números naturales. Luego la cardinalidad de las MT es la misma que la de los números naturales, y menor que la de las funciones. Hay más funciones de naturales a números naturales que MT.
b) Función Parada No Computable
Como hemos visto existen muchas funciones (infinitas) no computables por MT. El ejemplo más famoso es el de la función parada.Procedemos por reducción al absurdo. Esto es: Asumimos que existe una MT, MH, que computa H(n). Y mostramos que, si este fuera el caso, entonces podríamos construir una MT imposible, MI.La MT imposible se construiría como sigue, asumiendo que MH existe:
Cuando a MI se le da como input k, comienza utilizando el programa MH como subrutina para comprobar si la TM k para cuando se le da el input k. Es decir, la máquina imposible, MI utiliza MH para comprobar si la MT k para.
DEFINICIÓN DE MI
MI(I)=0 (MI NO se detiene) si MH(I)=1 (si MI recibe la respuesta ‘si’ (si lee un 1 después de aplicar MH al input), entonces MI no para.)LA CLAVE ESTÁ EN QUE EL INPUT QUE RECIBE LA MÁQUINA MH ES I, ES DECIR, EL NÚMERO QUE SE ASOCIA CON EL CONJUNTO DE INSTRUCCIONES CORRESPONDIENTE A LA MÁQUINA IMPOSIBLE I)
MI(I)=1 (MI PARA) si MH(I)=0. En otro caso MI para.
Ahora supongamos que MI es la i-ésima MT y considérese la cuestión de si MI para cuando se le da el input I.
Hay dos posibilidades: MI para (se detiene) al recibir el input I
MI(I)=1 sii MH(i)=0; Pero lo que hace MH es comportarse como la máquina I cuando recibe como input a la propia máquina I. Por lo que tenemos que MI para sii no para.
Por definición de la función parada, función que es implementada por la MT H, MH, esto significa que H(i)=1. Así pues, según la definición de MI, MI entra en un bucle infinito. MI no para al recibir el input i
Pero lo que hace MH es comportarse como la máquina I cuando recibe como input a la propia máquina I. Por lo que tenemos que MI no para sii para.
Por definición de la función parada, esto significa que H(i)=0. De la definición de MI, se sigue que MI parará dado el input i.Así pues, tenemos que MI para sii no para. Lo cual es imposible. Esto significa que MI no puede existir, así es que MH no puede existir. Así pues, la Función Parada no es computable.
Teorema de Incompletitud de Gödel
c) Formulación del Teorema de Gödel
A grandes rasgos, el primer teorema de Gödel afirma que dado un lenguaje L de la aritmética lo suficientemente rico, no existe una MT capaz de definir, o mejor dicho, decir (en términos de decibilidad) sobre todas las sentencias del lenguaje. Luego se predica la indecibilidad de L. Otra manera de postularlo es que ninguna axiomatización de la aritmética será a la vez completa y consistente.Una axiomatización no es más que un sistema de axiomas con el que se demuestran cosas acerca del lenguaje. Los axiomas son sentencias que suponemos verdaderas a priori.
Un ejemplo serían los axiomas de Peano. ∀x(0≠(x+1)) ∀x∀y (x+1=y+1→x=y) ∀x(x+0=0);∀x(x+0=x) ∀x∀y[(x+(y+1))=((x+y)+1)] ∀x(xx0=0)Cualquier axiomatización es válida siempre que sea computable por alguna MT. Una vez que tenemos un lenguaje válido podemos introducir la noción de demostrabilidad. Una sentencia S del Lenguaje L es demostrable siempre que existen un conjunto de sentencias del lenguaje tales que: Estas sentencias son o bien axiomas o bien inferencias de estos, y la última sentencia del conjunto sea S.
Diremos que una axiomatización es completa si se puede demostrar la verdad o falsedad de todas las sentencias del lenguaje por medio de las reglas de inferencia. De los axiomas se tiene que poder seguir toda sentencia o su negación.
A su vez, decimos que una axiomatización es consistente si es imposible deducir una contradicción de ese conjunto de reglas.
d) Programa de Hilbert
El programa de Hilbert se basaba en dos ideas. La primera, que el conjunto de la aritmética era decidible, esto es, que existía un conjunto de reglas o algoritmos capaz de establecer la verdad sobre un conjunto de axiomas. Para Hilbert que un conjunto de axiomas fuera consistente era condición suficiente para establecer la verdad de una estructura matemática. De esta forma no tendríamos más que aplicar esa regla a nuestros axiomas para saber sobre su verdad.Gödel probó que si una función es computable por una MT, luego esa sentencia también es deducible del conjunto estándar de las reglas de la aritmética. Cualquier problema resoluble por medio de un procedimiento algorítmico, es luego deducible por medio de las reglas (Axiomas) de la aritmética.
Gödel también probó que es imposible probar la consistencia de cualquier sistema de axiomas que sea tan fuerte como el de la aritmética. Luego las implicaciones de los dos teoremas de Gödel respecto a las hipótesis de Hilbert son claras. Ni existe un proceso para resolver todos los problemas, ni el conjunto de la aritmética es consistente.
Deja un comentario