dd/sh is powerful enough to emulate a turing machine. We
show here the program without comment, as anybody
who has read and understood the text editor will
have no problems understanding this (much simpler) code.
The usage is really simple:
turing "Initial_state" "Initial_tape_contents" < program
Where "Initial_state" is a single character,
"Initial_tape_contents" is a (possibly empty) string
describing the tape on the right of the machine's head (the left cannot
be initialised, but you can always start the program moving the head
to the right ad required). The program consists of one statement per
line, with five fields separated by "|" (pipe symbol);
the fields are old state, old symbol, movement (left, right, stop),
new state, new symbol respectively.
When a move is not possible, or the movement of the last executed command was "stop", the machine prints the state and the tape contents and stops. The head is represented by a pipe symbol.
We have provided, for your convenience, three example programs.
Program 0 runs from initial state "a" with tape contents "This is a test". After downloading the machine and the program, you can run it as:
turing a "This is a test" < prog
The machine will end in state " " (space) with the head just before
the string "Aren't you glad you asked?". This will be represented as:
|Aren't you glad you asked?
Program 1 runs from initial state " " (space) with tape contents " " (space) After downloading the machine and the program, you can run it as:
turing " " " " < prog1
The machine will end in state "." (dot) with the head just before
the string "Use dd/sh, not perl!". This will be represented as:
. |Use dd/sh, not perl!
Program 2 also runs from initial state " " (space). The tape contents are a string of "1"s followed by a string of "2"s (for example "111222" or "112222"). After the program runs, the tape will contain a string of "3"s, where the number of "3"s is the product of the number of "1"s and the number of "2"s: given the two example inputs, the results will be "333333333" (nine "3"s) and "33333333" (eight "3"s), respectively. The program file is this and you call it as:
turing " " 111222 < prog2
turing " " 112222 < prog2
As soon as workload permits, I will be adding some more example programs for the Turing machine. Note, however, that we do not recommend using Turing machines as an alternative to DD/SH.