#! /bin/sed -f
# 
# turing.sed -- emulate a Turing machine
#
# Christophe Blaess <ccb@club-internet.fr>
# http://perso.club-internet.fr/ccb/

# See text file for information about Turing Machine script.

# Read all the instructions, and add a final newline.
:read
N  
$ !b read
G  

# Delete comments extending from a '#' to the end of the line.
s/#[^\n]*\n//g
s/#.*$//g

# Use a colon to separate the instructions.
s/\n/:/g

# Is there an initial tape ?
/|/ s/\(.*\)|\([^:]\)\([^:]*\):\(.*\)/|\2|\3:\1\4/

# else insert a blank one.
/|/ !s/\(.*\)/| |:\1/

# Reserve the storage place at the beginning of the pattern space,
# then set the current state to zero.
s/\(.*\)/0x\1/

# Start the machine !
:loop
# Display only the tape and the state.
h  
# (comment out the next two lines to see internal data when
#  debuging TM script)
s/:.*//
s/^\(.\)./(\1) /
p  
g  

# Check the content of the current cell.
/|[^:|]|/ !{
    s/.*/nternal error in the Turing machine/
    q
}  

# Store in second position the symbol read on the tape
s/^\(.\).\(.*\)|\(.\)|\(.*\)/\1\3\2|\3|\4/

# Have we reached a final state ?
/^\(.\).*:\1/ !{
    s/\(.\).*/Final state \1 reached... end of processing/
    q
}  

# Is there an instruction for this state and this cell content ?
/^\(..\).*:\1/ !{
    s/^\(.\)\(.\).*/No instruction for state \1 and cell \2/
    q
}  

# Look for the new content to write.
/^\(..\).*:\1[^:|]/ !{
    s/.*/can't write this symbol on the tape!/
    q
}  
s/^\(..\)\(.*\)|.|\(.*\):\1\(.\)/\1\2|\4|\3:\1\4/

# Look for the direction of movement.
/^\(..\).*:\1.[ LRlr]/ !{
    s/.*/Movement must be specified as L, R or space/
    q
}  
# Clear the substitute flag that we will use later.
t nop
:nop
/^\(..\).*:\1. / {
    # Direction = ' ' -> Don't move the head
    b end_move
}  
/^\(..\).*:\1.[Ll]/ {
    # Move the head to the left if the tape is long enough,
    s/^\(..\)\(.*\)\(.\)|\(.\)|/\1\2|\3|\4/
    t end_move
    # else extend the tape with an empty cell.
    s/|\(.\)|/| |\1/
    b end_move
}  

# Move the head to the right, if the tape is long enough,
s/|\(.\)|\([^:]\)/\1|\2|/
t end_move
# else extend the tape with an empty cell.
s/|\(.\)|/\1| |/

:end_move

# Check the new state,
/^\(..\).*:\1..[^:|]/ !{
    s/.*/can't use this symbol as new state/
    q
}  
# then switch the machine state
s/^\(.\)\(.\)\(.*\):\1\2\(..\)\(.\)/\5\2\3:\1\2\4\5/

# Garbage collector : cut the blank portions of the tape,
# on the left,
s/\(..\) */\1/
# then on the right.
s/\(..\)\([^:]\) *:/\1\2:/

b loop

###### end of the script 

### colorized by sedsed, a debugger and code formatter for sed scripts
### original script: http://sed.sf.net/grabbag/scripts/turing.sed