Primitívny Turingov stroj

Na jednom z predmetových cvičení na univerzite som dostal za úlohu vypracovať zadanie na tému primitívneho Turingového stroja. Nikdy predtím so o Turingovom stroji nepočul a vôbec som nevedel ako mám postupovať. Zadanie nevyžadovalo znalosť programovania, preto jeho vypracovanie nie je vo forme kódu ale vo forme písaných inštrukcii.

Zadanie príkladu:

Popíšte konštrukciu kontrolného kódu, ktorý akceptuje reťazec tvaru:
X 0…(nx0)…0$1……(2nx1)……1 X (obrázok časť A) pre n>1 pomocou inštrukcii l if sig then (sig’, o, l).
{Inštrukciu môžeme prečítať ako: Ak sme na mieste inštrukcie l, ak prehliadané políčko obsahuje sig, potom prepíšeme sig na sig’, posunieme sa o o políčko ( do ľava = -1, stoj na pozícii = 00 , do prava = +1 ) a vykonáme (nasledujúcu) inštrukciu l. Vysvetlenie: X – hraničný znak, $ – deliaci znak, 0 – nula, 1 – jednotka}

Popis riešenia:

Jedná sa o primitívny Turingov stroj. Čítacia hlava sa pohybuje z ľava do prava a naspäť (obrázok časť A). Začíname na mieste prvej 0 z ľava a postupujeme podľa inštrukcii (hore). Pohybujeme sa do prava (obrázok časť B), až dôjdeme na X (obrázok časť C) a pohybujeme sa naspäť (obrázok časť D). To opakujeme toľkokrát, koľko je treba (obrázok časť F). Výsledkom kontrolného kódu bude buď vyhovujúci počet n na obidvoch stranách (nx0=2nx1) alebo nevyhovujúci stav (nevyhovujúce prípady).

Možné koncové prípady:

Začiatok:
X 0…0$1……1 X – Na jednej, aj druhej strane je určitý počet 0 a 1tiek.
Koniec – vyhovujúce vyhodnotenie:
X X…X$X……X X – Na oboch stranách bol rovnaký počet jednotiek a núl.
Koniec – nevyhovujúce vyhodnotenie:
a) X X…X0$X……X X
– Na ľavej strane bolo o jednu nulu viac ako jednotiek na pravej.
b) X X…X…00$X……X X
– Na ľavej srane bolo o niekoľko núl viac ako jednotiek na pravej.
c) X X…X$1X……X X
– Na pravej strane bolo o jednu jedntku viac ako na ľavej núl.
d) X X…X$11..X……X X
– Na pravej strane bolo o niekoľko jednotiek viac ako na ľavej strane núl.

Riešenie

Upozornenie :  Je dôležité uvedomiť si, čo robia inštrukcie (italics v zadaní príkladu).

01. if 0 than (X,+1,02.)
--  Prepíšeme 0 na X (hraničný znak)
02. if 0 than (0,+1,02.)
--  Cyklus až kým sa nedôjde po $
03. if $ than ($,+1,04.)
04. if 1 than (1,+1,04.)

--  Cyklus až kým sa nedôjde po X
05. if X than (X,-1,06.)
06. if 1 than (X,-1,07.)
--  Prepíšeme 1 na X (hraničný znak)
07. if 1 than (X,-1,08.)
--  Prepíšeme 1 na X (hraničný znak)
08. if 1 than (1,-1,08.)
--  Cyklus až kým sa nedôjde po $
09. if $ than ($,-1,10.)
10. if 0 than (0,-1,10.)
--  Cyklus až kým sa nedôjde po X
11. if X than (X,+1,12.)
========================
--  Koniec jednej otočky.

12. if 0 than (0,00,17.)
========================
--  Poistka. Kedže inštrukcie sa spracúvajú v smere zhora nadol, ak by tu nebol 12. bod, došlo by k tomu, že čítacia hlava sa posunie za znak $ a tam buď vyhodnotí stav alebo sa zasekne. To by potom odporovalo inštrukcii 17., ktorá je ešte pred $ znakom. Preto inštrukcia 12. je taká poistka, že pred $ nie je 0. Ak pred $ nie je nula, dostávame sa do jedného z možných koncových vyhodnotení.

13. if $ than ($,+1,14.)
14. if X than (X,00,23.)
========================
--  Vyhovujuce vyhodnotenie X X...X$X......X X, výsledok vyhovuje (nx0=2nx1)
15. if $ than ($,+1,16.)
16. if 1 than (1,00,22.)
========================
-- &nbsp;Nevyhovujúce vyhodnotenie c) X X...X$1X......X X a d) X X...X$11..X......X X. Na pravej strane je o niekoľko 1 viac ako na ľavej n 0liek. (<em>Na rozdiel od nevyhovujúceho vyhodnotenia a) a b) keď narazíme už na prvú 1tku vieme, že nevyhovuje. Pri a) b) môže byť najskôr viac 0iek a robí sa cyklus. Len tak informatívne ...</em>)

17. if 0 than (X,+1,18.)
18. if 0 than (0,+1,18.)
-- &nbsp;Cyklus až kým sa nedôjde po $
19. if $ than ($,+1,20.)
20. if X than (X,00,22.)
========================
-- &nbsp;Nevyhovujúce vyhodnotenie a) X X...X0$X......X X a b) X X...X...00$X......X X. Na ľavej strane je o niekoľko 0 viac ako na pravej xn 1tiek.

21. if 1 than (1,00,04.)
========================
-- &nbsp;Sme za $ znakom a môžeme pokračujeme odznova...

22. RETURN
23. ACCEPT

Update 18. 12. 2010

– Zmenil som obrázok, pridal som časť F) a následne dosadil do textu.
– Číslo 21. malo tvar “21. if 1 than (X,+1,04.)” a teda, po deliacom znaku $ menilo prvú 1 na X. To je samozrejme zle. Teraz ma tvar “if 1 than (1,00,04.)”. Tento tvar vyjadruje, že keď za $ znakom ide 1, možeme to chápať už ako časť nového cyklu a pokračovať od bodu 04.

Update 01. 05. 2011

Dozvedel som sa, že Alan Turing bol najväčší odborník na Počítačovú vedu v ľudskej histórii. Podieľal sa napr. na dešifrovaní a rozlúštení kódu Enigmi. Tento algoritmus som vytvoril bez znalosti pozadia Alana Turinga a Turingovho stroja (len na základe základných inštrukcii). Z letmého pohľadu na anglickú wikipédiu o Turingovom stroji sa môj algoritmus zdá správny. Odporúčam však radšej porovnať ho s obsahom wikipédie lepšie.

Update 05. 12. 2015

Pre pochopenie významu Alana Turinga pre súčastnú históriu odporúčam pozrieť si film v anglickom názve – The Imitation Game.

Kľúčové slová

Alan Turing, inštrukcie turingovho stroja, primitívny turingov stroj, Turing machine, Turingov stroj, Turing, kódovanie, algoritmus, kryptografia, matematika, computer science, počítačová veda