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}

Algoritmus Turingovho stroja

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

This entry was posted in Škola and tagged , . Bookmark the permalink.

2 Responses to Primitívny Turingov stroj

  1. kryspincholera says:

    06. if 1 than (X,-1,07.)
    — Prepíšeme 0 na X (hraničný znak)
    07. if 1 than (X,-1,08.)
    — Prepíšeme 0 na X (hraničný znak)

    Nema byt: prepiseme 1 na X ?

Leave a Reply

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.