Gödel y Turing (Parte 7)

(A la parte 6 - A la parte 8)

La máquina universal de Turing

Cada máquina de Turing queda caracterizada por el programa que rige su comportamiento. Es decir, dos máquinas de Turing son iguales si y solo si son iguales (símbolo a símbolo) sus respectivos programas. Utilizaremos esta definición para mostrar una manera de enumerar una por una todas las máquinas de Turing existentes.

Convengamos en adoptar el siguiente código, que transforma en números enteros a los símbolos que hemos usado para describir a las máquinas T:

1 = símbolo 0 (o casilla vacía)
2 = símbolo #
3 = letra D
4 = letra I
5 = letra S
6 = estado final de la máquina (q0), que indica el final del cálculo.
7 = estado inicial de la máquina (q1), en el que se encuentra al comenzar.
8 = estado 2 de la máquina (q2).
9 = estado 3 de la máquina (q3).
10 = estado 4 de la máquina (q4).
Etc.

Con esta convención, todo programa de una máquina de Turing puede transformarse en una sucesión finita de enteros positivos. Por ejemplo, el programa siguiente:

# + q1 -> 0Dq2
0 + q1 -> 0Iq1
# + q2 -> #Sq0
0 + q2 -> 0Dq2

se transforma en 1-3-8-1-4-7-2-5-6-1-3-8, que es simplemente la traducción de 0-D-q2-0-I-q1-#-S-q0-0-D-q2 (nótese que en esta traducción omitimos la columna de la izquierda).

Toda sucesión que sea la traducción del programa de una máquina T tendrá necesariamente las siguientes características:

a) Estará formada por una cantidad par de ternas de números naturales. Más precisamente, si la máquina tiene n estados, la sucesión tendrá 2n ternas.

b) El primer número de cada terna será 1 o 2.

c) El segundo número de cada terna será 3, 4 o 5.

d) Si la máquina tiene n estados, el tercer número de cada terna será mayor o igual que 6 y menor o igual que n + 6.

Recíprocamente, toda sucesión que cumpla las condiciones anteriores será la traducción de una máquina de Turing de n estados.

La traducción que hemos descripto nos da un método para enumerar una por una todas las máquinas T existentes. En primer lugar enumeramos las sucesiones correspondientes a todas las máquinas de un solo estado, ordenadas lexicográficamente (1). La lista de todas las máquinas de un estado comenzaría así:

1-3-6-1-3-6
1-3-6-1-3-7
1-3-6-1-4-6

Un simple razonamiento combinatorio nos permite deducir que existe un total de 144 máquinas de Turing de un estado.

A continuación de las máquinas de un estado enumeramos las máquinas de dos estados, luego las de tres estados y así sucesivamente. Si procedemos de esta manera, tarde o temprano, toda máquina T aparecerá en nuestra lista una y sólo una vez. Llamaremos T1 a la primera de las máquinas de la enumeración, T2 a la siguiente, etc.

Es claro que es posible escribir un algoritmo que, dados los números n y m, escriba la sucesión finita que describe a la máquina Tn y que además ejecute el cálculo que haría Tn si recibiera como entrada el número m. Este algoritmo, de acuerdo a la tesis de Turing, puede a su vez representarse mediante una máquina T.

Deducimos entonces que existe una máquina de Turing U (llamada máquina universal de Turing) que recibe como entrada dos números (n,m) y que imita el cálculo que haría Tn al recibir como entrada el número m. Esta máquina será esencial en la construcción de una función no recursiva.

Nota:

(1) En el orden lexicográfico u orden del diccionario las sucesiones se ordenan según la primera cifra, a igualdad de la primera cifra se ordenan según la segunda, a igualdad de las dos primeras se ordenan según la tercera y así sucesivamente. Por ejemplo 1-2-6 viene antes que 1-2-9, pero después de 1-1-7.

(A la parte 6 - A la parte 8)