Máquinas de Turing
Fecha de entrega:
En ésta tarea las máquinas de Turing usarán los símbolos \(\left\{\ast,0,1 \right\}\). En cada problema especificaremos si los números se representarán en unario (5 = \(\cdots \ast \ast 1 1 1 1 1 \ast \ast \cdots\)) o en binario (5 = \(\cdots \ast \ast 1 0 1 \ast \ast \cdots\)). La cabeza siempre supondremos que empieza en el 0 o 1 de más a la izquierda.
Para esta tarea está altamente recomendado usar un simulador de máquinas de Turing. En particular, no sean malos con el ayudante: ¡prueben sus máquinas en el simulador antes de entregar la tarea! Recuerden la famosa cita de Donald Knuth (en traducción libre1): «Ese programa puede contener errores: solo he demostrado que es correcto, no lo he ejectuado» 😛.
Programación
En cada caso explica cómo funciona tu máquina.
- Escribe una máquina de Turing que calcule la función \(n \mapsto 2n\) en (a) unario, (b) binario.
- Escribe una máquina de Turing que calcule la función \(n \mapsto (n,n)\). Usaremos notación binaria para los números y para representar un par ordenado en la cinta de la máquina de Turing, ponemos el primer número, un asterisco y luego el segundo número; así que la máquina debe convertir \(\cdots \ast \ast 1 0 1 \ast \ast \cdots\) en \(\cdots \ast \ast 1 0 1 \ast 1 0 1 \ast \ast \cdots\).
- Escribe una máquina de Turing que calcule igualdad de números en notación unaria, es decir, dada una cinta que tiene un número \(m\), un asterisco, y otro número \(n\), la máquina debe dejar solo un dígito sobre la cinta, 0 si \(m \neq n\) y 1 si \(m = n\).
¿Qué hace esta máquina?
Considera la máquina de Turing con esta tabla de instrucciones:
q s s’ q’ d q s s’ q’ d 0 0 ∗ 0 → 3 0 ∗ 1 → 0 1 ∗ 1 → 3 1 ∗ 2 → 0 ∗ 1 F 3 ∗ 0 F 1 0 ∗ 2 → 4 0 ∗ 3 → 1 1 ∗ 3 → 4 1 ∗ 4 → 1 ∗ 0 F 4 ∗ 0 F 2 0 ∗ 4 → 2 1 ∗ 0 → 2 ∗ 0 F (Cuando la máquina pasa al estado
F, no hay instrucciones aplicables y se detiene).(a) Encuentra un número \(n\) tal que si empezamos la máquina con \(n\) escrito en binario, y en estado incial 0, la máquina termina con un 1 en la cinta.
(b) ¿Qué hace la máquina?
La original dice: «Beware of bugs in the above code; I have only proved it correct, not tried it». Es de una carta que le escribió Knuth a Peter van Emde Boas.