💾 Archived View for compudanzas.net › m%C3%A1quinas_de_turing.gmi captured on 2024-05-10 at 10:52:32. Gemini links have been rewritten to link to archived content
⬅️ Previous capture (2024-03-21)
-=-=-=-=-=-=-
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.
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
tres símbolos posibles: 0, 1, y vacío
cuatro estados posibles: a, b, c, d
la máquina empieza en el estado a.
la cinta puede estar "vacía".
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?
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)
tres símbolos posibles: 0, 1, y B
dos estados posibles: a, b
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.
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?
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
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
cuatro símbolos posibles: (, ), A, X
tres estados posibles: a, b, c
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.
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?
dibujo que representa la tabla de arriba, pero con símbolos estilizados
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
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í)
dos símbolos posibles: 0 y 1
un estado: a
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"
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?
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.
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
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
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í)
dos símbolos posibles: 0 y 1
dos estados: a, b
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"
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?
las condiciones no especificadas detienen a la máquina.
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
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
