By Wayne Dwight Thorsen <wdt21@columbia.edu>


This code works with Suzanne Brittons Turing Machine applet.

1)      equal-streak TM: A decider for that accepts any string of the form
	0^n | 1^n | 0^n 1^n | 1^n 0^n | 0^n 1^n 0^n | ... any string which
        alternates between streaks of 0's and 1's of the same length,
        (epsilon is accepted as well).



See the applet at:
http://www.igs.net/~tril/tm/tm.html

COPY/PASTE THE CODE BETWEEN THE UNDERLINES INTO THE APPLET

PHASE I)

This finds the first 0 or 1 and marks it as Q or Z respectively.
It then seperates the 0's and 1's by making the beginning of each
streak with an B or A respectively.
_________________________________________________
1,_,H,_,>
1,0,2,Q,>
1,1,3,Z,>
2,0,2,0,>
2,_,H,_,>
3,1,3,1,>
3,_,H,_,>
2,1,5,A,>
3,0,4,B,>
4,0,4,0,>
4,_,6,_,<
4,1,5,A,>
5,1,5,1,>
5,0,4,B,>
5,_,6,_,<
____________________________________________
Phase 2
This code marks the first unmarked 0 or 1 in each streak with an X,
until it reaches a blank.  If at the end, its all A or B (plus a Q|Z)
this means N==1 and it accepts.  If first char is Blank, Epsilon,
So accept.  If all 0 or 1, its all of one type, accept.

Code will keep marking first unmarked 0 or 1 with X until the end.
It will check for equality as it travels left back to the beginning.
If at the end, the first char to the right is an A|B, all need to be A|B.
If at the end, and the first char to the left is X, then there cannot be
any 0|1 left.
_________________________________________
6,0,6,0,<
6,1,6,1,<
6,A,6,A,<
6,B,6,B,<
6,Q,7,Q,>
6,Z,8,Z,>
7,0,11,X,>
7,A,9,A,>
7,X,7,X,>
8,B,10,B,>
8,1,12,X,>
8,X,8,X,>
9,B,10,B,>
9,_,H,_,<
10,A,9,A,>
10,_,H,_,<
11,0,11,0,>
11,A,13,A,>
12,1,12,1,>
12,B,14,B,>
13,X,13,X,>
13,1,15,X,>
13,_,17,_,<
14,X,14,X,>
14,0,16,X,>
14,_,17,_,<
15,1,15,1,>
15,B,14,B,>
15,_,17,_,<
16,0,16,0,>
16,A,13,A,>
16,_,17,_,<
17,0,18,0,<
17,1,18,1,<
17,A,19,A,<
17,B,19,B,<
17,X,20,X,<
18,A,18,A,<
18,B,18,B,<
18,X,18,X,<
18,1,18,1,<
18,0,18,0,<
18,Q,7,Q,>
18,Z,8,Z,>
19,A,19,A,<
19,B,19,B,<
19,Q,H,Q,>
19,Z,H,Z,>
20,X,20,X,<
20,B,20,B,<
20,A,20,A,<
20,Q,H,Q,>
20,Z,H,Z,>