V prvej kapitole kurzu o strojovom a hĺbkovom učení sme sa stručne dotkli Turingovho stroja. Tento koncept, ktorý položil základy umelej inteligencie a strojového učenia, opísal britský matematický génius Alan Turing (1912–1954) už v roku 1936.
Alan Turing, bývalý študent univerzity v Cambridgei, si získal slávu tým, že počas druhej svetovej vojny dešifroval nacistické kódy. Ani tento úspech ho však neochránil pred tým, aby bol v roku 1952 odsúdený na chemickú kastráciu za svoju homosexualitu, ktorá bola v povojnovej Anglicku považovaná za trestný čin. Turing bol napokon v roku 2014 – šesťdesiat rokov po svojej smrti – omilostený kráľovnou Alžbetou II. na žiadosť skupiny jedenástich britských vedcov vrátane Stephena Hawkinga.
Zaujalo vás to? Chcete vedieť viac o tom, ako tento slávny stroj funguje? Poďme sa na to pozrieť!
Teoretický princíp
Turingov stroj je abstraktný koncept, ktorý Turing opísal vo svojom článku z roku 1936 „On Computable Numbers, With An Application to the Entscheidungsproblem“. Čo je na tomto „stroji“ revolučné? Ide o univerzálny výpočtový model – dokáže vykonávať rovnaké výpočty ako fyzický počítač.
Hoci Turing tento stroj počas svojho života nikdy nepostavil, je teoreticky možné ho skonštruovať. Ak vás to zaujíma, na internete nájdete množstvo videí, ktoré ukazujú, ako na to. My si zatiaľ princíp fungovania opíšeme slovami.
Ako funguje Turingov stroj
Turingov stroj pozostáva z týchto základných komponentov:
- Páska: Je rozdelená na bunky, pričom každá bunka obsahuje symbol (číslicu, písmeno alebo prázdny symbol pre nevyplnené bunky). Teoreticky je páska nekonečná, ale v praxi môže byť kruhová alebo konečná.
- Hlavička na čítanie/zapisovanie: Táto hlavička dokáže vykonávať tri úkony: pohybovať sa doľava alebo doprava po páske, čítať symboly a zapisovať ich.
- Stavový register: Stroj môže byť v rôznych stavoch – počiatočný stav (pred začatím výpočtu), aktuálny stav (hlavička je umiestnená nad konkrétnou bunkou) a koncový stav (po dokončení výpočtu). Register uchováva informácie o aktuálnom stave stroja.
- Tabuľka akcií (prechodov): Ide o súbor inštrukcií programu. Na základe symbolu prečítaného hlavičkou a aktuálneho stavu stroja určuje, aká akcia sa má vykonať. Stroj dostane tri informácie: aký symbol má zapísať, ktorým smerom sa má pohnúť a do akého nového stavu má prejsť. Ak nenájde akciu pre danú kombináciu, zastaví sa.
Jednoduchý príklad na pochopenie
Predstavme si konkrétny príklad: máme Turingov stroj s konečnou páskou, ktorej bunky môžu obsahovať tri hodnoty – 0, 1 alebo prázdnu bunku. Naším cieľom je premeniť všetky 0 na 1, pričom 1 ostávajú nezmenené a prázdne bunky zostávajú prázdne.
- Stavy stroja:
- Stav 1: Hlavička sa pohybuje doprava, kým nenájde 0 alebo 1, potom prejde do stavu 2.
- Stav 2: Ak číta 0, zapíše 1. Ak číta 1, nič nezapíše a pohne sa doprava. Ak číta prázdnu bunku, ukončí sekvenciu a prejde do finálneho stavu.
- Finálny stav: Hlavička zastaví svoju činnosť.
Výsledok: Všetky 0 na páske sú premenené na 1, a to len pomocou pásky, čítacej hlavičky a súboru inštrukcií!
Záver
Tento jednoduchý príklad ukazuje princíp programu založeného na Turingovom stroji. Avšak, Turingov stroj dokáže omnoho viac – sčítanie, odčítanie, detekciu palindrómov či generovanie číselných sekvencií. Teoreticky by sme – s veľkou dávkou trpezlivosti – mohli replikovať všetky existujúce algoritmy.
Turingov stroj je skutočne fascinujúci, rovnako ako génius jeho tvorcu.
Zdroje: