:
:  Turing machine program that implements
:  Euclid's algorithm. Numbers are represented on
:  tape as a series of 1s, where 5 would appear
:  as 11111. The two numbers are separated by a 0.
:
:  Adapted from Roger Penrose's book:
:     The Emperor's New Mind
:

:  Use these for test tapes:
:  001111111111111110111111111100
:   Answer should be 11111
:
:  1111110111111111111111
:   Answer should be 111
:

0:0:0:0:R
0:1:1:1:L
1:0 :10:1:R
1:1:1:1:L
10:0 :1010:0:R
10:1:11:0:R
11:0 :100:0:R
11:1:11:1:R
100:0 :100:0:R
100:1:101:0:R
101:0 :111:0:L
101:1:110:1:L
110:0 :110:0:L
110:1:1:1:L
111:0 :111:0:L
111:1:1000:1:L
1000:0 :1001:0:L
1000:1:1000:1:L
1001:0 :10:0:R
1001:1:1:1:L
1010:0 :halt:0:S
1010:1:1010:1:R