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/^(.*@)(.*)>(.)(.*#\1\3([^@]*@)(..))/\5\2\6>\4/ T s/(..)l>|r>/>\1/ s/>@/@> / s/>#/> #/ bs 

Input format is

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

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

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

Examples:

Marco's aⁿbⁿ program

Input

0@>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> #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@> #0@ 1@Hr#1@ 2@er#2@ 3@lr#3@ 4@lr#4@ 5@or#5@ 6@!r 

Output

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

So I'm a bit late, but just thought I would leave this here...

Turing Machine Simulating a Turing Machine: 370 bytes?

Here I'm using the structure Turing used in his 1936 paper. I'm using one symbol = one byte, including m-configs and operations.

╔═══════════════╦═══════╦═══════════════════╦═══════════════╗ ║ m-config ║ Symbol ║ Operations ║ Final m-config ║ ╠═══════════════╬═══════╬═══════════════════╬═══════════════╣ ║ currentCommand ║ Any ║ L ║ currentCommand ║ ║ ║ * ║ MR ║ readCommand ║ ╠----------------╬--------╬---------------------╬----------------╣ ║ nextCommand ║ Any ║ L ║ nextCommand ║ ║ ║ * ║ E R R R P* R ║ readCommand ║ ╠----------------╬--------╬---------------------╬----------------╣ ║ readCommand ║ P ║ R ║ readCommandP ║ ║ ║ M ║ R ║ readCommandM ║ ║ ║ G ║ R ║ readCommandG ║ ║ ║ E ║ R ║ MHPNone ║ ╠----------------╬--------╬---------------------╬----------------╣ ║ readCommandP ║ 0 ║ ║ MHP0 ║ ║ ║ 1 ║ ║ MHP1 ║ ║ ║ e ║ ║ MHPe ║ ║ ║ x ║ ║ MHPx ║ ║ ║ None ║ ║ MHPNone ║ ╠----------------╬--------╬---------------------╬----------------╣ ║ readCommandM ║ R ║ ║ MHMR ║ ║ ║ L ║ ║ MHML ║ ╠----------------╬--------╬---------------------╬----------------╣ ║ readCommandG ║ 1 ║ ║ G2<1 ║ ║ ║ 2 ║ ║ G2<2 ║ ║ ║ 3 ║ ║ G2<3 ║ ║ ║ 4 ║ ║ G2<4 ║ ║ ║ 5 ║ ║ G2<5 ║ ╠----------------╬--------╬---------------------╬----------------╣ ║ G2<1 ║ int(1) ║ L P@ R R R P* R ║ GTS ║ ║ ║ < ║ ║ G21 ║ ║ ║ * ║ E L ║ G2<1 ║ ║ ║ @ ║ E L ║ G2<1 ║ ║ ║ Any ║ L ║ G2<1 ║ ╠----------------╬--------╬---------------------╬----------------╣ ║ G2<2 ║ int(2) ║ L P@ R R R P* R ║ GTS ║ ║ ║ < ║ ║ G22 ║ ║ ║ * ║ E L ║ G2<2 ║ ║ ║ @ ║ E L ║ G2<2 ║ ║ ║ Any ║ L ║ G2<2 ║ ╠----------------╬--------╬---------------------╬----------------╣ ║ G2<3 ║ int(3) ║ L P@ R R R P* R ║ GTS ║ ║ ║ < ║ ║ G23 ║ ║ ║ * ║ E L ║ G2<3 ║ ║ ║ @ ║ E L ║ G2<3 ║ ║ ║ Any ║ L ║ G2<3 ║ ╠----------------╬--------╬---------------------╬----------------╣ ║ G2<4 ║ int(4) ║ L P@ R R R P* R ║ GTS ║ ║ ║ < ║ ║ G24 ║ ║ ║ * ║ E L ║ G2<4 ║ ║ ║ @ ║ E L ║ G2<4 ║ ║ ║ Any ║ L ║ G2<4 ║ ╠----------------╬--------╬---------------------╬----------------╣ ║ G2<5 ║ int(5) ║ L P@ R R R P* R ║ GTS ║ ║ ║ < ║ ║ G25 ║ ║ ║ * ║ E L ║ G2<5 ║ ║ ║ @ ║ E L ║ G2<5 ║ ║ ║ Any ║ L ║ G2<5 ║ ╠----------------╬--------╬---------------------╬----------------╣ ║ G21 ║ int(1) ║ L P@ R ║ GTS ║ ║ ║ Any ║ R ║ G21 ║ ╠----------------╬--------╬---------------------╬----------------╣ ║ G22 ║ int(2) ║ L P@ R ║ GTS ║ ║ ║ Any ║ R ║ G22 ║ ╠----------------╬--------╬---------------------╬----------------╣ ║ G23 ║ int(3) ║ L P@ R ║ GTS ║ ║ ║ Any ║ R ║ G23 ║ ╠----------------╬--------╬---------------------╬----------------╣ ║ G24 ║ int(4) ║ L P@ R ║ GTS ║ ║ ║ Any ║ R ║ G24 ║ ╠----------------╬--------╬---------------------╬----------------╣ ║ G25 ║ int(5) ║ L P@ R ║ GTS ║ ║ ║ Any ║ R ║ G25 ║ ╠----------------╬--------╬---------------------╬----------------╣ ║ GTS ║ ^ ║ R ║ TS ║ ║ ║ Any ║ R ║ GTS ║ ╠----------------╬--------╬---------------------╬----------------╣ ║ TS ║ 0 ║ ║ RL0 ║ ║ ║ 1 ║ ║ RL1 ║ ║ ║ e ║ ║ RLe ║ ║ ║ x ║ ║ RLx ║ ║ ║ None ║ ║ RLNone ║ ╠----------------╬--------╬---------------------╬----------------╣ ║ RL0 ║ @ ║ R R ║ GTS0 ║ ║ ║ Any ║ L ║ RL0 ║ ╠----------------╬--------╬---------------------╬----------------╣ ║ RL1 ║ @ ║ R R ║ GTS1 ║ ║ ║ Any ║ L ║ RL1 ║ ╠----------------╬--------╬---------------------╬----------------╣ ║ RLe ║ @ ║ R R ║ GTSe ║ ║ ║ Any ║ L ║ RLe ║ ╠----------------╬--------╬---------------------╬----------------╣ ║ RLx ║ @ ║ R R ║ GTSx ║ ║ ║ Any ║ L ║ RLx ║ ╠----------------╬--------╬---------------------╬----------------╣ ║ RLNone ║ @ ║ R R ║ GTSNone ║ ║ ║ Any ║ L ║ RLNone ║ ╠----------------╬--------╬---------------------╬----------------╣ ║ GTS0 ║ 0 ║ R P* R ║ readCommand ║ ║ ║ Any ║ R ║ GTS0 ║ ╠----------------╬--------╬---------------------╬----------------╣ ║ GTS1 ║ 1 ║ R P* R ║ readCommand ║ ║ ║ Any ║ R ║ GTS1 ║ ╠----------------╬--------╬---------------------╬----------------╣ ║ GTSe ║ e ║ R P* R ║ readCommand ║ ║ ║ Any ║ R ║ GTSe ║ ╠----------------╬--------╬---------------------╬----------------╣ ║ GTSx ║ x ║ R P* R ║ readCommand ║ ║ ║ Any ║ R ║ GTSx ║ ╠----------------╬--------╬---------------------╬----------------╣ ║ GTSNone ║ _ ║ R P* R ║ readCommand ║ ║ ║ Any ║ R ║ GTSNone ║ ╠----------------╬--------╬---------------------╬----------------╣ ║ MHP0 ║ ^ ║ R ║ Print0 ║ ║ ║ Any ║ R ║ MHP0 ║ ╠----------------╬--------╬---------------------╬----------------╣ ║ MHP1 ║ ^ ║ R ║ Print1 ║ ║ ║ Any ║ R ║ MHP1 ║ ╠----------------╬--------╬---------------------╬----------------╣ ║ MHPe ║ ^ ║ R ║ Printe ║ ║ ║ Any ║ R ║ MHPe ║ ╠----------------╬--------╬---------------------╬----------------╣ ║ MHPx ║ ^ ║ R ║ Printx ║ ║ ║ Any ║ R ║ MHPx ║ ╠----------------╬--------╬---------------------╬----------------╣ ║ MHPNone ║ ^ ║ R ║ PrintNone ║ ║ ║ Any ║ R ║ MHPNone ║ ╠----------------╬--------╬---------------------╬----------------╣ ║ MHMR ║ ^ ║ R R ║ MHR ║ ║ ║ Any ║ R ║ MHMR ║ ╠----------------╬--------╬---------------------╬----------------╣ ║ MHML ║ ^ ║ L ║ MHL ║ ║ ║ Any ║ R ║ MHML ║ ╠----------------╬--------╬---------------------╬----------------╣ ║ Print0 ║ ^ ║ R ║ Print0 ║ ║ ║ None ║ P0 ║ nextCommand ║ ║ ║ Any ║ E ║ Print0 ║ ╠----------------╬--------╬---------------------╬----------------╣ ║ Print1 ║ ^ ║ R ║ Print1 ║ ║ ║ None ║ P1 ║ nextCommand ║ ║ ║ Any ║ E ║ Print1 ║ ╠----------------╬--------╬---------------------╬----------------╣ ║ Printx ║ ^ ║ R ║ Printx ║ ║ ║ None ║ Px ║ nextCommand ║ ║ ║ Any ║ E ║ Printx ║ ╠----------------╬--------╬---------------------╬----------------╣ ║ Printe ║ ^ ║ R ║ Printe ║ ║ ║ None ║ Pe ║ nextCommand ║ ║ ║ Any ║ E ║ Printe ║ ╠----------------╬--------╬---------------------╬----------------╣ ║ PrintNone ║ ^ ║ R ║ PrintNone ║ ║ ║ None ║ ║ nextCommand ║ ║ ║ Any ║ E ║ PrintNone ║ ╠----------------╬--------╬---------------------╬----------------╣ ║ MHL ║ ^ ║ R R ║ MHL ║ ║ ║ [ ║ ║ SBL ║ ║ ║ Any ║ L P^ R R E ║ nextCommand ║ ╠----------------╬--------╬---------------------╬----------------╣ ║ MHR ║ ^ ║ R R ║ MHR ║ ║ ║ ] ║ ║ SBR ║ ║ ║ None ║ P^ L L E ║ nextCommand ║ ╠----------------╬--------╬---------------------╬----------------╣ ║ SBR ║ ] ║ E R R P] ║ currentCommand ║ ╠----------------╬--------╬---------------------╬----------------╣ ║ SBL ║ ] ║ R ║ SBLE ║ ║ ║ Any ║ R ║ SBL ║ ╠----------------╬--------╬---------------------╬----------------╣ ║ SBLE ║ [ ║ ║ currentCommand ║ ║ ║ None ║ L ║ SBLE ║ ║ ║ Any ║ E R R P] L ║ SBLE ║ ╚═══════════════╩═══════╩═══════════════════╩═══════════════╝ 

