Turing Machine Simulator
GNU sed with -r - 133 117 111 93 chars

Yes, sed is turing complete. GNU sed and -r (extended regexps) is only to save a few characters, it is only a small change to work with POSIX sed.

:s
s/^(.*@)(.*)&gt;(.)(.*#\1\3([^@]*@)(..))/\5\2\6&gt;\4/
T
s/(..)l&gt;|r&gt;/&gt;\1/
s/&gt;@/@&gt; /
s/&gt;#/&gt; #/
bs


Input format is 

[initial state]@[non-empty tape with &gt; marking head position]#[state]@[input symbol][next state]@[output symbol][direction l or r]#...


The delimiters @, # and head character &gt; cannot be used as a symbol on the tape. State labels cannot contain @ &gt; or #.

It will run all of the programs in the input, one per line

Examples:

Marco's anbn program


  Input

0@&gt;aaabbb#0@a1@ r#0@ 4@ r#1@a1@ar#1@b1@br#1@ 2@ l#2@b3@ l#2@a5@al#3@b3@bl#3@a3@al#3@ 0@ r#4@ 5@Tr

  
  Output

5@    T&gt;  #0@a1@ r#0@ 4@ r#1@a1@ar#1@b1@br#1@ 2@ l#2@b3@ l#2@a5@al#3@b3@bl#3@a3@al#3@ 0@ r#4@ 5@Tr



Marco's Hello! program


  Input

0@&gt; #0@ 1@Hr#1@ 2@er#2@ 3@lr#3@ 4@lr#4@ 5@or#5@ 6@!r

  
  Output

6@Hello!&gt; #0@ 1@Hr#1@ 2@er#2@ 3@lr#3@ 4@lr#4@ 5@or#5@ 6@!r