#!/bin/sh

# turing machine written in dd/sh

# usage: turing [-v] Initial_state "Initial tape contents" < program
# program has lines of the form:
# state|symbol|movement|new-state|new-symbol
# where movement is "left", "right" or "stop"

# /bin/rm is not really required, but it is nice to clean up temporary files

PATH=
dd=/bin/dd
rm=/bin/rm

# temporary files we might need
tape=/tmp/tape.$$
tmp=/tmp/silly.$$
program=/tmp/turing.$$
trap "$rm -f $tmp $program $tape.left $tape.right; exit" 0 1 2 3

# from now on, no more rm - the above trap is enough
unset rm

case "$1" in
    -v*) debug=true ; shift ;;
    *)   debug=false ;;
esac

# we do interesting things with IFS, but better save it...
saveIFS="$IFS"

# in case "echo" is not a shell builtin...

Echo () {
case "$1" in
  -n) shift
      $dd of=$tmp 2>/dev/null <<EOF 
$@
EOF
      IFS="+"
      set `$dd if=$tmp bs=1 of=/dev/null skip=1 2>&1`
      IFS="$saveIFS"
      $dd if=$tmp bs=1 count=$1 2>/dev/null
      ;;
  *)  $dd 2>/dev/null <<EOF 
$@
EOF
      ;;
esac
}

# Initialise tapes
$dd if=/dev/null of=$tape.left 2>/dev/null
Echo -n "$2" > $tape.right

# Initialise state (use first character only)
state=`Echo "$1" | $dd bs=1 count=1 2</dev/null`

# Now read program
Echo 'program () {' > $program
Echo '    case "$1$2" in' >> $program

IFS='|'
while read oldstate oldsymbol movement newstate newsymbol
do
    Echo "        \"$oldstate$oldsymbol\"*)" >> $program
    Echo "            state=\"$newstate\"" >> $program
    Echo "            move=$movement" >> $program
    Echo "            symbol=\"$newsymbol\"" >> $program
    Echo '            ;;' >> $program
done
IFS="$saveIFS"

Echo '        *)' >> $program
Echo '            state="$1"' >> $program
Echo '            move=stop' >> $program
Echo '            symbol="$2"' >> $program
Echo '            ;;' >> $program
Echo '    esac' >> $program
Echo '}' >> $program

# source $program
eval "`$dd if=$program bs=1 2>/dev/null`"

true () {
    return 0;
}

false () {
    return 1;
}

zero () {
  ( trap 'go=false' 13
    go=true
    while $go
    do
      $dd "if=$0"
      case "$?" in
	0) ;;
	*) go=false ;;
      esac
    done
  ) 2>/dev/null
}

# subtract variable n1 n2
# subtracts n2 from n1, assigns result to variable

subtract () {
  result="$1"
  zero | $dd of=$tmp bs=1 "count=$2" 2>/dev/null
  IFS="+"
  set `$dd if=$tmp bs=1 of=/dev/null "skip=$3" 2>&1`
  IFS="$saveIFS"
  eval $result='$1'
}

printstate () {
    Echo -n "$state "
    $dd if=$tape.left 2>/dev/null
    Echo -n '|'
    $dd if=$tape.right 2>/dev/null
    Echo
}

# go!
go=true
while $go
do
    if $debug
    then
	printstate
    fi
    symbol="`$dd if=$tape.right bs=1 count=1 2>/dev/null`"
    program "$state" "$symbol"
    case "$move" in
        r*)
	    Echo -n "$symbol" >> $tape.left
	    case `$dd if=$tape.right of=/dev/null bs=1 skip=1 2>&1` in
	        0*) Echo -n ' ' > $tape.right ;;
		*)
		    $dd if=$tape.right of=$tmp bs=1 skip=1 2>/dev/null
		    $dd if=$tmp of=$tape.right 2>/dev/null
		    ;;
	    esac
	    ;;
        l*)
	    IFS='+'
	    set `$dd if=$tape.left bs=1 of=/dev/null 2>&1`
	    len="$1"
	    IFS="$saveIFS"
	    case $len in
	        0*)
		    Echo -n ' ' > $program
		    $dd if=$tape.right bs=1 >> $program 2>/dev/null
		    $dd if=$program of=$tape.right bs=1 2>/dev/null
		    ;;
		*)
		    subtract len $len 1
		    $dd if=$tape.left bs=1 skip=$len of=$program 2>/dev/null
		    Echo -n "$symbol" >> $program
		    $dd if=$tape.right bs=1 skip=1 2>/dev/null >> $program
		    $dd if=$program of=$tape.right 2>/dev/null
		    $dd if=$tape.left bs=1 count=$len of=$program 2>/dev/null
		    $dd if=$program of=$tape.left 2>/dev/null
		    ;;
	    esac
	    ;;
	*)
	    go=false
	    ;;
    esac
done
printstate