Here is one of Turing's examples from the paper above for my machine:

['<', None, 1, '0', None, 'P', 'e', None, 'M', 'R', None, 'P', 'e', None, 'M', 'R', None, 'P', '0', None, 'M', 'R', None, 'M', 'R', None, 'P', '0', None, 'M', 'L', None, 'M', 'L', None, 'G', '2', '1', None, 'P', 'e', None, 'M', 'R', None, 'P', 'e', None, 'M', 'R', None, 'P', '0', None, 'M', 'R', None, 'M', 'R', None, 'P', '0', None, 'M', 'L', None, 'M', 'L', None, 'G', '2', 'e', None, 'P', 'e', None, 'M', 'R', None, 'P', 'e', None, 'M', 'R', None, 'P', '0', None, 'M', 'R', None, 'M', 'R', None, 'P', '0', None, 'M', 'L', None, 'M', 'L', None, 'G', '2', 'x', None, 'P', 'e', None, 'M', 'R', None, 'P', 'e', None, 'M', 'R', None, 'P', '0', None, 'M', 'R', None, 'M', 'R', None, 'P', '0', None, 'M', 'L', None, 'M', 'L', None, 'G', '2', '_', None, 'P', 'e', None, 'M', 'R', None, 'P', 'e', None, 'M', 'R', None, 'P', '0', None, 'M', 'R', None, 'M', 'R', None, 'P', '0', None, 'M', 'L', None, 'M', 'L', None, 'G', '2', None, 2, '1', None, 'M', 'R', None, 'P', 'x', None, 'M', 'L', None, 'M', 'L', None, 'M', 'L', None, 'G', '2', '0', None, 'G', '3', None, 3, '0', None, 'M', 'R', None, 'M', 'R', None, 'G', '3', '1', None, 'M', 'R', None, 'M', 'R', None, 'G', '3', '_', None, 'P', '1', None, 'M', 'L', None, 'G', '4', None, 4, 'x', None, 'E', 'E', None, 'M', 'R', None, 'G', '3', 'e', None, 'M', 'R', None, 'G', '5', '_', None, 'M', 'L', None, 'M', 'L', None, 'G', '4', None, 5, '0', None, 'M', 'R', None, 'M', 'R', None, 'G', '5', '1', None, 'M', 'R', None, 'M', 'R', None, 'G', '5', 'e', None, 'M', 'R', None, 'M', 'R', None, 'G', '5', 'x', None, 'M', 'R', None, 'M', 'R', None, 'G', '5', '_', None, 'P', '0', None, 'M', 'L', None, 'M', 'L', None, 'G', '2', None, '[', '^', None, ']', None] 

