385 lines
12 KiB
Plaintext
385 lines
12 KiB
Plaintext
# máquinas de turing
|
|
lang=es
|
|
compendio de descripciones de máquinas de turing para implementarse de múltiples formas.
|
|
|
|
ideales para bailarlas en modalidad {d-turing}, o para simularlas con {jarotsim} o {turingsim}.
|
|
|
|
# la primera
|
|
|
|
esta máquina genera la secuencia 0 1 0 1 0 1 de manera infinita.
|
|
|
|
estos son los componentes adaptados de la primera máquina de este tipo que describe turing en su artículo.
|
|
|
|
=> https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf on computable numbers, with an application to the entscheidungsproblem - alan turing 1936
|
|
|
|
|
|
## alfabeto de símbolos posibles en la cinta
|
|
|
|
tres símbolos posibles: 0, 1, y vacío
|
|
|
|
## conjunto de estados posibles
|
|
|
|
cuatro estados posibles: a, b, c, d
|
|
|
|
## estado inicial
|
|
|
|
la máquina empieza en el estado a.
|
|
|
|
la cinta puede estar "vacía".
|
|
|
|
## tabla de reglas
|
|
|
|
dado un símbolo encontrado en la cinta, y un estado actual: ¿por cuál símbolo hay que reemplazarlo, a qué dirección hay que mover la cabeza, y cuál ha de ser el nuevo estado?
|
|
|
|
+ <table>
|
|
+ <tr>
|
|
+ <th>estado actual</th><th>símbolo leído</th><th>nuevo símbolo</th><th>dirección</th><th>nuevo estado</th>
|
|
+ </tr>
|
|
+ <tr><td>a</td><td>cualquiera</td><td>0</td><td>derecha</td><td>b</td>
|
|
+ <tr><td>b</td><td>cualquiera</td><td>el que estaba</td><td>derecha</td><td>c</td>
|
|
+ <tr><td>c</td><td>cualquiera</td><td>1</td><td>derecha</td><td>d</td>
|
|
+ <tr><td>d</td><td>cualquiera</td><td>el que estaba</td><td>derecha</td><td>a</td>
|
|
+ </table>
|
|
|
|
& * si el estado es 'a', sin importar el símbolo leído, escribe 0, mueve a la derecha, y cambia a estado 'b'
|
|
& * si el estado es 'b', sin importar el símbolo leído, deja ese símbolo, mueve a la derecha, y cambia a estado 'c'
|
|
& * si el estado es 'c', sin importar el símbolo leído, escribe 1, mueve a la derecha, y cambia a estado 'd'
|
|
& * si el estado es 'd', sin importar el símbolo leído, deja ese símbolo, mueve a la derecha, y cambia a estado 'a'
|
|
|
|
=> https://www.wolframalpha.com/input/?i=Turing+machine+rule+%7B%7B1%2C_%7D+-%3E+%7B2%2C0%2CR%7D%2C+%7B2%2C0%7D+-%3E+%7B3%2C0%2CR%7D%2C+%7B2%2C1%7D+-%3E+%7B3%2C1%2CR%7D%2C+%7B3%2C_%7D+-%3E+%7B4%2C1%2CR%7D%2C+%7B4%2C0%7D+-%3E+%7B1%2C0%2CR%7D%2C+%7B4%2C1%7D+-%3E+%7B1%2C1%2CR%7D%7D simulación en wolfram alpha
|
|
|
|
# calculadora de paridad
|
|
|
|
esta máquina cuenta la cantidad de "1"s en una secuencia binaria, y termina escribiendo "1" si la cantidad es impar, o "0" si es par.
|
|
|
|
similar al proceso descrito en {par y danza}, pero en máquina de turing.
|
|
|
|
adaptado de la descripción de minsky (computation: finite and infinite machines - marvin minsky 1967, pág 120)
|
|
|
|
|
|
## alfabeto de símbolos posibles en la cinta
|
|
|
|
tres símbolos posibles: 0, 1, y B
|
|
|
|
## conjunto de estados posibles
|
|
|
|
dos estados posibles: a, b
|
|
|
|
## estado inicial
|
|
|
|
la máquina empieza en el estado a.
|
|
|
|
la cinta ha de contener la secuencia binaria, terminada con B. por ejemplo:
|
|
|
|
```
|
|
101101B
|
|
```
|
|
|
|
la cabeza ha de empezar en el 1 que está más a la izquierda.
|
|
|
|
## tabla de reglas
|
|
|
|
dado un símbolo encontrado en la cinta, y un estado actual: ¿por cuál símbolo hay que reemplazarlo, a qué dirección hay que mover la cabeza, y cuál ha de ser el nuevo estado?
|
|
|
|
+ <table>
|
|
+ <tr>
|
|
+ <th>estado actual</th><th>símbolo leído</th><th>nuevo símbolo</th><th>dirección</th><th>nuevo estado</th>
|
|
+ </tr>
|
|
+ <tr><td>a</td><td>0</td><td>0</td><td>derecha</td><td>a</td>
|
|
+ <tr><td>a</td><td>1</td><td>0</td><td>derecha</td><td>b</td>
|
|
+ <tr><td>a</td><td>B</td><td>0</td><td>-</td><td>FIN</td>
|
|
+ <tr><td>b</td><td>0</td><td>0</td><td>derecha</td><td>b</td>
|
|
+ <tr><td>b</td><td>1</td><td>0</td><td>derecha</td><td>a</td>
|
|
+ <tr><td>b</td><td>B</td><td>1</td><td>-</td><td>FIN</td>
|
|
+ </table>
|
|
|
|
& * si el estado es 'a' y el símbolo leído es 0, deja ese símbolo, mueve la cabeza a la derecha, y quédate en el estado 'a'
|
|
& * si el estado es 'a' y el símbolo leído es 1, escribe 0, mueve la cabeza a la derecha, y cambia al estado 'b'
|
|
& * si el estado es 'a' y el símbolo leído es B, escribe 0, y termina la operación
|
|
& * si el estado es 'b' y el símbolo leído es 0, deja ese símbolo, mueve la cabeza a la derecha, y quédate en el estado 'b'
|
|
& * si el estado es 'b' y el símbolo leído es 1, escribe 0, mueve la cabeza a la derecha, y cambia al estado 'a'
|
|
& * si el estado es 'b' y el símbolo leído es B, escribe 1, y termina la operación
|
|
|
|
## archivo para turingsim
|
|
|
|
este archivo se puede utilizar con {turingsim}
|
|
|
|
```
|
|
a
|
|
101101B
|
|
0
|
|
6
|
|
a0a00
|
|
a1b00
|
|
aBH00
|
|
b0b00
|
|
b1a00
|
|
bBH10
|
|
80
|
|
```
|
|
|
|
en este caso el estado final indica paridad par:
|
|
|
|
```
|
|
step 7
|
|
H
|
|
0000000
|
|
halted
|
|
```
|
|
|
|
cambiando la cinta inicial a por ejemplo 101100B, con paridad impar, el resultado es:
|
|
|
|
```
|
|
step 7
|
|
H
|
|
0000001
|
|
halted
|
|
```
|
|
|
|
# comprobador de paréntesis
|
|
|
|
esta máquina revisa una secuencia con pares de paréntesis, y al finalizar escribe 1 si es una secuencia bien formada, o 0 si no.
|
|
|
|
una secuencia bien formada de paréntesis implica que a cada paréntesis izquierdo le corresponde uno derecho.
|
|
|
|
adaptado de la descripción de minsky (computation: finite and infinite machines - marvin minsky 1967, pág 122)
|
|
|
|
=> ./img/dibujo_d-turing_parentesis.png dibujo de tres personas emitiendo un símbolo cada una, alrededor de una cinta de símbolos
|
|
|
|
## alfabeto de símbolos posibles en la cinta
|
|
|
|
cuatro símbolos posibles: (, ), A, X
|
|
|
|
## conjunto de estados posibles
|
|
|
|
tres estados posibles: a, b, c
|
|
|
|
## estado inicial
|
|
|
|
la máquina empieza en el estado a.
|
|
|
|
la cinta ha de contener la secuencia de paréntesis contenida entre un par de A. por ejemplo:
|
|
|
|
```
|
|
A((()())())A
|
|
```
|
|
|
|
la cabeza ha de empezar en el primer paréntesis a la izquierda.
|
|
|
|
## tabla de reglas
|
|
|
|
dado un símbolo encontrado en la cinta, y un estado actual: ¿por cuál símbolo hay que reemplazarlo, a qué dirección hay que mover la cabeza, y cuál ha de ser el nuevo estado?
|
|
|
|
+ <table>
|
|
+ <tr>
|
|
+ <th>estado actual</th><th>símbolo leído</th><th>nuevo símbolo</th><th>dirección</th><th>nuevo estado</th>
|
|
+ </tr>
|
|
+ <tr><td>a</td><td>)</td><td>X</td><td>izquierda</td><td>b</td>
|
|
+ <tr><td>a</td><td>(</td><td>(</td><td>derecha</td><td>a</td>
|
|
+ <tr><td>a</td><td>A</td><td>A</td><td>izquierda</td><td>c</td>
|
|
+ <tr><td>a</td><td>X</td><td>X</td><td>derecha</td><td>a</td>
|
|
+ <tr><td>b</td><td>)</td><td>)</td><td>izquierda</td><td>b</td>
|
|
+ <tr><td>b</td><td>(</td><td>X</td><td>derecha</td><td>a</td>
|
|
+ <tr><td>b</td><td>A</td><td>0</td><td>-</td><td>FIN</td>
|
|
+ <tr><td>b</td><td>X</td><td>X</td><td>izquierda</td><td>b</td>
|
|
+ <tr><td>c</td><td>)</td><td>-</td><td>-</td><td>-</td>
|
|
+ <tr><td>c</td><td>(</td><td>0</td><td>-</td><td>FIN</td>
|
|
+ <tr><td>c</td><td>A</td><td>1</td><td>-</td><td>FIN</td>
|
|
+ <tr><td>c</td><td>X</td><td>X</td><td>izquierda</td><td>c</td>
|
|
+ </table>
|
|
|
|
& * si el estado es 'a' y el símbolo leído es ), reemplaza por X, mueve la cabeza a la izquierda, y cambia al estado 'b'
|
|
& * si el estado es 'a' y el símbolo leído es (, deja (, mueve la cabeza a la derecha, y mantén el estado 'a'
|
|
& * si el estado es 'a' y el símbolo leído es A, deja A, mueve la cabeza a la izquierda, y cambia al estado 'c'
|
|
& * si el estado es 'a' y el símbolo leído es X, deja X, mueve la cabeza a la derecha, y mantén el estado 'a'
|
|
& * si el estado es 'b' y el símbolo leído es ), deja ), mueve la cabeza a la izquierda, y mantén el estado 'b'
|
|
& * si el estado es 'b' y el símbolo leído es (, reemplaza por X, mueve la cabeza a la derecha, y cambia al estado 'a'
|
|
& * si el estado es 'b' y el símbolo leído es A, reemplaza por 0, y finaliza
|
|
& * si el estado es 'b' y el símbolo leído es X, deja X, mueve la cabeza a la izquierda, y mantén el estado 'b'
|
|
& * si el estado es 'c' y el símbolo leído es ), hay algún error pues no debería suceder
|
|
& * si el estado es 'c' y el símbolo leído es (, reemplaza por 0, y finaliza
|
|
& * si el estado es 'c' y el símbolo leído es A, reemplaza por 1, y finaliza
|
|
& * si el estado es 'c' y el símbolo leído es X, deja X, mueve la cabeza a la izquierda, y mantén el estado 'c'
|
|
|
|
|
|
=> ./img/dibujo_tabla_d-turing_parentesis.png dibujo que representa la tabla de arriba, pero con símbolos estilizados
|
|
|
|
## archivo para turingsim
|
|
|
|
el siguiente archivo se puede usar con {turingsim} para ver los pasos de la máquina. nota la correspondencia entre la tabla y la lista de reglas.
|
|
|
|
```
|
|
a
|
|
A((()())())A
|
|
1
|
|
11
|
|
a)bX1
|
|
a(a(0
|
|
aAcA1
|
|
aXaX0
|
|
b)b)1
|
|
b(aX0
|
|
bAH00
|
|
bXbX1
|
|
c(H00
|
|
cAH10
|
|
cXcX1
|
|
80
|
|
```
|
|
|
|
# contador
|
|
|
|
esta máquina escribe "1"s en la cinta en una dirección, hasta encontrar un "1" en la cinta (o por siempre, si no es así)
|
|
|
|
## alfabeto de símbolos posibles en la cinta
|
|
|
|
dos símbolos posibles: 0 y 1
|
|
|
|
## conjunto de estados posibles
|
|
|
|
un estado: a
|
|
|
|
## estado inicial
|
|
|
|
la máquina empieza en el estado a.
|
|
|
|
la cinta ha de empezar vacía (llena de "0"s) o con algún "1" en su extremo superior
|
|
|
|
```
|
|
0000001
|
|
```
|
|
|
|
la cabeza ha de empezar en alguno de los "0"s a la izquierda del "1"
|
|
|
|
## tabla de reglas
|
|
|
|
dado un símbolo encontrado en la cinta, y un estado actual: ¿por cuál símbolo hay que reemplazarlo, a qué dirección hay que mover la cabeza, y cuál ha de ser el nuevo estado?
|
|
|
|
+ <table>
|
|
+ <tr>
|
|
+ <th>estado actual</th><th>símbolo leído</th><th>nuevo símbolo</th><th>dirección</th><th>nuevo estado</th>
|
|
+ </tr>
|
|
+ <tr><td>a</td><td>0</td><td>1</td><td>derecha</td><td>a</td>
|
|
+ <tr><td>a</td><td>1</td><td>1</td><td>-</td><td>FIN</td>
|
|
+ </table>
|
|
|
|
& * si el estado es 'a' y el símbolo leído es 0, escribe 1, mueve la cabeza a la derecha, y quédate en el estado 'a'
|
|
& * si el estado es 'a' y el símbolo leído es 1, escribe 1, y termina la operación
|
|
|
|
la condición de finalización puede omitirse: cuando la máquina no encuentra una entrada en la tabla, que corresponda a la combinación estado + símbolo, se detiene.
|
|
|
|
## quintupla binaria
|
|
|
|
como solo hay un estado, podemos representarlo con 1 bit con valor 0.
|
|
|
|
los dos símbolos ya son las dos opciones de 1 bit, 0 o 1.
|
|
|
|
las dos direcciones posibles también son las dos opciones de un bit, 0 para derecha y 1 para izquierda.
|
|
|
|
esta máquina puede escribirse entonces como quintupla binaria, en formato: estado actual, símbolo actual, estado nuevo, símbolo nuevo, dirección:
|
|
|
|
```
|
|
00 010
|
|
```
|
|
|
|
esta quintupla puede usarse como parte de la cinta de la máquina universal bailable {mub}
|
|
|
|
## archivos para turingsim
|
|
|
|
estos archivos se pueden usar con {turingsim} para simular su comportamiento.
|
|
|
|
esta es la versión usando el nombre del estado 'a':
|
|
|
|
```
|
|
a
|
|
0000001
|
|
0
|
|
2
|
|
a0a10
|
|
a1H10
|
|
80
|
|
```
|
|
|
|
y así usando '0' para quedarnos con una quintupla en formato binario
|
|
|
|
```
|
|
0
|
|
0000001
|
|
0
|
|
1
|
|
00010
|
|
80
|
|
```
|
|
|
|
# contador alternado
|
|
|
|
esta máquina escribe una secuencia de "10" en la cinta en una dirección, hasta encontrar un "1" en la cinta (o por siempre, si no es así)
|
|
|
|
## alfabeto de símbolos posibles en la cinta
|
|
|
|
dos símbolos posibles: 0 y 1
|
|
|
|
## conjunto de estados posibles
|
|
|
|
dos estados: a, b
|
|
|
|
## estado inicial
|
|
|
|
la máquina empieza en el estado a.
|
|
|
|
la cinta ha de empezar vacía (llena de "0"s) o con algún "1" en su extremo superior
|
|
|
|
```
|
|
0000001
|
|
```
|
|
|
|
la cabeza ha de empezar en alguno de los "0"s a la izquierda del "1"
|
|
|
|
## tabla de reglas
|
|
|
|
dado un símbolo encontrado en la cinta, y un estado actual: ¿por cuál símbolo hay que reemplazarlo, a qué dirección hay que mover la cabeza, y cuál ha de ser el nuevo estado?
|
|
|
|
+ <table>
|
|
+ <tr>
|
|
+ <th>estado actual</th><th>símbolo leído</th><th>nuevo símbolo</th><th>dirección</th><th>nuevo estado</th>
|
|
+ </tr>
|
|
+ <tr><td>a</td><td>0</td><td>1</td><td>derecha</td><td>b</td>
|
|
+ <tr><td>b</td><td>0</td><td>0</td><td>derecha</td><td>a</td>
|
|
+ </table>
|
|
|
|
& * si el estado es 'a' y el símbolo leído es 0, escribe 1, mueve la cabeza a la derecha, y cambia al estado 'b'
|
|
& * si el estado es 'b' y el símbolo leído es 0, escribe 0, mueve la cabeza a la derecha, y cambia al estado 'a'
|
|
|
|
las condiciones no especificadas detienen a la máquina.
|
|
|
|
## quintupla binaria
|
|
|
|
como hay dos estado, podemos representarlos como los valores de 1 bit, 0 para 'a' y 1 para 'b'.
|
|
|
|
los dos símbolos ya son las dos opciones de 1 bit, 0 o 1.
|
|
|
|
las dos direcciones posibles también son las dos opciones de un bit, 0 para derecha y 1 para izquierda.
|
|
|
|
esta máquina puede escribirse entonces como un par de quintuplas binarias, en formato: estado actual, símbolo actual, estado nuevo, símbolo nuevo, dirección:
|
|
|
|
```
|
|
00 110
|
|
10 000
|
|
```
|
|
|
|
estas quintuplas pueden usarse como parte de la cinta de la máquina universal bailable {mub}
|
|
|
|
## archivo para turingsim
|
|
|
|
este archivo se puede utilizar con {turingsim} para simular el conteo a partir de esta dupla de quintuplas (?)
|
|
|
|
```
|
|
0
|
|
0000001
|
|
0
|
|
2
|
|
00110
|
|
10000
|
|
80
|
|
```
|