Turing's Very First Example (with sed)

I have fun with sed and Turing Machine. It is pleasure to digg into sed, to find out the powerful features by sed. To me, sed is not just a tool for string find and replacement, but also Turing-Complete, that means sed is programable, the best way to prove it is to construct a Turing Machine. What I choose here is Turing's very first example by Alan Turing, so I can learn Turing Theory.

The following is my coding with seds, I implement the 4 state (b c e f) table, and use "_" to identify the head position, "$" to identify the end of tap cells and "*" for blank symbols on the tap.

# Turing's very first example

# check input
/^_\?[\*]*$/! b error

# start from first
s/^\*/_/
s/\([_\*]\)$/\1\$/

# b blank P0,R c
: b
h
s/^/b /
p
g

/_/ {
# write 0
s/_/0/

# move right
s/0\*/0_/

/0\$$/ b H

b c
}
b error

: c
h
s/^/c /
p
g 

/_/ {
# print blank
s/_/ /
# right
s/ \*/ _/

/ \$$/ b H
b e
}
b error

: e
h
s/^/e /
p
g 

/_/ {
# print one
s/_/1/
# turn right
s/1\*/1_/

/1\$$/ b H
b f
}
b error

: f

h
s/^/f /
p
g 

/_/ {
# print blank
s/_/ /
# right

s/ \*/ _/

/ \$$/ b H
b b
}
b error



: error
s/^/error with turing machine/

q 1

: H
s/^/= /
s/\$$//
q 0

And the output:

 # echo "********" | sed -f Turing_first.sed 
b _*******$
c 0_******$
e 0 _*****$
f 0 1_****$
b 0 1 _***$
c 0 1 0_**$
e 0 1 0 _*$
f 0 1 0 1_$
= 0 1 0 1