Turing-gép - studopediya
Turing-gép áll egy végtelen heveder, amely cellákra van felosztva (sejtek) azonos nagyságúak. Minden cella lehet rögzíteni pontosan egy levelet. Az üres cella azt jelenti, hogy az tartalmazza az üres karaktereket. Mozgatni a szalag gép fel van szerelve egy egyszerű szalag szállítási mechanizmust, amely lehetővé teszi, hogy mozog a szalag egyik cellából a balra vagy jobbra. Olvasni írt a szalag szimbólumot és írd meg Turing-gép fel van szerelve egy olvasófej - felvételt. Ugyanakkor a fejét egy időben tud olvasni csak egy levél, írt a sejt a szalag található, amely a fej alatt. levelek nem helyettesítik az olvasás, mi van írva a cellában
A legfontosabb része a Turing-gép egy logikai egység, amely egy start gombot. Amikor megnyomja, a logikai egység fogadja a kezdeti állapotban és működni kezd:
1. ez okozza a fejét, hogy olvasni egy levelet, hogy a szalagon a fej alatt;
rekord a kazettára a sejt a fej alatt, a betűk;
b mozog a szalag balra, jobbra, vagy balra a helyén;
c változtatni saját helyzetüket;
3. Ha a műveletek eredményeként a 2. bekezdésben meghatározott, a levél alatt található a fej, a helyzet a szalagot, és az állam gép logikai blokk takimizhe marad, mint volt, csak előtt ezeket a lépéseket, akkor a gép leáll. Minden más esetben, a logikai egység vissza az 1. lépésre.
- Néhány ábécé P = o, ..., pi. pn> tartalmú leveleket lehet rögzíteni a szalagra. Ez ábécé hívják az ábécé egy Turing-gép;
- ábécé A = 1. a2. ..., am> tartalmazó állam, amely lehet egy logikai egységet;
- ábécé D = -1. d0. d1> hivatott jelölni a szalag mozgását balra vagy jobbra, és állítsa le a szalagot.
Emlékszünk, hogy hívjuk egy sor ábécé elrendezése egy bizonyos értelemben a szimbólumok nyelvén vagy rendszer. Ezek a karakterek úgynevezett leveleket. Csak karakterek, amelyek ehhez ábécé, lehet építeni szavakat.
Bemutatjuk, hogyan viselkedik egy Turing-gép, ha a logikai egység, 2. bekezdés, összhangban a szimbólumokat.
Ha a fej olvassa a levelet pi. és a készülék állapotban ai. a viselkedését a gép határozza meg a felvétel px dy AZ. amely megfelel a csapat:
A kazettára felvett betű helyett pi levél pi;
hogy a mozgás a szalag dy;
bemegy egy állapotot logikai blokk AZ.
Nyilvánvaló, hogy a kombinációs reakciók pi. aj i ≠ j függ a munka a Turing-gép. A reakciót a gép a kombinációja pi. aj lehet képviseli, mint egy táblázat, amelyben a sejtek tripletek a szimbólumok formájában px dy AZ.
Ha a kazettán egy szót az ábécé P és nyomja meg a start gombot, az eredmény a gép két lehetséges kimenetele:
A gép üzemeltetése után véges számú lépés leáll. Ugyanakkor szót írt a szalagon fogják hívni a munkája eredményét, azaz a gép alkalmazható az eredeti adatokat;
A gép nem áll meg, azaz Eredmény: A készülék nem bocsát ki és nem vonatkozik az eredeti adatokat.
Levelezés létre Turing-gép a forrás adatok, amelyekre vonatkozik, és az eredményeket a működését, néhány egész szám, nem-negatív f (x).
Adott egy f (x) = x + 1 0 ° C hőmérsékleten h≥ Construct Turing gép, amely megvalósítja ezt a funkciót.
1) adja meg a szimbólumok és meghatározzák a kezdeti állapot a szalag:
a) az x értékét lesz írva a szalagot, mint álló jelsorozat egységek, és az üres cellák fogják zérussal jelöltük;
b) intézkedik a szalagot úgy, hogy a bal szélső egység volt a fej alatt;
c) lefordítani logikai egység az eredeti állapotába ai;
2) elemzi a logikai művelet blokk:
a) ha az állam úgy ítéli meg, egy szimbólum ai 1 fej, az szükséges, hogy a logikai egység újra rögzíteni a cellában 1, a szalag már előrehaladott egy pozícióval balra és maradt ugyanolyan állapotban ai;
b) Ha az állam úgy ítéli meg, egy szimbólum ai fej 0, a logikai-nek egységet kell írni, 1 cella, a szalag maradt ugyanabban a helyzetben magam bemegy állapotban a2;
c) az állam a a2 és olvasó fej szimbólum 1, a logikai egység ismét meg kell írni a cella 1, a szalag nem mozdul, és továbbra is az állam a2. Ebben az esetben a gép leáll;
3) megépíteni a függvénytábla a Turing-gép, amely kiszámítja az értéke az f (x) = x + 1, h≥0:
e) miután a negyedik lépés leáll a gép, és a szalagot függvényében jegyezzük értéke megfelel a sejtek száma teli jelek 1.
Kiszámításakor az f (x) van olyan algoritmus, amelynek révén össze egy Turing-gép, akkor ez a funkció kerül meghívásra Turing kiértékelhető.
tudjuk megfogalmazni a fő Turing tézis a következő: „Minden számolható függvény, akkor össze egy Turing-gép, amely megvalósítja ezt a funkciót.”