3662 Gyakorlatok a matematikai logika és algoritmusok elmélete - 3. oldal

Turing-gép - ez egy idealizált matematikai modelljét számítástechnikai eszköz.

Turing-gép T teljesen határozzák meg:

- programot, hogy egy parancsokat.

A alkotóeleme a Turing gép:

- szalag kellően hosszú, amely a sejtek;

- egy mutatót, amely jelzi az aktuális cella a szalag; A mutató megváltoztathatja a karakter az aktuális cella és mozgassa szerint egy előre meghatározott parancs

- belső memória, amely tartalmazza a jelenlegi állapotában a belső qi gép.

Csapat Turing-gép általános alakja:

ahol qi - a belső állapotát a gép abban a pillanatban; ai - jelképe az adott cellában a szalag; qj - belső állapotát a következő pillanatban; aj - a karakter, amely megváltoztatja szimbólum ai; D = - mutató mozgás iránya, ahol R - jobb, L - bal, S - a helyükön maradnak (általában csökkentette S).

Része a csapat «®» szimbólum az úgynevezett baloldali része a csapatnak, és miután «®» szimbólum - jobb.

Az utolsó sor utasítást minősül programot.

A belső állapot q1 kell tekinteni a kezdeti és a végső állapotban q0 venni. Amint a Turing-gép mozog az állami q0. parancs végrehajtása befejeződik.

Turing-gép működési idő, mely még ma is, hogy diszkrét és pillanatok vannak számozva 1, 2, 3, .... Bármikor csak egy parancsot.

Jellemzően az ábécé A két karakter:

ahol 0 - null karaktert. A sejt, amely felvett egy null karakter üresnek.

Gép szó sorozata nem üres karakter a szalagon. Szavak elválasztva egy vagy több üres karaktert, amely jelentős ajánlatot.

Az alábbi példa a szalagon rögzített szót álló négy szimbólum az ábécé A = 1; a2; a3>. A gép az állam q1. és a jelenlegi az első cella (mutató által pozíció).

Az állam a RAM m (k) magában a tartalmát a sejtek a szalag, a helyzet a mutatót, és az értéke a belső állapotát qi. Hatása alatt a program megváltoztatja az állam a gép:

m (0) ® m (1) ® ... ® m (p).

Mi határozza meg a számítás numerikus funkciókat egy Turing-gép. Kevesebb numerikus funkciókat értünk egy függvény, amelynek értékei és az értékek az érvek nem negatív egész számok, amelyek kódolják a következők. A számú M kerül meghatározásra egy sor M + 1 egységet, amelyet jelölt 1 M + 1. Például:

0 lesz beállítva 1

A Turing-gép az úgynevezett univerzális, ha tudja, bizonyos kezdeti bemenő adatok kiszámításához minden olyan funkciót, amely kiszámítható a Turing-gép.

Ha a gép elkezdett dolgozni néhány szót (ek) jön a végső állapotban q0. ez az úgynevezett alkalmazható a szót (ok) és a munkája eredményét kell tekinteni a szó (ek), amely rögzíti a szalagot a végső állapot. Ha a gép nem lép a végső állapot, akkor azt mondják, hogy nem alkalmazható ez a szó (ek) és a munkája eredményét nem meghatározott.

Példa 2.4. Turing-gép megépítésére ábécé A =, amely átalakítja a szót x1 x2 ... xn szóval x2 x3 ... xn x1. ahol xi = és a maradék sejteket a szalagon üres lesz.

Határozat. cél a program a következő parancsokat: