K=document;L=clearInterval;K.O=K.getElementById;_=0;M=Math;a="";h=99;while(h--)a+=M.floor(M.random()*3)+",";a+="0";I=K.createElement("div");I.innerHTML='T<input id="t"value="'+a+'">R<input id="r"value="[[[1,V,1],[2,v,0]],[[2,v,0],[2,V,1]],[[1,v,0],[0,V,0]]]"><input type="button"value="Go"onclick="E()">';eval('K.body.appendChild(I);U=null;E=Q(){r=eval(K.O("r").value);L(_);S=B=y=0;a=(K.O("t").value||"0").split(",");t.r=t.l=t.c=U;for(i=0;i<a.length;B=($=t.a({v:a[i]},V,v)).v>2?$:B||U,i++);B?B.v-=4:U;t.c=B||t.l;_=setInterval(C,20);X.clearRect(0,0,H,H)};v="l";V="r";h=H=400;g=K.O("c");g.width=2*H;g.height=H;X=g.getContext("2d");t={a:Q(n,d,b){T=t[d]||t[b]?t[d]:t[b]=n;T[d]=T==n?U:n;n[b]=T==n?U:T;t[d]=n;return n},m:Q(d,b){T=t.c;t.c=T[d]?T[d]:t.a({v:0},d,b);}};S=0;A={r:v,l:V};y=0;Y=["gray","yellow","red","black"];C=Q(){if(y>H)y=0;x=0;R=r[t.c.v][S];t.c.v=R[0];T=R[1];if(T)t.m(T,A[T]);S=R[2];T=t.l;while(T){X.fillStyle=T==t.c?Y[3]:Y[T.v];X.fillRect(x,y,2,2);x+=2;T=T.r;}y+=2;if(S=="H")L(_);};E();'.replace(/Q/g,'function'))
K=document;
L=clearInterval;
K.O=K.getElementById;
_=0; // interval id
M=Math;
a="";
h=99; // startup Tape length - the tape will be populated with random symbols
while(h--)
a+=M.floor(M.random()*3)+","; // generating random symbols for the tape
a+="0"; // last symbol is always '0' :(, but hey, it saves an 'if-else' statement
I=K.createElement("div");
// the markup for the controls displayed
I.innerHTML=
'T<input id="t"value="'+a+'">'+ // the tape - comma separated values
'R<input id="r"value="[[[1,V,1],[2,v,0]],[[2,v,0],[2,V,1]],[[1,v,0],[0,V,0]]]">'+ // Turing Machine Rules - "Rule 101" - the smallest Universal Turing Machine known ;), as an example
'<input type="button"value="Go"onclick="E()">'; // .
K.body.appendChild(I);
U=null;
// reset and startup procedure
E=function(){
r=eval(K.O("r").value); // get the rules from INPUT
L(_); // clearInterval
S=B=y=0; // set 0 for start position for drawing and set B to faulty value
a=(K.O("t").value||'0').split(","); // get the symbols from the tape as array
t.r=t.l=t.c=U; // reset the tape object
for(i=0;i<a.length;B=($=t.a({v:a[i]},V,v)).v>2?$:B||U,i++); // populate the tape and sets the tape head to the cell marked - if marked
B?B.v-=4:U; // if the tape head was pre-positioned, calculate the symbol in that cell . . .
t.c=B||t.l; // move to the first element in the tape
_=setInterval(C,20);
X.clearRect(0,0,H,H) // cleanup the background
};
v="l"; // symbol for L - Left
V="r"; // symbol for R - Right
h=H=400; // canvas height
g=K.O("c"); // get the canvas element
g.width=2*H;
g.height=H;
X=g.getContext("2d"); // and the 2D drawing context
// THE tape: Simulates infinite tape in both directions and has the following methods: add(Node, toWhichEnd) and move(Left_or_Right)
t={
// function add
// parameters:
// - n - the node - some object in format {v:some_value}
// - d - direction - 'r' or 'l' (right/left)
// - b - direction inverse: 'r'->'l' and for 'l'->'r'
a:function(n,d,b){
T=t[d]||t[b]?t[d]:t[b]=n; // get the last node in the direction d, if exists - if not add another in that direction and use that one
T[d]=T==n?U:n; // next in this direction is n
n[b]=T==n?U:T; // previous will be the previous, or nothing if this is the first one in the list
t[d]=n; // move the 'last' node in this direction to point to n - since n is the last one now
return n; // will save us some coding bellow
},
// function move
// move the head left or right
m:function(d,b){
T=t.c;
t.c=T[d]?T[d]:t.a({v:0},d,b);// if the selected node has a sibling in the direction d, select that sibling; if not - we're at the end of that direction so add a node there and move to it
}
};
S=0; // Machine State
A={r:v,l:V}; // "Anti"-Directions - 'r'->'l'; 'l'->'r'
y=0; // set y to 0 - haven't I done this before ?
Y=["gray","yellow","red","black"]; // set of colors to paint the symbols (Max 3 symbols) and a color for the tape head
C=function(){
if(y>H)
y=0;
x=0;
R=r[t.c.v][S]; // read the symbol on the Tape and according to the current state, read the appropriate rule
t.c.v=R[0]; // write the symbol specified by the rule
T=R[1]; // get the tape head movement direction
if(T) // if direction given ('r' or 'l') - move; if not - presume that this is no move command 'N' - fairly uncommon
t.m(T,A[T]); // move the tape
S=R[2]; // set the state to the machine
// here is where the drawing begins
T=t.l; // get the left-most element in the tape
while(T){
X.fillStyle=T==t.c?Y[3]:Y[T.v]; // get the rect for symbol coloring
X.fillRect(x,y,2,2); // draw the symbol
x+=2;
T=T.r; // next element in tape
}
y+=2;
if(S=="H") // if the current state is "H" (HALT), the machine stops
L(_); // clearInterval
};
E(); // start the computation
