Los números de descripción son números que surgen en la teoría de las máquinas de Turing . Son muy similares a los números de Gödel y, ocasionalmente, también se les llama "números de Gödel" en la literatura. Dada alguna máquina de Turing universal , a cada máquina de Turing se le puede asignar un número, dada su codificación en esa máquina. Este es el número de descripción de la máquina. Estos números desempeñan un papel clave en la prueba de Alan Turing de la indecidibilidad del problema de la detención y también son muy útiles para razonar sobre las máquinas de Turing.
Digamos que tenemos una máquina de Turing M con estados q 1 ,... q R , con un alfabeto en cinta con símbolos s 1 ,... s m , con el espacio en blanco indicado por s 0 , y transiciones que dan el estado actual, el símbolo actual y las acciones realizadas (que podrían ser sobrescribir el símbolo de la cinta actual y mover el cabezal de la cinta hacia la izquierda o hacia la derecha, o tal vez no moverlo en absoluto) y el siguiente estado. Según la máquina universal original descrita por Alan Turing, esta máquina se codificaría como entrada de la siguiente manera:
Por lo tanto, la entrada del UTM consta de transiciones separadas por punto y coma, por lo que su alfabeto de entrada consta de siete símbolos, 'D', 'A', 'C', 'L', 'R', 'N' y ';' . Por ejemplo, para una máquina de Turing muy simple que alterna la impresión de 0 y 1 en su cinta para siempre:
Dejando que el espacio en blanco sea s 0 , '0' sea s 1 y '1' sea s 2 , la máquina sería codificada por el UTM como:
DADDCCRDAA;DAADDCRDA;
Pero entonces, si reemplazamos cada uno de los siete símbolos 'A' por 1, 'C' por 2, 'D' por 3, 'L' por 4, 'R' por 5, 'N' por 6 y '; ' con 7, tendríamos una codificación de la máquina de Turing como número natural: este es el número de descripción de esa máquina de Turing bajo la máquina universal de Turing. La máquina de Turing simple descrita anteriormente tendría, por tanto, el número de descripción 313322531173113325317. Existe un proceso análogo para cualquier otro tipo de máquina de Turing universal. Generalmente no es necesario calcular un número de descripción de esta manera: la cuestión es que cada número natural puede interpretarse como el código de como máximo una máquina de Turing, aunque muchos números naturales pueden no ser el código de ninguna máquina de Turing (o dicho de otro modo, representan máquinas de Turing que no tienen estados). El hecho de que ese número siempre exista para cualquier máquina de Turing es generalmente lo importante.
Los números de descripción juegan un papel clave en muchas pruebas de indecidibilidad, como la prueba de que el problema de detención es indecidible . En primer lugar, la existencia de esta correspondencia directa entre los números naturales y las máquinas de Turing muestra que el conjunto de todas las máquinas de Turing es numerable , y dado que el conjunto de todas las funciones parciales es incontablemente infinito , ciertamente debe haber muchas funciones que no se pueden calcular. por las máquinas de Turing.
Haciendo uso de una técnica similar al argumento diagonal de Cantor , es posible exhibir una función tan incomputable, por ejemplo, que el problema de detención en particular sea indecidible. Primero, denotemos por U(e, x) la acción de la máquina de Turing universal dado un número de descripción e e ingresemos x, devolviendo 0 si e no es el número de descripción de una máquina de Turing válida. Ahora, suponiendo que hubiera algún algoritmo capaz de resolver el problema de la detención, es decir, una TEST(e) de la máquina de Turing que, dado el número de descripción de alguna máquina de Turing, devolvería 1 si la máquina de Turing se detiene en cada entrada, o 0 si hay algunas entradas que harían que se ejecutara para siempre. Combinando las salidas de estas máquinas, debería ser posible construir otra máquina δ(k) que devuelva U(k, k) + 1 si TEST(k) es 1 y 0 si TEST(k) es 0. De esta definición δ se define para cada entrada y, naturalmente, debe ser totalmente recursivo. Dado que δ también se construye a partir de lo que hemos asumido que son máquinas de Turing, entonces también debe tener un número de descripción, llámelo e. Entonces, podemos alimentar nuevamente el número de descripción e al UTM y, por definición, δ(k) = U(e, k), entonces δ(e) = U(e, e). Pero como TEST(e) es 1, según nuestra otra definición, δ(e) = U(e, e) + 1, lo que lleva a una contradicción. Por lo tanto, TEST(e) no puede existir y de esta manera hemos resuelto el problema de la detención como indecidible.