Turing-gép - studopediya
A Turing-gép olyan, mint a Post gép, de egy kicsit eltér.
Turing-gép (MT) áll számítva a szalagot (cellákra osztjuk, és balról, de nem a jobb oldalon), az olvasási és írási fejek, szalagos meghajtó és működtető hajtómű, amely lehet az egyik diszkrét állapotok qo, q1. qs tartozó véges számú (betűrendben belső állapotok). Ebben a kezdeti állapotban qo hívják.
Működés MT (egy működő ábécé a0. A1. AT, és kijelenti, q0. Q1. Qs) egy olyan Turing-gép asztalra. Ez a táblázat egy olyan mátrix, négy oszlopot és (s + 1) (t + 1) sorokban. Minden sor a formája
Itt kombinálásával elem vij kijelölt ábécé 0. a1. AT> és több követelmények szalagos meghajtó: l - bal mozog a szalag, r - mozog a szalag a jobb, s - állítsa le a gépet; vij - hatása TM amely vagy belépő a sejt szalag ábécé a0 jelképe. a1. AT, vagy a fej mozgását, vagy megáll az autó; qij a soron következő állapot.
MT szerint működik, az alábbi szabályok: ha az MT képes Qi, a fej leolvassa a 0 a termelési cellában. Hagyja, hogy a vonal qi aj vij qij kiindulva qi karakter. aj. Ez csak egyszer fordul elő a táblázatban. Ha vij - levél ábécé munkás, a fej törli a tartalmát a munka sejt, és tolja vissza a levelet. Ha vij - R L vagy parancsot a szalagos meghajtó, a szalag van tolva az egyik cellából a jobbra vagy balra (ha nincs kimenet a bal széle a szalag) rendre. Ha vij = s, akkor van egy gép megáll.
Turing gép megkezdi egy bizonyos kezdeti konfigurációt, beleértve a kezdeti állapot (általában Q0) és a helyzet az író-olvasó fej fölött egy adott szalagos egység, amely egy, a működési szimbólumok az ábécé A.
Megjegyezzük, hogy a jelenléte a különböző karakterek az ábécé MT lehetővé vált a szalagon képviseli tetszőleges szöveget és numerikus információt egy ellenőrző központba MT átmenetek különböző állapotú Turing gép modell tárolására közbenső művelet eredménye. Táblázat, meghatározzák a MT nem a szó szoros értelmében a szó programot (annak előírásai nem végzik egymás után egymás után, és írja le a karakterkészlet konverzió néhány szöveget a szalag). Táblázat MT gyakran nevezik ábra egy Turing-gép, vagy egyszerűen azonosítani a Turing-gép, mindaddig, amíg annak szerkezetét és működését az elv ismert.
Tekintsük a példát néhány áramkörök a Turing-gép.
1. Az algoritmus az addíciós egység az n szám a tízes számrendszerben. Decimális jelölés adott szám n (azaz n egy természetes szám képviselet decimális számrendszer); megkapja a szükséges számú tizedespontokkal n + 1.
Nyilvánvaló, hogy a külső ábécé MT kell állnia tízjegyűekig 0,1,2,3,4,5,6,7,8,9, és a szóköz karakter _. Ezek a számok vannak írva egy sejtenként (a sorban nélkül rések).
Elegendő a két belső állapotát a gépet: a Q1 és Q2.
Tegyük fel, hogy a kezdeti időben a fej egyik számjegyét, és a gép az állam q1. Ezután a problémát meg lehet oldani két szakaszban történik. Head mozgását a számjegy egységek száma (Q1 belső állapotát), és cseréje a számjegy egy nagyméretű (figyelembe véve a transzfer 1 a következő mentesítési, ha a 9 eszköz, egy belső állapota Q2 megfelelő MT séma formájában
2. Vedd algoritmus számokat a tízes számrendszerben.
Adott véges sorozata jelek rögzített kazettára sorban sejtek nem hiányos. Megköveteli írt tizedes címkék száma számít címkén).
A lényege az algoritmus állhat az a tény, hogy számos 0 a szalagon elején a gép működését, a gép hozzáteszi 1, törlése a jel a jel, hogy a nulla helyett van egy szám 0 + k.
Könnyen hozzá számokat algoritmusok lehet építeni, ezek egymással szorozzák, megtámadják a legnagyobb közös osztó, stb Azonban a fő célja bevezetésének gépek Posta és Turing programozás nekik, és tulajdonságainak tanulmányozására algoritmusok és algoritmikus problémák a fizetőképességi problémák.
Attól függően, hogy a sávok száma, céljuk és az államok száma a vezérlőberendezés lehet tekinteni különböző módosításokat a Turing-gép.
Tegyük fel, bővítettük meghatározása MT hozzáadásával egy bizonyos állapotot q. gépi berendezésről. Azt mondják, hogy ha a vezérlő egység továbblép az állami q0 egy meghatározott bemeneti szót x, x a gép lehetővé teszi; ha az eszköz bemegy qx. A gép megtiltja x. Ez az autó lesz az úgynevezett Turing-gép két out. Figyelembe lehet venni sok lehetőség a Turing-gép véges számú szalagok. Minden cellában ezeket a szalagokat lehet az egyik karakter a külső ábécé A = a0. a1. AN>. egy gép vezérlőegység minden egyes alkalommal van egyik egy véges halmaza Q = 0. q1. qm>. A K -lentochnoy gép konfigurációja azt az i-edik idő által leírt K-szavakat írja:
Az első index megfelel annak az időnek, a második - a szalag számát, a harmadik -Numbers sejtek balról jobbra. Azt mondják, hogy a gép végrehajtja a parancsot
Ha, állapotban qi és felmérési sejtet AA1 szimbólumok - AAK, a gép megy az állam QJ helyett a tartalmát a sejtek által a szimbólumok Ab1 - ABK, miután ezt a szalagot rendre eltolt irányba k1. kk.
Eddig azt feltételezték, hogy a különböző algoritmusok különböző Turing-gép különböző utasítások halmaza, a belső és külső ábécét. Azonban lehetséges egy univerzális Turing-gép, elvégzésére képesek bármely algoritmus bármely Turing-gép. Ezt úgy érjük el kódoló konfiguráció és programjai adott Turing-gép a külső jelek ábécé univerzális gépen. Felesleges kódolást kell végezni a következők szerint:
1) a különböző szimbólumok kell helyettesíteni másik kód csoportok, hanem az azonos szimbólum kell cserélni ott, ahol korábban nem teljesülnek, ugyanazt a kódot csoport;
2) rögzíti a kódot húrok kell egyedileg bontották egyedi kód-csoport;
3) lehetővé kell tenni, hogy felismerik a kódot csoportok megfelelő parancsok A, P, C, megkülönböztetni a kód megfelelő csoportot a szimbólumok az ábécé a külső és belső körülmények között.
Összehasonlítani a struktúrák különböző gépek és felmérése a komplexitás szükséges egy megfelelő intézkedés a bonyolult gépek. K.Shennon javasolta, hogy fontolja meg olyan intézkedéseket, mint a termék a számos külső ábécé szimbólumok száma és a belső állapotok. A nagy érdeklődés van a probléma a létrehozunk egy univerzális Turing-gép a legalacsonyabb komplexitás.
Meg lehet tekinteni egy másik általánosítása Turing-gépek: az összetételüket. készítmény végrehajtott műveletek az algoritmusok, amelyek lehetővé teszik a kialakulását egy új, kifinomultabb algoritmusokkal korábban ismert egyszerű algoritmust. Mivel a Turing-gép - algoritmus működését a készítmény alkalmazható a Turing-gép. Tekintsük a legfontosabbak: a termék, hatványozás, iteráció.
Hasonlóképpen határoztuk hatványozási művelet: n -edik fokú gép T. T a termék a T c N szorzók.
iterációs művelet alkalmazható egy gépen, és a következőképpen definiáljuk. Hagyja, hogy a készülék T1 számos végső állapot. Úgy döntünk, hogy az r-edik végleges állapot, és azonosítja a rendszer az autó eredeti állapotát. A kapott gép az eredménye a T T1 gépek iteráció. T = T1.
Mielőtt laknak a probléma algoritmikus megoldhatóságának problémákat pedig más módon hivatalossá fogalmának algoritmus.