Siguiente: Presentación del Problema de Un nivel arriba: Irresolubilidad Anterior: Teorema de Rice

Problema de la correspondencia de Post

Hemos visto que el problema de la parada en máquinas de Turing no es resoluble por máquinas de Turing. Así pues, con la terminología y la notación introducidas en la sección 1.6.2, tenemos que no es posible construir un procedimiento recursivo que decida si acaso una descripción instantánea inicial, $\mbox{\rm DI}_0$, ha de transformarse en una DI final.