sed is turing complete...

turing.sed

#! /bin/sed -f
# 
# turing.sed -- emulate a Turing machine
#
# Christophe Blaess <[email protected]>
# 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