Turing gép
Az algoritmus fogalmainak egyik finomítását a Post és az A. Turing egymástól függetlenül 1936-1937-ben adta meg. Fő elképzelésük az volt, hogy az algoritmikus folyamatok olyan folyamatok, amelyeket egy megfelelően rendezett "gép" képes megvalósítani. Leírt hipotetikus (feltételes) eszközöket, amelyeket "Post Machine" (MP) és "Turing Machine" (MT) neveztek. Mivel sok közös vonás van, később Turing gépekként ismertek.
A Turing gép az alábbi részekből áll:
1. Egy információs szalag, amely a gép végtelen memóriáját képviseli. Ez egy mágneses vagy papír végtelen szalag, amelyet cellákra osztanak. Minden cellában csak egy karaktert helyezhet el, beleértve a nulla értéket is.
2. Az olvasófej - érzékeny különleges elem, amely képes a sejtek tartalmának megtekintésére. A szalag mozoghat a fején úgy, hogy minden pillanatban a fej egy cellára néz.
3. A vezérlőegység (CU), amely bármikor bizonyos állapotban van. Az államok száma véges. Az egyik állam az utolsó állapot.
Az 1, S2, ..., Sm> információs szalagon rögzített szimbólumok halmaza a MT ábécéit alkotja.
Ebben az esetben az S1 egy üres karakter.
Az államok halmaza, amelyben a CW található, 1, q2, ..., qn> jelöli. Az államok közül az egyik jelentős lesz, ahol az MT leáll.
Ezenkívül a CU három parancsot hoz létre a szalag mozgatásához: P, L, H, ahol
- a jobb oldali cellát felmérni;
A - nézze meg a cellát a bal mellett;
H - továbbra is vizsgálja ugyanazt a cella.
A gép diszkrét időben működik. Az MT minden egyes pillanatában, az qi állapotában. Megjeleníti a Sk szimbólumot a szalagon. majd az állam qj. helyettesíti a Sk-ot a Sl jelzéssel, és mozgatja a szalagot (vagy nem) egy cellára.
Az olvasófej és a vezérlőegység logikai blokkot képez. amely egy (2,3) - pólusú.
qi Sk qj Sl Π (A, H)
Így az MT parancsot öt szimbólum adja: qi. Sk. qj, Sl. P, és maga az LB lényegében véges automata.
Az MT szerkezete a következő:
Q - a cella tárolja az állapot szimbólumot, és P - a cella - a shift szimbólum. Ezek a jelek késleltetik a következő intézkedés megkezdéséig.
Mivel az eredeti információt a szalagot lehet etetni minden véges ábécé sorrendben külső U. Amennyiben egy véges számú órajel ciklus MT megáll etetés jel, hogy hagyja abba, és kiderül a szalagon információk B, akkor azt mondjuk, hogy a gép vonatkozik az U sorozatot, és átalakítja azt sorozata B.
Ha egy stop és stop jelet soha nem fogadunk, az MTN azt mondja, hogy alkalmazható az U sorozatra.
Tekintsük az MT működését két szám hozzáadásával, amelyet egységcsoportként fogunk képviselni.
A külső ábécé a szimbólumokat fogja tartalmazni :, ahol Ù üres karakter.
A belső ábécé négy szimbólumból állhat: 1. q2. q3.>, ahol a q1 jel a kezdeti állapotot jelöli, a. - a végső állapot.
Hagyja, hogy a kezdeti információk a kazettára íródjanak: