icono de compudanzas

máquinas de turing

compendio de descripciones de máquinas de turing para implementarse de múltiples formas.

ideales para bailarlas en modalidad d-turing

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 actualsímbolo leídonuevo símbolodirecciónnuevo estado
acualquiera0derechab
bcualquierael que estabaderechac
ccualquiera1derechad
dcualquierael que estabaderechaa

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?

estado actualsímbolo leídonuevo símbolodirecciónnuevo estado
a00derechaa
a10derechab
aB0-FIN
b00derechab
b10derechaa
bB1-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)

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?

estado actualsímbolo leídonuevo símbolodirecciónnuevo estado
a)Xizquierdab
a((derechaa
aAAizquierdac
aXXderechaa
b))izquierdab
b(Xderechaa
bA0-FIN
bXXizquierdab
c)---
c(0-FIN
cA1-FIN
cXXizquierdac
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?

estado actualsímbolo leídonuevo símbolodirecciónnuevo estado
a01derechaa
a11-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 actualsímbolo leídonuevo símbolodirecciónnuevo estado
a01derechab
b00derechaa

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

incoming links

d-turing

qiudanz technique

mub

turingsim