¿Cómo puede ser un editor de flujo, una utilidad para el tratamiento de
texto, un lenguaje Turing completo? sed permite saltos condiciones e
incondicionales y utiliza un buffer temporal, lo que permite
construir una máquina de Turing con él, y cualquier lenguaje que
pueda construir una máquina de Turing es Turing completo.
Una implementación de una máquina de Turing con sed es turing.sed.
Un ejemplo de programa que realiza el incremento de un número binario es el siguiente:
| 10010111
# State 0
0 R0
011R1
000R1
# State 1
1 L2
100R1
111R1
# State 2
2 1R3
201R3
210L2
# State 3
3 RF
300R3
311R3
En la primera línea se muestra el contenido de la cinta a la derecha del cursor, marcado por una barra vertical.
Las siguientes líneas del programa son las reglas que definen lo que debe hacer la máquina de Turing, y tienen la siguiente sintaxis:
estado_actual símbolo_actual nuevo_símbolo dirección nuevo_estado
Para ejecutar el programa:
$ sed -f turing.sed < increment.tm
(0) | |10010111
(0) |1|0010111
(1) 1|0|010111
(1) 10|0|10111
(1) 100|1|0111
(1) 1001|0|111
(1) 10010|1|11
(1) 100101|1|1
(1) 1001011|1|
(1) 10010111| |
(2) 1001011|1|
(2) 100101|1|0
(2) 10010|1|00
(2) 1001|0|000
(3) 10011|0|00
(3) 100110|0|0
(3) 1001100|0|
(3) 10011000| |
(F) 10011000 | |
Final state F reached... end of processing
La salida muestra el estado en el que está la máquina, el contenido de la cinta y la posición del cursor entre dos barras verticales.
El siguiente programa concatena dos cadenas de unos:
# concatenate two strings of 1's
| 11011
# State 0
0 R0
000R0
01 R1
# State 1
111R1
100R2
# State 2
200R2
211R3
# State 3
3 1L4
301L4
311R3
# State 4
411L4
400L5
# State 5
5 R7
500L5
511L6
# State 6
6 R0
600R0
611L6
# State 7
700R7
711R8
# state 8
811R8
8 RF
800RF
Otros ejemplos:
» Tetris » Sokoban (juego » Calculator
Referencias
» A proof that Unix utility "sed" is Turing complete » Implementation of a Turing Machine as Sed Script » Turing machine simulator