Número de descripción

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 los llama "números de Gödel" en la literatura. Dada una 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 ₁ , ... q _R , con un alfabeto de cinta con símbolos s ₁ , ... s _m , con el espacio en blanco denotado por s ₀ , y transiciones que dan el estado actual, el símbolo actual y las acciones realizadas (que podrían ser sobrescribir el símbolo de cinta actual y mover el cabezal de la cinta a la izquierda o a 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 estaría codificada como entrada de la siguiente manera:

1. El estado q _i está codificado por la letra 'D' seguida de la letra 'A' repetida i veces (una codificación unaria )
2. El símbolo de cinta s _j está codificado por la letra 'D' seguida de la letra 'C' repetida j veces
3. Las transiciones se codifican proporcionando el estado, el símbolo de entrada, el símbolo a escribir en la cinta, la dirección a seguir (expresada por las letras 'L', 'R' o 'N', para izquierda, derecha o ningún movimiento) y el siguiente estado al que ingresar, con estados y símbolos codificados como se indicó anteriormente.

La entrada del UTM consiste entonces en las transiciones separadas por punto y coma, por lo que su alfabeto de entrada consiste en 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:

1. Estado: q ₁ , símbolo de entrada: en blanco, acción: imprimir 1, mover a la derecha, siguiente estado: q ₂
2. Estado: q ₂ , símbolo de entrada: en blanco, acción: imprimir 0, mover a la derecha, siguiente estado: q ₁

Si el espacio en blanco es s ₀ , '0' es s ₁ y '1' es s ₂ , la máquina quedaría codificada por el UTM como:

DADDCCRDAA;DAADDCRDA;

Pero entonces, si sustituyéramos 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: éste 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 arriba tendría entonces el número de descripción 313322531173113325317. Existe un proceso análogo para cualquier otro tipo de máquina de Turing universal. Normalmente no es necesario calcular realmente un número de descripción de esta manera: el punto es que cada número natural puede interpretarse como el código para, como máximo, una máquina de Turing, aunque muchos números naturales pueden no ser el código para ninguna máquina de Turing (o, para decirlo de otra manera, representan máquinas de Turing que no tienen estados). El hecho de que tal número siempre exista para cualquier máquina de Turing es generalmente lo importante.

Los números de descripción desempeñan 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 , seguramente debe haber muchas funciones que no puedan ser calculadas por las máquinas de Turing.

Al hacer uso de una técnica similar al argumento diagonal de Cantor , es posible exhibir una función incomputable tal, 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 universal de Turing dado un número de descripción e y una entrada x, devolviendo 0 si e no es el número de descripción de una máquina de Turing válida. Ahora, supongamos que hubiera algún algoritmo capaz de resolver el problema de detención, es decir, una máquina de Turing TEST(e) 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 funcione para siempre. Al combinar 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. A partir de esta definición, δ se define para cada entrada y naturalmente debe ser totalmente recursiva. Dado que δ se construye a partir de lo que hemos supuesto que son máquinas de Turing, entonces también debe tener un número de descripción, llamémoslo e. Por lo tanto, podemos introducir el número de descripción e en la UTM nuevamente y, por definición, δ(k) = U(e, k), por lo que δ(e) = U(e, e). Pero como TEST(e) es 1, según nuestra otra definición, δ(e) = U(e, e) + 1, lo que conduce 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.

• Número de Gödel
• Máquina universal de Turing
• Número de la iglesia
• Problema de parada

• John Hopcroft y Jeffrey D. Ullman (1979). Introducción a la teoría de autómatas, lenguajes y computación (1.ª ed.). Addison-Wesley. ISBN 0-201-44124-1.(El libro de Cenicienta)
• Turing, AM "Sobre números computables, con una aplicación al Entscheidungsproblem ", Proc. Roy. Soc. Londres, 2(42), 1936, págs. 230–265.