Siguiente: Teorema de Rice Un nivel arriba: COMPUTABILIDAD Y COMPLEJIDAD Anterior: Segunda lista de programas

Irresolubilidad

En la sección 4.2 vimos que no existe una función recursiva que permita decidir, para una función recursiva f cualquiera y una instancia $\mbox{\bf x}$ arbitraria, si acaso $\mbox{\bf x}$ está o no en el dominio de f. Dada la equivalencia entre funciones recursivas y máquinas de Turing, tenemos que el resultado de ``inexistencia'' anterior se convierte en que no hay máquina de Turing que decida, para una máquina de Turing cualquiera si acaso ha de detenerse a partir de una instancia inicial cualquiera. El ``problema de la parada'' para máquinas de Turing es pues irresoluble mediante máquinas de Turing. En resumen, existen problemas irresolubles que se pueden plantear en el lenguaje de la teoría de la computabilidad. En el presente capítulo presentaremos diversos problemas que, al igual que el problema de la parada, no son resolubles mediante funciones computables. Inicialmente, presentamos el teorema de Rice que indica que no hay manera alguna de reconocer procedimentalmente clases ``interesantes'' de funciones. Veremos luego otro problema clásico irresoluble, el de la ``correspondencia de Post''. A partir de éste, veremos que muchos problemas de decisión, planteados para gramáticas libres de contexto, vale decir, para gramáticas en los primeros niveles de la Jerarquía de Chomsky, son también irresolubles. Finalmente, presentamos el equivalente a la noción de irresolubilidad en la Lógica Matemática. En ésta, una demostración consiste, al igual que una computación, de una secuencia de transformaciones para derivar teoremas. Un enunciado indemostrable es entonces uno inaccesible mediante las reglas de deducción de la teoría. Veremos un ejemplo de un enunciado indemostrable en la Aritmética de Peano.

Siguiente: Teorema de Rice Un nivel arriba: COMPUTABILIDAD Y COMPLEJIDAD Anterior: Segunda lista de programas