Turingovy a RAM stroje
Ve snaze definovat algoritmus si vymysleli matematici Turingovy a RAM stroje... Jde o dva různé přístupy (modely) univerzálních počítačů/programovacích jazyků/algoritmů. Jinými slovy těmito stroji lze definovat a provést libovolný algoritmus.
Model Turingova stroje byl popsán dříve, ještě před rozmachem počítačů, proto se od reálného počítače (programování) podstatně liší, na rozdíl od RAM stroje. Turing například pracuje s celou abecedou zatímco RAM (podobně jako počítač) s čísly.
Turingovy stroje
Turingův stroj je podobný konečnému automatu, ale má oboustranně nekonečnou pásku, místo symbolu ε pro prázdné znaky se používá ▢, hlava je čtecí i zapisovací a pohybuje se po pásce v obou směrech.
Turingův stoj definujeme seznamem přechodových funkcí δ, které tvoří instrukce algoritmu. Přechodová funkce má tvar:
δ(stav, znak) = (novy_stav, novy_znak, posun)
Na obrázku vlevo vidíme Turingův stroj realizující algoritmus znázorněný modrým automatem (zapis u hran znamená - čtený_znak, psaný_znak, posunu). Přechodové funkce by vypadaly následovně: δ1(S1,a)=(S1,b,+), δ2(S1,b)=(S1,a,+), δ3(S1,▢) = (S2,▢, 0).
Zobrazeny algoritmus invertuje slovo na pásce. Ve stavu S1, přepisuje 'a' na 'b' a naopak, a posunuje se doprava (+). Jakmile je slovo přečtené (narazí na prázdný znak ▢), přechází do koncového stavu S2 a dál se neposouvá.
RAM stroje
RAM stroje už vycházejí ze skutečných počítačů. RAM stroje mají paměť, pracují s přirozenými čísly (1,2,3,...) a instrukce se podobají klasickýcm příkazům. Buňky paměti jsou oadresovány čísly 0 - ∞, přičemž první registr [0] se bere jako pracovní registr a registr [1] je indexový registr (pouzívá se u příkazu s hvězdičkou).
Na obrázku je znázorněný RAM stroj s vnitřním kodem, pro výpočet průměru ze sekvence čísle ukončených nulou.
Instrukce turingova stroje:
Čísla (operátory) za příkazy mají následující významy:
| op | vysvětlení |
|---|---|
| =6 |
Hodnota 6 |
| 6 |
Hodnota v registru [6] Pro podmínky (JZERO, JGTZ) a JUMP je to číslo řádku |
| *6 |
Hodnota registru [IR], Toho se využívá při procházení poli. |
V následující tabulce jsou vypsány instrukce RAM stroje. Je-li za instrukcí op viz předchozí tabulka, r znamená číslo řádku a není li uvedeno nic, používá se příkaz samostatně.
| instrukce | vysvětlení |
|---|---|
| READ |
do pracovního registru se načte vstup a hlava se posune [0]=IN |
| WRITE |
na vystup se vypíše PR OUT=[0] |
|
LOAD op |
do pracovního registru se načte hodnota dána operátorem [0]=op |
| STORE op* |
pracovní registr se zapíše do registru daného operátorem => * op nemůže být ve tvaru =cislo op=[0] |
| ADD op |
sčítání - k prac.registru se přičte hodnota dana operatorem [0]=[0]+op |
| SUB op |
odčítání - od prac.registru se odečte hodnota dana operatorem [0]=[0]-op |
| MUL op |
násobení - prac.registr se vynásobí hodnotou danou operatorem [0]=[0]*op |
| DIV op |
celočíselné dělení - prac.registr se vydělí hodnotou danou operatorem [0]=[0]/op |
| JUMP r |
skok na řádek r |
| JZERO r |
rovno nule - je-li prac.registr. roven nule, pokračuje kod na řádku r |
| JGTZ r |
kladné - je-li prac.registr. větší než nula, pokračuje kod na řádku r |
| HALT r |
korektní ukončení programu |
Pěkná animace RAM stroje.