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)

La paradoja del segundo número

Pensemos en el siguiente juego. Hay muchos participantes, cuantos más mejor. Cada uno anota en secreto un número entero mayor que cero (es decir 1, 2, 3, 4,...) y luego todos muestran a la vez sus números. Gana el que haya anotado el segundo menor número no repetido.

Por ejemplo, si los números anotados son 4-5-5-5-6-6-10-12-19-19 gana el jugador que anotó el 10. (Si todos los números se repiten o sólo uno no se repite, no gana nadie).

¿Cuál es la mejor jugada posible? Veamos:

No sirve jugar el 1, pues éste número no puede ganar (nunca será el sgundo menor). El 1 queda descartado como jugada posible. Si el 1 queda descartado entonces el 2 entonces nunca ganará. El 2 queda entonces descartado. El 3 nunca ganará, pues para ello alguien debería jugar el 1 o el 2. Luego el 3 queda también descartado. De la misma manera se descartan todos los demás números. La única jugada "racional" consiste entonces en negarse a jugar.

Otro de veraces y mentirosos

A, B y C son, o bien veraces o bien mentirosos. Cada uno sabe la condición de todos los demás. Le hablan a un cuarto personaje:

C dice: "A es mentiroso o B es veraz (o ambas cosas)".
B dice: "A y C son ambos mentirosos".
A dice: "Los datos de este problema son insuficientes para resolverlo".

¿Quién es veraz y quién es mentiroso?

Problemita de probabilidad

De un bolillero que contiene 100 bolillas numeradas del 1 al 100 se extraerán tres bolillas con reposición. Un jugador anotó en un papel tres números diferentes entre 1 y 100. Cada vez que del bolillero salga uno de sus números, el jugador lo tachará de su lista (si un número saliera dos o tres veces, el jugador sólo lo tachará una vez).

0. ¿Cuál es la probabilidad de que el jugador no tache número alguno de su lista?
1. ¿Cuál es la probabilidad de que tache exactamente un número?
2. ¿Cuál es la probabilidad de que tache exactamente dos números?
3. ál es la probabilidad de que tache los tres números?

Gödel y Turing (Parte 6)

(A la parte 5 - A la parte 7)

Funciones recursivas parciales

Toda máquina de Turing Z define de manera natural una función F cuyo dominio (1) está formado por todos los enteros positivos n tales que #n es una entrada válida para Z, es decir, todos los números que, cargados en Z dan (después de una cantidad finita de tiempo) una salida que representa un entero positivo. El número F(n) se define entonces del siguiente modo: F(n) = m si y sólo si #m es la salida que corresponde a la entrada #n.

Definición: Diremos que una función G es recursiva parcial si existe una máquina de Turing Z tal que la función F por ella definida coincide exactamente con la función G (es decir, si F y G tienen el mismo dominio y además para cada número n de ese dominio vale que F(n) = G(n)). Cuando el dominio de G está formado por todos los enteros positivos, decimos simplemente que la función es recursiva.

Expresado en términos más simples, una función G es recursiva parcial si existe un algoritmo (o un programa de computadora) que permite calcular G(n) para cualquier número n de su dominio y que, cuando intenta calcular G(n) para un n que no pertenezca al dominio, o bien entra en un ciclo de cómputo infinito o bien da una respuesta ininteligible.

Como ya hemos visto en la Parte 4, la función G(n) = n – 1 (cuyo dominio está formado por los enteros mayores que 1) es recursiva parcial. Para dar otro ejemplo, veamos que la función H(n) = log n, cuyo dominio es el conjunto de las potencias de 10, es también recursiva parcial. Gracias a la Tesis de Turing no será necesario mostrar explícitamente una máquina T que calcule H(n), alcanzará con mostrar cualquier algoritmo que haga ese cálculo, la Tesis nos garantiza que dicho algoritmo podrá traducirse a una máquina T. En este caso un algoritmo puede describirse de la siguiente manera:

1) Entrada: n.
2) Defina k = 1.
3) Calcule 10 elevado a la k y compárelo con n, si son iguales deténgase, en caso contrario vaya al paso siguiente.
4) Sume 1 al valor de k y vuelva al paso 3).
5) Salida: k.

En realidad toda función que esté descripta mediante una o varias fórmulas basadas en las operaciones usuales (suma, resta, producto, cociente, radicación, etc.) será una función recursiva parcial. Casi cualquier función que Ud., lector, pueda llegar imaginar será, casi con certeza, una función recursiva parcial.

Surge entonces la pregunta siguiente: ¿existen funciones que no sean recursivas parciales? Es decir, ¿existen funciones tales que no haya algoritmos capaces de calcularlas? Curiosamente la respuesta es afirmativa.

Una manera indirecta de demostrar la existencia de infinitas funciones no recursivas parciales es la siguiente. Puede probarse con no demasiada dificultad que el conjunto de todas las máquinas de Turing es numerable, mientras que el conjunto de todas las funciones del conjunto de los números naturales en sí mismo es no numerable. Por lo tanto deben existir necesariamente funciones no calculables por máquina de Turing alguna. Es decir, existen funciones que no pueden ser calculadas algorítmicamente (no pueden ser “comprendidas” por un programa de computadora).

En la parte 7 iniciaremos el proceso que nos permitirá mostrar explícitamente un ejemplo concreto de función no recursiva.

Nota:

(1) A los efectos de estas notas, el dominio de F es el conjunto de todos los enteros positivos n para los cuales F(n) puede calcularse y da como resultado un entero positivo. Por ejemplo, para F(n) = n/2 el dominio está formado por todos los números pares.

(A la parte 5 - A la parte 7)

Triángulos enteros (II)

Si trazamos todas las medianas de un triángulo éste quedará dividido en seis triángulos más pequeños (véase aquí un dibujo de la situación). ¿Es posible lograr que los lados de esos triángulos pequeños tengan, todos ellos, medidas enteras en centímetros? La verdad es que no lo sé. El primer problema consiste, entonces, en hallar una respuesta a esta pregunta.

¿Es posible lograr que los lados de esos triángulos más pequeños tengan, todos ellos, medidas que, en centímetros, sean todas enteras o la raíz cuadrada de un entero? La respuesta es que sí, el segundo problema consiste entonces en hallar el triángulo más pequeño para el cual se da esta situación (más pequeño en el sentido de que su lado mayor sea lo más corto posible).

Triángulos enteros

Si trazamos todas las alturas de un triángulo acutángulo éste quedará dividido en seis triángulos rectángulos (véase aquí un dibujo de la situación). ¿Es posible lograr que los lados de esos triángulos rectángulos tengan, todos ellos, medidas enteras en centímetros? La respuesta es que sí, el problema consiste entonces en hallar el triángulo más pequeño para el cual se da esta situación (más pequeño en el sentido de que su lado mayor sea lo más corto posible).