# gcd3.tur: Beregn største fælles divisor.
#
# Med input "a^m#a^n" vil maskinen stoppe med a^gcd(m, n) på båndet.
#
# Martin Geisler <mgeisler@mgeisler.net>


0 a a r 0 Søg forbi $a$.
0 b b r 0 Søg forbi $b$.
0 # # r 10 Begynd at danne par.

10 a b l 20 Markér $a$ som $b$, find makker til venstre.
10 b b r 11 Søg forbi $b$.
10 # # r 10 Søg forbi $\#$.
10 _ _ l 12 Fandt \spc. Båndet er nu $a^i\#$.

11 a b l 20 Markér $a$ som $b$, find makker til venstre.
11 b b r 11 Søg forbi $b$.
11 # # r 11 Søg forbi $\#$.
11 _ _ l 15 Fandt højre kant. Båndet er nu $a^ib^j\#b^j$ med $i \geq 0$ og $j \geq 1$.

12 # _ l 50 Fjern $\#$ fra $a^i\#$ og stop.


15 b _ l 15 Fjern $b$.
15 # a l 16 Fjern $\#$.

16 b a l 16 Lav $b$ om til $a$.
16 a a r 17 Fandt sidste $a$ i $a^ib^j\#b^j$.
16 _ _ r 18 Fandt \spc, det svarer til $i=0$ i $a^ib^j\#b^j$.

17 a # r 10 Lav ny midte hér.

18 a _ r 50 Fjern $a$ der stammer fra $\#$ og stop.


20 b b l 20 Søg forbi $b$.
20 # # l 21 Søg forbi $\#$ og husk dette.

21 a b r 10 Markér $a$ som $b$, find makker til højre.
21 b b l 22 Søg forbi $b$.
21 _ _ r 23 Fandt venstre kant. Båndet er nu $\#ba^i$.

22 a b r 10 Markér $a$ som $b$, find makker til højre.
22 b b l 22 Søg forbi $b$.
22 _ _ r 25 Fandt venstre kant. Båndet er nu $b^j\#b^{j+1}a^i$ med $i \geq 0$ og $j \geq 1$.

23 # _ r 23 Fjern $\#$ fra $\#b$.
23 b a r 50 Lav eneste $b$ om til $a$ i $b$, ryk så til venstre og stop.


25 b _ r 25 Fjern $b$.
25 # a r 26 Lav $\#$ om til $a$.

26 b a r 26 Lav $b$ om til $a$.
26 a a l 27 Fandt først $a$ i $b^j\#b^{j+1}a^i$.
26 _ _ l 27 Fandt et \spc, det svarer til $i=0$ i $b^j\#b^{j+1}a^i$.

27 a a l 28 Ryk til venstre igen.
28 a # r 10 Lav ny midte hér.