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.
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?
| estado actual | símbolo leído | nuevo símbolo | dirección | nuevo estado |
|---|---|---|---|---|
| a | cualquiera | 0 | derecha | b |
| b | cualquiera | el que estaba | derecha | c |
| c | cualquiera | 1 | derecha | d |
| d | cualquiera | el que estaba | derecha | a |
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?
| estado actual | símbolo leído | nuevo símbolo | dirección | nuevo estado |
|---|---|---|---|---|
| a | 0 | 0 | derecha | a |
| a | 1 | 0 | derecha | b |
| a | B | 0 | - | FIN |
| b | 0 | 0 | derecha | b |
| b | 1 | 0 | derecha | a |
| b | B | 1 | - | FIN |
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)
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?
| estado actual | símbolo leído | nuevo símbolo | dirección | nuevo estado |
|---|---|---|---|---|
| a | ) | X | izquierda | b |
| a | ( | ( | derecha | a |
| a | A | A | izquierda | c |
| a | X | X | derecha | a |
| b | ) | ) | izquierda | b |
| b | ( | X | derecha | a |
| b | A | 0 | - | FIN |
| b | X | X | izquierda | b |
| c | ) | - | - | - |
| c | ( | 0 | - | FIN |
| c | A | 1 | - | FIN |
| c | X | X | izquierda | c |
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?
| estado actual | símbolo leído | nuevo símbolo | dirección | nuevo estado |
|---|---|---|---|---|
| a | 0 | 1 | derecha | a |
| a | 1 | 1 | - | FIN |
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?
| estado actual | símbolo leído | nuevo símbolo | dirección | nuevo estado |
|---|---|---|---|---|
| a | 0 | 1 | derecha | b |
| b | 0 | 0 | derecha | 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