Try it online! (Uses Python 3 as an interpreter) --Edit: I just checked the TIO, and it doesn't seem to actually work right... Try it on your local machine and it should (hopefully) work. It does on mine.

APL (110)

(It's not even that short...)

0(''⍞){×⍴X←0~⍨⍺∘{x y S T s m t←⍺,⍵⋄S T≡x,⊃⊃⌽y:s,⊂(⊃y){m:(¯1↓⍺)(⍵,⍨¯1↑⍺)⋄(⍺,⊃⍵)(1↓⍵)}t,1↓⊃⌽y⋄0}¨⍵:⍵∇⍨⊃X⋄,/⊃⌽⍺}⎕ 

It reads two lines from the keyboard: the first is the program and the second is the initial tape.

The format is

(in-state in-tape out-state movement out-tape) 

and they should all be on the same line. 'Movement' is 0 to move right and 1 to move left.

Example program (line breaks inserted for clarity, they should be all on one line.)

(0 ' ' 1 0 '1') (0 '1' 0 0 '1') (1 '1' 1 0 '1') (1 ' ' 2 1 ' ') (2 '1' 3 1 ' ') 

The program adds two unary numbers together, for example:

in: 1111 111 out: 1111111 

Example 2 (adapted from the binary increment program from Marco Martinelli's entry):

(0 '0' 0 0 '0') (0 '1' 0 0 '1') (0 ' ' 1 1 ' ') (1 '0' 2 0 '1') (1 '1' 3 1 '0') (3 '0' 2 0 '1') (3 ' ' 2 0 '1') (3 '1' 3 1 '0') 

Python, 101 189 152 142

a=dict(zip(range(len(b)),b)) r=eval(p) i=s=0 while 1: c=a.get(i,' ') s,m,a[i]=r[s,c] if 0==m:exit([x[1]for x in sorted(a.items())]) i=i+m 

b and p are the inputs, b is the initial tape, p encodes the rules as (string representation of) a dict from (in-state, in-tape) tuple to (out-state, head move, out-tape) tuple. If move is 0 the program finishes, 1 is move to the right and -1 is move to the left.

b="aaba" p="""{(0, 'a'): (1, 1, 'a'), (0, 'b'): (0, 1, 'b'), (1, 'a'): (1, 1, 'a'), (1, 'b'): (0, 1, 'b'), (1, ' '): (1, 0, 'Y'), (0, ' '): (0, 0, 'N')}""" 

This sample program tests if the last letter of the string (before empty tape) is 'a', if so it writes 'Y' at the end of the string (first empty space).

Edit 1:

Changed the tape to be represented as a dict, as it seemed the shortest way to write an extensible data structure. The second to last line is mostly transforming it back into readable form for output.

Edit 2:

Thanks to Strigoides for a great deal of improvements.

Edit 3:

I had unnecessarily made it so 0 as output would leave the place as it is. I removed this as we can always write the output the same as the input.

Postscript (205) (156) (150) (135)

<< >>begin /${stopped}def([){add dup{load}${exit}if}def 0 A{1 index{load}${pop( )}if get{exec}${exit}if}loop 3{-1[pop}loop{1[print}loop 

This is probably cheating, but the transition table contains code to perform the transitions. And since the tape is represented by a mapping from integers to integers, I've represented states as a mapping from names to dictionaries so the tape and the program coexist in the same anonymous dictionary.

Extra savings by making all state names executable, so they auto-load.

Ungolfed with embedded "Hello" program. An extra 52 chars buys a loop to read the tape from stdin. Run with gsnd -q tm.ps.

%! << /A<<( ){dup(H)def 1 add B}>> /B<<( ){dup(e)def 1 add C}>> /C<<( ){dup(l)def 1 add D}>> /D<<( ){dup(l)def 1 add E}>> /E<<( ){dup(o)def 1 add F}>> >>begin %ds: int-keys=tape name-keys=prog 0 A %pos state { %loop 1 index{load}stopped{pop( )}if %pos state tape(pos) get {exec}stopped{exit }if %new-pos new-state } loop % Loop from tape position 0 to left until left tape end is found 0{ %pos -1 add %new-pos dup{load}stopped{exit}if %new-pos tape(new-pos) pop %new-pos tape(new-pos) }loop % Move to the right and print all chars until right end is hit { %pos 1 add %new-pos dup{load}stopped{exit}if %new-pos tape(new-pos) print %new-pos tape(new-pos) }loop 

So the table-format is

/in-state<<in-tape{dup out-tape def movement add out-state} in-tape2{dup out-tape2 def movement2 add out-state2}>> 

where in-state is a name, in-tape and out-tape are chars (ie. integers, or expressions which yield integers), movement is -1 for left or 1 for right, and out-state is an executable name. Multiple in-tape transition for the same state must be combined as above.

C (not golfed yet)

I suppose I can't win with this, still it was fun getting it to work. This is even more true now that it really does work. :)

Except it's only infinite in one direction. I suppose it needs a negative tape, too. Sigh....

Negative wasn't so bad. We interleave the two sides as evens and odds. Complication is now it needs to display the tape in sequential order, as the file itself is now jumbled. This is a legitimate alteration to make, I think. Turing himself simplified this way.

#include<stdio.h> int main(int c, char**v){ int min=0,max=0; int pos=0,qi;sscanf(v[1],"%d",&qi); FILE*tab=fopen(v[2],"r"); FILE*tape=fopen(v[3],"r+"); setbuf(tape,NULL); do { min = pos<min? pos: min; max = pos>max? pos: max; fseek(tape,(long)(abs(pos)*2)-(pos<0),SEEK_SET); int c = fgetc(tape), qt=qi-1,qr; fseek(tape,(long)(abs(pos)*2)-(pos<0),SEEK_SET); char x = c==EOF?' ':c, xt=x-1,xr,d[2]; if (x == '\n') x = ' '; printf("%d '%c' %d (%d)\n", qi, x, pos, (int)ftell(tape)); while((qt!=qi)||(xt!=x)){ fscanf(tab, "%d '%c' %d '%c' %1[LRN]", &qt, &xt, &qr, &xr, d); if (feof(tab)){ goto HALT; } printf("%d '%c' %d '%c' %s\n", qt, xt, qr, xr, d); } qi=qr; rewind(tab); fputc(xr,tape); pos+=*d=='L'?-1:*d=='R'?1:0; } while(1); HALT: printf("[%d .. %d]:\n", min, max); for (pos = min; pos <= max; pos++){ fseek(tape,(long)(abs(pos)*2)-(pos<0),SEEK_SET); //printf("%d ",pos); putchar(fgetc(tape)); //puts(""); } return qi; } 

And here's the test-run:

522(1)04:33 AM:~ 0> cat bab.tm 0 'a' 0 'b' R 0 'b' 0 'a' R 523(1)04:33 AM:~ 0> echo aaaaa > blank; make tm ; tm 0 bab.tm blank; echo; cat blank make: `tm' is up to date. 0 'a' 0 (0) 0 'a' 0 'b' R 0 'a' 1 (2) 0 'a' 0 'b' R 0 'a' 2 (4) 0 'a' 0 'b' R 0 ' ' 3 (6) 0 'a' 0 'b' R 0 'b' 0 'a' R [0 .. 3]: bbbÿ babab 

The program outputs the tape in sequential order, but the file represents the negative and positive sides interleaved.

Groovy 234 228 154 153 149 139 124

n=[:];i=0;t={it.each{n[i++]=it};i=0};e={p,s->a=p[s,n[i]?:' '];if(a){n[i]=a[1];i+=a[2];e(p,a[0])}else n.sort()*.value.join()} 

Formatted for readability

n=[:]; i=0; t={it.each{n[i++]=it};i=0}; e={p,s-> a=p[s,n[i]?:' ']; if(a){ n[i]=a[1]; i+=a[2]; e(p,a[0]) }else n.sort()*.value.join() } 

t is the function that set the tape e is the function that evaluate the program

Example 1 - Print "Hello!" on the tape :)

t('') e([[0,' ']:[1,'H',1], [1,' ']:[2,'e',1], [2,' ']:[3,'l',1], [3,' ']:[4,'l',1], [4,' ']:[5,'o',1], [5,' ']:[6,'!',1]],0) 

Example 2 - Leave a T on the tape if the initial string is in the form of aⁿbⁿ, stop otherwise.

t('aaabbb') e([[0,'a']:[1,' ',1], [0,' ']:[4,' ',1], [1,'a']:[1,'a',1], [1,'b']:[1,'b',1], [1,' ']:[2,' ',-1], [2,'b']:[3,' ',-1], [2,'a']:[5,'a',-1], [3,'b']:[3,'b',-1], [3,'a']:[3,'a',-1], [3,' ']:[0,' ',1], [4,' ']:[5,'T',1]],0) 

Example 3 - Increment of a binary number

t('101') e([[0,'0']:[0,'0',1], [0,'1']:[0,'1',1], [0,' ']:[1,' ',-1], [1,'0']:[2,'1',1], [1,'1']:[3,'0',-1], [3,'0']:[2,'1',1], [3,' ']:[2,'1',1], [3,'1']:[3,'0',-1]],0) 

in the examples 1 means move to the right and -1 means move to the left