creat 1201

Brian Inglis

(snip)

Here is the program I used (with some output formatting deleted), written in TECO language at the MIT AILAB in 1974. The seven 16 character lines are the symbol-state data for a Turing machine that simulates a Post Tag Process, which in turn interprets data for a 2-register Universal machine.

hki1Aul qq+^^0:iqm^29iiq y0L1 00L1 11L2 A1L1 y0L1 0yR2 1AR2 AyR6 yyL3 00L0 1AL3 A1L4 yyL4 0yR5 11L7 A1L4 yyR5 0yL3 1AR5 A1R5 yyR6 0AL3 1AR6 A1R6 y0R7 0yR6 11R7 A0R2 jxblx1lx2lx3lx4lx5lx6lx7hk

I find that I don't remember TECO well enough to understand this hideous macro. I do remember spending many hours making and debugging it. However, if any of you can can figure it out, I'd like to know how it works! As for how the simulated Turing machine works, this was described in detail in my 1967 book Computation. The string "110101110000010011011" is the only one I tested it on. The program takes a *doubly" exponential time, and I recall thinking that the universe would not last long enough for it to run any larger program.

Here are some snapshots from its first hundred or so steps: 11o1o1 11ooooo1oo 11o11 yyAyyAyyoooooooooooooooooooooooooooooooo 1 1 11o1o1 11ooooo1oo 11o11 oyAyyAyyoooooooooooooooooooooooooooooooo 1 2 11o1o1 11ooooo1oo 11o11 oyAyyAyyoooooooooooooooooooooooooooooooo 2 3 11o1o1 11ooooo1oo 11oA1 oyAyyAyyoooooooooooooooooooooooooooooooo 2 4 11o1o1 11ooooo1oo 11oAA oyAyyAyyoooooooooooooooooooooooooooooooo 2 5 11o1o1 11ooooo1oo 11oAA yyAyyAyyoooooooooooooooooooooooooooooooo 2 6 11o1o1 11ooooo1oo 11oAA yoAyyAyyoooooooooooooooooooooooooooooooo 1 7 11o1o1 11ooooo1oo 11o11 oyAyyAyyoooooooooooooooooooooooooooooooo 2 8 11o1o1 11ooooo1oo 11oAA yoAyyAyyoooooooooooooooooooooooooooooooo 1 12 11o1o1 11ooooo1oo 11o11 ooAyyAyyoooooooooooooooooooooooooooooooo 2 17 11o1o1 11ooooo1oo AAyAA yyyyyAyyoooooooooooooooooooooooooooooooo 6 25 11o1o1 11ooooo1oo AAyAA yyyyy1yyAooooooooooooooooooooooooooooooo 3 31 11o1o1 11ooooo1oo AAyA1 yyyyyAyyAooooooooooooooooooooooooooooooo 4 40 11o1o1 11ooooo1oy 11y11 yyyyyAyyAooooooooooooooooooooooooooooooo 5 45 11o1o1 11ooooo1oy AAyAA yyyyy1yy1yoooooooooooooooooooooooooooooo 3 60 11o1o1 11ooooo1oy AAyA1 yyyyyAyyAyoooooooooooooooooooooooooooooo 4 70 11o1o1 11ooooo1yy 11y11 yyyyyAyyAyoooooooooooooooooooooooooooooo 5 76 11o1o1 11ooooo1yy AAyAA yyyyy1yy1yyooooooooooooooooooooooooooooo 3 93 11o1o1 11ooooo1yy AAyA1 yyyyyAyyAyyooooooooooooooooooooooooooooo 4 104 11o1o1 11ooooo1yy 11y11 yyyyyAyyAyyooooooooooooooooooooooooooooo 7 111 11o1o1 11ooooy1yy 11y11 yyyyyAyyAyyooooooooooooooooooooooooooooo 6 112 11o1o1 11ooooyAyy AAyAA yyyyy1yy1yyAoooooooooooooooooooooooooooo 3 132

(BriandotInglis{at}SystematicSWdotabdotca)