# 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
```