(i) Bereken de ggd van 10941738641570527421809707322040357612003732945449205990913842131476349984288934784717997257891267332497625752899781833797076537244027146743531593354333897 en 1211474421143664613436133434296611353175315483933034705156062395796331907364046202035450580497701265308212112983319034224374442057337862086144312401934108158313895330097205941837731585600087701972973718095155156213887479729636223707
Dan vragen die het construeren van een Turing machine inhouden. De machine wordt beschreven door een tabel waar voor elke toestand beschreven wordt wat er gebeurt als er een 0 op de band onder de leeskop staat, en wat als het een 1 is. "Wat er gebeurt" is een paar: (actie,nieuwe toestand), waarbij actie 0, 1, L of R is. (Schrijf een 0, schrijf een 1, ga naar links of ga naar rechts.) Lege band leest als 0. De machine wordt gestart met de leeskop op de meest linkse plaats van de invoer. Toestand 1 is de starttoestand. Toestand 0 is de stoptoestand.
(ii) Schrijf een machine die kan optellen (Invoer op de band: twee getallen in het 1-tallig stelsel gescheiden door een 0. [Dus: het getal 7 wordt geschreven als 1111111.] Gewenste uitvoer: diezelfde twee getallen, gevolgd door hun som.
(iii) Schrijf een machine die kan vermenigvuldigen.
(i) Recentelijk werd een groot getal (dat bekend stond als RSA-155) op het CWI gefactoriseerd in a*b. De twee getallen hier zijn x = a*b en y = a*a*a. De g.g.d. a is gelijk aan 106603488380168454820927220360012878679207958575989291522270608237193062808643 en kon gevonden worden door in Mathematica naar GCD[x,y] te vragen. Deze factorisatie was een kleine sensatie die alle kranten haalde: de veiligheid van sommige betalingssystemen berust op het feit dat het heel moeilijk is om zulke grote getallen in factoren te ontbinden.
(ii) Een optelmachine: Start: _A0B0... Stop: A0B_0C0... waarbij A, B en C rijen enen zijn ter lengte a, b en c, en c = a+b. Het teken _ geeft aan dat de leeskop boven het volgende symbool staat.
1: R,9 0,2 2: R,3 R,1 3: R,4 R,3 4: R,5 R,4 5: 1,6 R,5 6: L,7 L,6 7: L,8 L,7 8: 1,2 L,8 9: 0,0 0,10 10: R,11 R,9 11: R,12 R,11 12: 1,13 R,12 13: L,14 L,13 14: 1,10 L,14
(iii) Een vermenigvuldigmachine: Start: _A0B0... Stop: A_0B0C0... waarbij A, B en C rijen enen zijn ter lengte a, b en c, en c = a*b.
1: 0,0 0,2 2: R,3 R,1 3: R,4 R,3 4: L,10 0,5 5: R,6 R,4 6: R,7 R,6 7: 1,8 R,7 8: L,9 L,8 9: 1,5 L,9 10: L,11 L,10 11: 1,2 L,11