#! /bin/sed -f # # turing.sed -- emulate a Turing machine # # Christophe Blaess # 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/.*/Internal 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/.*/I 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/.*/I 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