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 en ocasiones 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 juegan 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 de cinta con símbolos s 1 , ... s m , con el espacio en blanco denotado por s 0 , y las transiciones que dan el estado actual, 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. Bajo la máquina universal original descrita por Alan Turing, esta máquina se codificaría como entrada de la siguiente manera:
Por tanto, la entrada de UTM consta de las transiciones separadas por punto y coma, por lo que su alfabeto de entrada consta de los 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:
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 '; ' por 7, tendríamos una codificación de la máquina de Turing como un 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. Por lo general, no es necesario calcular realmente un número de descripción de esta manera: el punto es que cada número naturalpuede interpretarse como el código de una máquina de Turing como máximo, aunque muchos números naturales pueden no ser el código de ninguna máquina de Turing (o, para decirlo de otra manera, 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 la 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.