Példák a Turing-gép - studopediya
Tekintsük a Turing-gép, végrehajtása és biztosítja a kialakulását rekurzív függvények.
1. példa Construct Turing gép, amely kiszámítja a funkciót.
Hagyja, hogy a ábécét egy Turing-gép két karakter, ahol a 0 - null karakter, és 1 - jelképe elfoglalt sejteket. Ebben ábécé bármely nem negatív egész szám, k jelentése k + 1 szimbólumok 1, a szomszédos sejtek rögzítik a szalagot. Ebben az esetben a 0 szám van írva, ... 010 ...
Mi határozza meg a számítási eljárást az értékek ezt a funkciót Turing-gép. Mivel az eredmény képviselnek egy sor elfoglalt a sejteket, ahol - a sejtek száma által elfoglalt érv x. akkor a számítás gondoskodik a következőképpen. A sejt által elfoglalt érv x. szimbólum egy helyett rekordot üres szimbólum 0. Minden esetben, a szimbólum 1 információk vannak rögzítve két reprezentáló sejtek az eredmény. Ez azt eredményezi, amely egy sejtben tömb van elhelyezve, hogy a megfelelő a tömb sejtek elfoglalt argumentum x. keresztül egy üres cellát. Ha ahelyett, hogy a sejtek által elfoglalt érv x. csak akkor lesz üres cellákat, az új tömb elfoglalt eltávolított sejtek egy cellában a szimbólum 1.
A munkaprogram a Turing-gép, amely kiszámítja a függvény. Ez a következő:
- eltávolított egy elfoglalt cella érv.
- olvasni sejt által elfoglalt egy érv.
- Talált osztódó üres cella.
- olvassa le az eredményt a cella foglalt.
- töltött egy üres cellát eredményt.
- második sejt tele eredményt.
- nézve fordított sorrendben a sejt által elfoglalt eredményt.
- A megtalált üres osztódik.
- Talált második üres cella.
- újra olvasni üres elválasztás cellában.
- eltávolított egy forgalmas karaktert. Vége.
- Talált elfoglalt cella érv.
- nézve fordított sejt által elfoglalt egy érv.
- Talált egy üres cellára, mielőtt a sejt által elfoglalt érv.
2. példa Construct olyan Turing-gép, amely alkalmazható minden szó az ábécé a, b>, és átalakítja azokat a szavakat. Ellenőrizze a működését a gép beépített át néhány szót.
Határozat. Bemutatjuk az algoritmust, amely megoldja ezt a problémát. Először is, a parancsokat. telnie, mielőtt a szó végét, anélkül, hogy megváltoztatná annak jellegét. A jel a végén a beszéd fogja olvasni a karakter az állam.
A csapatok. . Mi mozgatni a bal megváltoztatása nélkül az utolsó karaktert.
Ha el tudja olvasni a szimbólum a. Ez azt jelenti. meg kell törölni az összes karakter szó. kivéve az utolsót. Ezt meg lehet tenni a parancsokat. . .
Ha a karakter olvassuk az állam. ezért minden munkát, és itt az ideje, hogy hagyja abba a parancsot.
Ha el tudja olvasni a szimbólum b. Ez azt jelenti. szükség van az összes szimbólumot kivéve. cserélje betűket b. Ezt használja parancsot. . .
Ha el tudja olvasni a szimbólum. ezért minden karakter az eredeti szót fogadnak el, akkor menjen egy állam a parancsot.
Ellenőrizze a művelet egy Turing-gép épül a szót Abba:
A szó bbaaa utolsó előtti szimbólum - a. és minden betű az eredeti szó, kivéve az utolsót, helyébe üres szimbólumok.
Így az ellenőrzés megtörtént, az eredmény egy Turing gép megfelel a melyeket meg a problémát.
A bemutatott példákban a megvalósíthatóság Turing gépek alapvető tulajdonságait algoritmus: diszkrétség determinizmust, tömeg és a hatás.
Ahhoz, hogy komplex Turing-gép fogalmát a Turing-gép készítmény.
Összetétele a Turing-gép az M1 és M2 az úgynevezett Turing gépet M amely kezdetben funkcionál Turing-gép M1. utolsó állam, ahol q0 változik a kezdeti állapot a Turing-gép M2. És tovább, az M gép működik, mint egy Turing-gép M2.
Turing-gépek készítmény jelölik: M = M1 M2 °.
Tehát, ha azt szeretnénk, hogy állítson össze egy Turing-gép, amely kiszámítja a függvény ƒ (x, y) = x + y + 1, ez elég ahhoz, hogy végrehajtsa a készítmény a Turing-gép. Legyen M1 készülék kiszámolja a függvény ƒ (x) = x + 1, és az M2 gép kiszámítja függvényében ƒ (x + y). Ezután a gép M = M1 M2 ° kiszámítja, nyilvánvaló, hogy a funkció ƒ (x, y) = x + y + 1. Ehhez a program, amely leírja az M1 gép. csatlakoztassa az M2 gép parancsokat. M1 gép állapotát is kifejti a gép M. A végleges állapotot q0 gépek M1 q2 kell cserélni a feltétele, hogy megfelel a kezdeti állapotát az M2 gép. majd számozni M2 gép államokban. az állam állapotba vált Q1 Q2 q2 gépek M. állapotváltozásokat az állami q3, és így tovább.
Sok változat a Turing-gépek, amelyek között az egyetemes és több gép. Sokoldalú gép jellemzi egyidejű használatát a jobb és bal polulent, amelyek közül az egyik az összes parancs van írva, hogy kiszámolja az adott funkció, másrészt a jelenlegi konfigurációt.
Mert Multitape gépek jelenléte jellemzi több szalagok és több fej, amely lehetővé teszi, hogy megszervezzék egyidejű működése a protokoll összes felvételt, így könnyen szervezni összetett párhuzamos számítások.
Rekurzív függvények és a Turing-gép, így közvetett meghatározására a koncepció az algoritmus: ha bizonyítható, hogy egy függvény primitív rekurzív, esetleg építeni egy Turing-gép megoldani egy bizonyos probléma, akkor ez a probléma megoldható.
Másrészt, ha bebizonyosodik, hogy a megoldás a probléma nem kapott számítási primitív rekurzív függvények, és bebizonyította, hogy nem lehet építeni egy Turing-gép, hogy megoldja ezt a problémát, ez a probléma az úgynevezett algoritmikusan megoldhatatlan.
Annak fontosságát, hogy a bizonyítékok a tény, hogy néhány probléma algoritmikusan megoldhatatlan, hogy a kutató nem töltenek sok időt és energiát, hogy dolgozzon ki egy olyan algoritmus e probléma megoldásának általános módon.