Turing Machine Simulator Write a Turing machine simulator.

For simplicity we can assume statuses as integer, symbols as char, blank symbol equals whitespace

5-tuple in the form of current state, input symbol, next state, output symbol, direction (left or right) the order is not mandatory but specify if you swap it

The machine must stop when an unknown state is reached, no other halt condition allowed.

The tape is infinite in both directions and you can always read an empty character.

Input: the initial tape, an initial state and a program. you are free to read the data from anywhere in the format you like

Output: the tape after the execution of the program

Required: an example program that run on top of your simulator

This is a code-colf so the shortest code win.

I'll post an implementation and some example programs in the next few hours.
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