Algoritmus: meghatározott adatokon jól meghatározott lépések végrehajtása.
Feladat: adott adatok alapján új adatok meghatározása, amelyek valamilyen matematikailag leirható formának eleget teszünk

Az algoritmus tulajdonságai
• Végesség: Az algoritmus futása véges sok lépés után befejezodik. Esetünkben
r kisebb mint n, azaz n értéke folyamatosan csökken az algoritmus
végrehajtása során, és pozitív egészek egyre fogyó sorozata egyszer véget
ér.
• Meghatározottság: Az algoritmus minden egyes lépésének pontosan definiáltnak
kell lennie. Miután az élonyelvi megfogalmazás esetenként nem
egyértelmu, használhatunk különféle programnyelveket, ahol mindennek
pontos, egyértelmuen definiált jelentése van...
• Bemenet/Input: Az algoritmus vagy igényel vagy sem olyan adatokat, amelyeket
a végrehajtása el?ott meg kell adni. Az input mindig bizonyos
meghatározott halmazból kerülhet ki, esetünkben m és n pozitív egész
szám.
• Kimenet/Output: Az algoritmushoz egy vagy több output tartozhat, amelyek
meghatározott kapcsolatban állnak az inputtal. Esetünkben az output
az n utolsó értéke lesz, ami az input értékeknek legnagyobb közös
osztója.
• Elvégezhetoség: Elvárjuk, hogy az algoritmust végre lehessen hajtani, azaz
a végrehajtható utasítások elég egyszeruek ahhoz, hogy egy ember papírral
és ceruzával véges ido alatt pontosan végrehajthassa. Például a végtelen
tizedestörtek osztása nem ilyen, mert ez végtelen lépéssorozat.
• Univerzális: Az algoritmusnak muködnie kell tetszoleges (a feltételeknek
megfelelo) bemeneti értékek esetén. Az euklidészi algoritmusunk természetesen
tetszoleges pozitív számpárnák meghatározza a legnagyobb
közös osztóját.
Ezek alapján tekinthetjük az algoritmust egy számolási probléma megoldásának. A
probléma megfogalmazása általánosságban meghatározza a kívánt bemenet/kimenet
kapcsolatot. Az algoritmus egy specifikus számolási eljárást ír le ennek a kapcsolatnak
eléréséhez. A legnagyobb közös osztó problémájának egy esete a 119,
544 számpár. Egy eset az összes olyan bement?o adatból áll, amelyek szükségesek
a probléma megoldásának számításához. Egy algoritmust helyesnek nevezünk, ha
minden konkrét bemenetre helyes kimenetet ad és megáll.

Turing koncepciója

Külso adat és tárolóterület: végtelen szalag, amelynek egymás után cellái vannak, amelyek vagy üresek, vagy jelöltek.
A gép egyszere egy cellával foglalkozik (Az író/olvasó feje egy cellán áll)
A szalagon tud jobbra-balra lépni, tud jelet olvasni, törölni és írni. Az „üres" szalagon nincs jel. A jelet a továbbiakban 1-gyel, az üres cellát 0-val jelöljük.
A bevitel, a számítás és a kivitel minden konkrét esetben véges marad, ezen túl a szalag üres.(0)
A gép belso állapotait számozzuk meg 0,1,2,...
A gép muködését megadja egy explicit helyettesítési táblázat. Állapot, bemenet --> Állapot, kimenet, fejmozgás

TURING gep: Tm ={A; S; f; k} formalis negyes, ahol
A: egy veges halmaz, a Turing gep abc-je, amely tartalmaz egy specialis jelet, a blank jelet
S: egy veges halmaz, a Turing gep allapotainak halmaza
f: egy lekepezes, amely a A £ S halmaz bizonyos elemeihez a A £ S £M halmaz elemeit
rendeli, ahol M = fÃ; !; "g
k: S a gep kezdoallapota
Mukodese: a gep rendelkezik egy ket iranyban vegtelen szalaggal, amely kockakra (mezokre) van
osztva. Minden mezobe az abc egy jele irhato, amelyet a gep iro/olvaso fejevel irhat
es olvashat. Az iro/olvaso fej a szalag hosszaban mozoghat. Kezdetben a szalagon egy
folytonos szoveg talalhato, az iro/olvaso fej a szoveg legbaloldalibb karakterenel all es a
gep a k kezdoallapotban van. Ezutan a karaktert beolvasva az f lekepezesnek megfeleloen
egy uj jelet ir a szalagra, uj allapotba kerul es elmozdul jobbra, vagy balra, vagy helyben
marad. Megall, ha az f lekepezes nincs definialva.
Ekkor azt mondjuk, hogy az input szoveget leforditotta arra a szovegre, amely megallaskor
a szalag tartalma.

Markov algoritmus: modellje az algoritmusnak. Szavakat konstruálnak a szavak bizonyos részének kicserélésével. Ekvivalens a Turing-géppel.

RAM-gép: Ekvivalens a Turing-géppel. (Ram géppel szimulálható a T.gép muködése és fordítva is igaz.)
Ram?Tg. : Ram memóriája lesz a Tg szalagja, Ram számol a memóriában, mintha a Tg számolna a szalagján.
Egy irányban végtelen a szalag. Minden második cellát vesszük. Párosak az egyik irányba, páratlanok a másik irányba.
Tg?Ram.: kombináltabb Tgép, egy szó írható a szalagjára. A Ram celláira akármekkora szám írható. Tgép-nél elválasztó jeleket vezetünk
be, ezek adják a Ram celláját.