Grafikus bemutatás. A Turing-gép működése. Turing-gépek építése. A gépek összetétele. Turing-számított függvények Milyen összetételűek a Turing-gépek
A Turing-gép definíciója, működése és meghatározásának módszerei
A Turing-gép egy hipotetikus (absztrakt) gép, amely a következő részekből áll (3.1. ábra)
1) egy végtelen szalag mindkét irányban, cellákra osztva, amelyek mindegyike csak egy karaktert tartalmazhat az ábécéből, valamint egy üres l karaktert;
2) vezérlőberendezés (munkafej), amely minden pillanatban a készlet valamelyik állapotában lehet. Mindegyik állapotban a fej a cellával szemben helyezkedik el, és képes beleolvasni (megnézni) vagy írni egy betűt az ábécéből A.
Rizs. 3.1. Turing gép
Az MT működése elemi lépések sorozatából (óraciklusok) áll. Minden lépésben a következő műveleteket hajtják végre:
1. a munkafej leolvassa (nézi) a szimbólumot;
2. állapotától és a felügyelt szimbólumtól függően a fej generál egy szimbólumot, és beírja a megfigyelt cellába (esetleg =);
3.a fej egy cellával jobbra mozdul (R), bal (L) vagy a helyén marad (E);
4. a fej más belső állapotba kerül. (talán =).
Az állapot kezdeti, - végleges. A végső állapotba lépéskor a gép leáll.
Az MT teljes állapotát ún konfigurációt ... Ezek a betűk eloszlása a szalag celláiban, a munkafej és a nézett cella állapota. Konfiguráció óránként t a következő alakban van írva:, ahol a megfigyelt cellától balra található részszó, - a megfigyelt cellában lévő betű, - jobbra az alszó.
A kezdeti és a végső konfigurációt szabványnak nevezzük.
Háromféleképpen írhatjuk le az MT munkáját:
Az űrlap parancsrendszere
Funkcionális asztal;
Átmenetek grafikonja (diagramja).
Tekintsük őket példákkal.
1. példa Készítsen egy MT-t, amely megvalósítja két szó összefűzését az ábécében. A szalagon szereplő szavakat * választja el. A kezdeti konfiguráció szabványos.
Az MT parancsrendszer a következő:
Állapotban a fej jobbra mozog egy üres szimbólumig.
A jobb szélső karakter törlődik.
A csillag törlődik, ha az első szó üres.
A jobb szó karakterenként balra tolódik.
Áttérés a standard végső konfigurációra.
Funkcionális asztal
| a | b | * | l | |
| - | ||||
| - | ||||
| - | ||||
| - |
A táblázatban lévő kötőjelek azt jelzik, hogy az l karakter nem található állapotokban.
|
|
|||
Normál végső konfiguráció.
A szótárfüggvény kiszámítása MT-n a következőképpen értelmezhető. Legyen az a szó a szalagra írva a kezdeti konfigurációban. Ha az érték definiálva van, akkor véges számú lépéshez (pipa) a gépnek a végső konfigurációba kell mennie, amelyben egy szót írnak a szalagra. Ellenkező esetben az MT-nek határozatlan ideig kell futnia.
Az MT segítségével leírhatja a számokkal végzett aritmetikai műveletek teljesítményét. Ebben az esetben a számok a szalagon olyan ábécé szavakként jelennek meg, amelyek valamilyen számrendszer számjegyeiből állnak, és egy speciális jellel vannak elválasztva, amely nem része ennek az ábécének, például *. A leggyakrabban használt rendszer az unáris, amely egy –1 karakterből áll. A szalagon lévő X szám egy szóban van írva (vagy rövidítve) az ábécé szerint A = (1).
Egy numerikus függvény helyesen Turing-számítható (vagy egyszerűen kiszámítható), ha van olyan MT, amely a konfigurációt konfigurációvá alakítja át, ha = y, vagy határozatlan ideig fut, ha nincs megadva.
2. példa Két szám összeadásának művelete egy unáris kódban.
Kezdeti konfiguráció:
Végső konfiguráció: i.e. Az összeadás valójában egy szám hozzárendelésében rejlik b a számhoz a... Ehhez az első 1 törlődik, és a * helyére 1 kerül.
Adjuk meg az MT leírását funkcionális táblázat formájában:
| * | l | ||
| - | |||
| - | |||
| - |
A fenti módszerek az MT leírására gyakorlatilag csak egyszerű algoritmusokhoz használhatók, hiszen bonyolult leírásokhoz túl nehézkessé válik. Hasonlóképpen rendkívül nehézkes lenne a rekurzív függvények leírása a szuperpozíció, a primitív rekurzió és a minimalizálás legegyszerűbb függvényeivel és operátoraival. Ezért egy függvény primitív vagy részleges rekurzivitását más függvényekkel igazoljuk, amelyek primitív vagy részleges rekurzivitását már bizonyítottuk.
Hasonlóan, a komplex algoritmusok Turing-gépei megépíthetők a meglévő MT-k felhasználásával. Ezt az elrendezést MT kompozíciónak nevezik.
Ismertesse meg az MT összeállításának 4 fő módját:
Szekvenciális kompozíció (szuperpozíció);
Párhuzamos összetétel;
Elágazó
Következetes összetétel gépek és szófüggvények kiszámítása és az ábécé A, autót hívtak T számítási függvény. A szekvenciális összetételt a következőképpen ábrázoljuk:
és jelzi.
A szekvenciális összetételt általában az algoritmusok lineáris szakaszainak leírására használják.
A gépépítés lehetőségére vonatkozó tétel bizonyítása T, amely két tetszőleges gép szekvenciális összetétele, és a végső állapot és a kezdeti állapot azonosításával történik.
3. példa Készítsen 2 * X szorzóalgoritmust egy unáris kódban olyan másológép segítségével, amely az a szót a * a szóra fordítja, és egy összeadási gépet. A kívánt MT így néz ki:
| | | |
|||||||||||||
| | |
||||||||||||||
Párhuzamos összetétel gépek és szófüggvények kiszámítása és ábécé Aés V illetőleg autónak hívják T szótárfüggvény kiszámítása. Itt a jel az MT párhuzamos összetételében lévő szavak elválasztására szolgál.
| |
és ezt jelzi:.
Valójában két MT párhuzamos összetétele egy 2 szóból álló szót kap különböző ábécékben bemenetként, és egy 2 szóból álló szót ad ki, pl. két egyidejűleg és egymástól függetlenül működő gépet jelent.
A párhuzamos kompozíció megvalósításához kétszintes szalaggal ellátott gépet használnak. Ennek szükségessége abból adódik, hogy a számítás időben is szekvenciálisan történik, és például először számítva több helyet igényelhet, mint a, és elrontja a b szót. Egy kétszintes szalagos gép a következőképpen működik: a b szót a második emeleten átírják és az elsőn törlik, az első emeleten kiszámítják, a második emeleten számolják, majd az első emeleten átírják, esetleg eltolással .
Párhuzamos kompozíció megvalósítása n használt gépek n- padlószalag.
Az MT parancs kétszintes szalaggal a következőképpen írható:, hol vannak az első és a második emeleten írt betűk.
4. példa... Gépek és számítási függvények párhuzamos összetételének megvalósítása a kettes számrendszerben és a + b egy unáris rendszerben.
A bemeneti szó:.
Írjuk le az MT munkáját egy parancsrendszerrel:
Ugrás jobbra a b szóra
A b szó átírása a második emeletre
Lépjen balra az a szóig
1 hozzáadása X-hez.
Ugrás jobbra a b szóra.
1. emeleti b népszámlálás a számok egyidejű összeadásával aés b.Т, ill. Kapcsos zárójelek a parancsrendszerhez hozzáadva
Az egész MT végső állapota.
Meg kell jegyezni, hogy az algoritmus elején minden esetben be kell szúrni az eredeti adatok ellenőrzését a speciális értékekhez (leggyakrabban 0-nál), ennek a követelménynek a be nem tartása végtelen hurokhoz vezethet.
Az MT összetétel összetett algoritmusok készítésére használható. Felmerül a kérdés: megvalósítható-e bármilyen algoritmus MT összetétel formájában? A választ erre a kérdésre a Turing tézise , Church tézisének analógja: bármilyen algoritmus megvalósítható Turing-gépekkel és fordítva, minden Turing-géppel megvalósított folyamat algoritmus.
Turing tézise nem tétel, nem lehet bizonyítani, mert tartalmazza az informális fogalmat " algoritmus". Sok éves matematikai gyakorlat azonban megbízható megerősítése ennek a tézisnek: 50 éve nem találtak olyan intuitív értelemben vett algoritmust, amelyet ne lehetne Turing-gépekkel megvalósítani.
Az előző bekezdésben megvizsgáltuk, hogyan számítja ki egy adott Turing-gép az f (, ...,) függvényt. Ehhez a ... számok mindegyikét a megfelelő számú egyek folytonos tömbjeként kell felírni a gép szalagjára, és magukat a tömböket 0 szimbólummal kell elválasztani. Ha az f ( , ..., adott argumentumértékek halmazán van definiálva, akkor ennek eredményeként a szalagra f (, ...,) egységet kell egy sorba írni. Ugyanakkor nem voltunk túl szigorúak a a gép kiindulási helyzete (gyakran ez volt a szokásos kiindulási helyzet), amelyben a munkát befejezi, és hogyan halad a munka.
A következőkben egy függvény kiszámíthatóságának erősebb fogalmára lesz szükségünk Turing-gépen – a helyes kiszámíthatóság fogalmára.
5.1. meghatározás: Azt mondjuk, hogy a Turing-gép helyesen számítja ki az f (, ...,) függvényt, ha a 0 ... 0 kezdeti szót 0 ... 0 szóra fordítja, és ugyanakkor nem ad hozzá új cellákat a szalagon a kezdő szóhoz vagy a bal vagy a jobb oldalon. Ha az f függvény nincs definiálva az argumentumértékek adott halmazán, akkor a megadott pozícióból elkezdve soha nem építi fel a folyamat során a bal oldali szalagot.
5.1. példa. Itt vannak a Turing-gépek programjai, amelyek helyesen számítják ki az S (x) = x + 1 és az O (x) = 0 függvényeket. Az S (x) = x + 1 függvény fordítása: 0 =>. Programja: 0> P, 1> 1P, 0> 1, 1> 1L, 0> 0. Az O (x) = 0 függvény fordítása: 0 =>. Programja: 0> 0P, 1> 1P, 0> 0L, 1> 0, 0> 0L, 0> 0. A megfelelő Turing-gépet O jelölte.
5.2. példa.Építsen két gépet "balra váltó" és "jobb váltás". A kezdő standard pozíció közül az első feldolgozza a 0 szót ugyanabban a szóban, és leállítja a bal szélső cella áttekintését nullával. A második gép a kezdeti állapotból, amelyben a bal oldali nulla cellát nézi, a 0 szót ugyanabban a szóban dolgozza fel, és megáll, átnézve a jobb szélső nullával jelölt cellát.
Gépi program: 0> 0L, 1> 1L, 0> 0. Jól látható, hogy a gépprogramot az előző gép programjából kapjuk, ha az "L" szimbólumot "P" szimbólumra cseréljük.
A Turing-gépek összetétele
6.1. meghatározás: Legyenek adottak Turing-gépek és közös külső ábécé (,…,) és belső állapotok ábécéi (,…,) illetve (,…,). Egy gép összetétele (vagy terméke) egy géphez egy új gép, amelynek ugyanaz a külső ábécéje (,…,), belső ábécéje (,…,…,) és egy program, amelyet a következőképpen kapunk meg. A stop szimbólumot tartalmazó összes parancsban cserélje ki az utolsót erre. A parancsok összes többi karaktere változatlan marad. A from parancsokban a szimbólum változatlan marad, és az összes többi állapot (i = 1, ..., t) helyére kerül. Az így kapott összes parancs összessége alkotja a kompozíciós gép programját.
A bevezetett koncepció kényelmes eszköz Turing-gépek készítéséhez. Mutassuk meg ezt egy példával.
6.1. példa. Készítsünk olyan Turing-gépeket, amelyek helyesen számítják ki a (,…,) = (1? M? N) vetületi függvényeket.
Először fontolja meg konkrét eset n = 3, m = 2, azaz. függvény (,) =. A 0 szót 0 szóvá kell alakítanunk. A kezdeti konfigurációhoz alkalmazzuk a szekvenciálisan megszerkesztett korábbi Turing-gépeket, B, O:
Így a (,) = függvényt a gépek következő összetételével számítjuk ki: BOO = V.
Most elképzelhetünk egy algoritmust a B, O gépek összetételének megalkotására bármely (,…,) = alakú függvény kiszámítására. A jobb eltolással, m-1 alkalommal alkalmazva először el kell érni a tömböt:
Ezután balra mozgatva transzponálja (a B segítségével) a tömböt úgy, hogy minden tömb balra szomszédos legyen, amíg a tömb felül nem jön:
Most el kell jutnia a jobb szélső tömbhöz az (n-1) használatával - többszörös jobbra eltolás:
Végül törölnie kell az összes tömböt, kivéve az elsőt, egymás után jobbról balra:
Tehát ezt a függvényt (helyesen) a következő Turing-gép számítja ki.
Célkitűzés: gyakorlati ismereteket szerezzenek az algoritmusok írásában a Turing-gépek összetételének felhasználásával.
Elméleti háttér
A gyakorlatban az MT leírására szolgáló fenti módszerek csak egyszerű algoritmusokhoz használhatók, ellenkező esetben a leírás túl nehézkessé válik. Összetett algoritmusokhoz Turing-gépeket lehet építeni a meglévő elemi MT-k segítségével, és egy ilyen konstrukciót nevezünk összetétele MT.
Ismertesse meg az MT összeállításának 4 fő módját:
Szekvenciális kompozíció (szuperpozíció);
Párhuzamos összetétel;
Elágazó
1. Turing-gépek szekvenciális összetétele
Következetes összetétel vagy szuperpozíció Turing gépek és 
és 
az ábécében A, hívta az autót M számítási függvény 
.
A szekvenciális összetételt a következőképpen ábrázoljuk:
és jelöltük 
vagy 
.
2. Turing-gépek párhuzamos összetétele
Párhuzamos összetétel
gépek 
és 
szófüggvények kiszámítása 
és 
ábécé szerint Aés V, illetőleg autónak hívják M szótárfüggvény kiszámítása. Itt jel 
a szavak elválasztására szolgál az MT párhuzamos összetételében.
Párhuzamos összetétel MT 
és 
a következőképpen van ábrázolva:
és ezt jelzi: 
.
Valójában két MT párhuzamos összetétele bemenetként egy 2 szóból álló szót kap különböző ábécékben, és egy olyan szót ad ki, amely szintén 2 szóból áll, pl. két egyidejűleg és egymástól függetlenül működő gépet jelent. A párhuzamos kompozíció megvalósításához kétszintes szalaggal ellátott gépet használnak.
A kétszintes hevedergép a következőképpen működik:
1) szó 
felül van írva a szalag második emeletén, és törlődik az elsőn,
2) kiszámításra kerül 
az első emeleten,
3) kiszámításra kerül 
A második emeleten
4)
emeletnek felel meg, esetleg váltással.
Egy MT parancs kétszintes szalaggal a következőképpen írható:
,
ahol 
- az első és a második emeleten írt levelek. Jelöljük a szavak hosszát 
, ill. 
.
Mutassuk be egy Turing-gép működését kétrétegű szalaggal. Általában szóhosszúság 
és 
nem esnek egybe egymással, de az egyszerűség kedvéért feltételezzük, hogy egyenlők. Ezután az 1) -4) pontok végrehajtása az MT-n kétszintes szalaggal a következőképpen történik:
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Párhuzamos kompozíció megvalósítása n Használt Turing gépek n– padlószalag.
3. Elágazás vagy feltételes átmenet a Turing-gépek összetételében
Ha a Turing-gépek adottak 
és 
szófüggvények kiszámítása 
és 
, és az autó 
valamilyen predikátum kiszámítása P(
)
helyreállítással (azaz szó törlése nélkül
),
akkor egy Turing-gépet lehet építeni az elágazás megvalósítására 
számítási függvény:
A Turing-gépek elágazása a kompozíciós diagramokon a következőképpen látható:
és jelöltük 
, itt 
- a gép eredménye 
, az "1" értékeket véve, ha az állítmány P(
)=
”igaz”
és "0", ha az állítmány P(
)=
“hamis”
,
- Turing gép, amely megvalósítja a bemeneti szó másolását 
.
4 . Ciklus a Turing-gépek összetételében
Ciklus a kompozícióban az MT ugyanazon elvek szerint valósul meg, mint az elágazás.
" Viszlát P (
)=
”igaz”
, teljesíteni 
»,
ahol
- a szó a szalagon az első végrehajtás előtt 
és a következő kivégzés után .
A ciklus ábrázolásához bevezetünk néhány jelölést, legyen:
- egy Turing-gép, amely kiszámítja a predikátumot P (
)
;
–МТ, amely megvalósítja a bemeneti szó másolását 
;
–MT, ciklusban végrehajtva és megvalósítva 
;
–MT, a ciklusból való kilépéskor és megvalósításkor végrehajtódik 
.
Ezután a Turing-gépek ciklikus összetétele vagy egy ciklus a következőképpen ábrázolható:
Programozás Turing-gép kompozíciókkal:
1) összetett algoritmusok blokkdiagramjainak készítése olyan részletességgel, hogy azok blokkjai megfeleljenek az elemi MT-nek;
2) egyszerű blokkokat megvalósító elemi MT-k építése;
3) elemi MT-k kombinálása MT-kompozícióvá.
Példa. Készítsen egy MT-kompozíciót, amely megvalósítja 
.
–Turing gép, amely a bemeneti szó másolását valósítja meg;
–МТ, amely az állandó nullára állításának funkcióját valósítja meg;
–MT a predikátum kiértékelése helyreállítással 
;
- MT, amely megvalósítja a kiválasztási funkciót 
-th érv 
érvek;
–МТ, amely az argumentum csökkentésének funkcióját valósítja meg 
1-gyel az unáris kódban (törli a bal szélső karaktert);
- MT, két szám összeadása egy unáris kódban.
Megjegyzendő, hogy az algoritmus végrehajtásának kezdetén minden esetben ellenőrizni kell a bemeneti adatok helyességét (például az argumentum 0-val való egyenlőségét az osztás során).
A Turing-gép (MT) egy absztrakt végrehajtó (absztrakt számítási gép).
Az algoritmusok kombinációi egy olyan név, amelyet számos konkrét módszerre hoztak létre, amelyek több megadott algoritmusból új algoritmusokat hozhatnak létre.
A kombinációs tételek az általános algoritmuselmélet fontos részét képezik. Miután bebizonyították, lehetővé teszik az összetett és nehézkes algoritmusok megvalósíthatóságának további ellenőrzését anélkül, hogy ténylegesen kiírnák az azokat meghatározó áramköröket.
A Turing-gép algoritmusainak kombinációit a Turing-gépeken végzett műveletek írják le.
1. A kompozíció működése.
Legyenek M 1 és M 2 Turing-gépek azonos külső A «(a 0, a 1, ..., a p) ábécével. Jelöljük ki a Q1 «(q 0, q 1, ..., q n) és Q2« (q 0 ", q 1", ..., q m ") állapothalmazait.
Meghatározás.
Az M 1 és M 2 gépek összetétele egy olyan gép, amelyet M = M 1 × M 2 jelöl, és amelynek programjában van egy A ábécé, Q «(q 0, q 1, ..., qn, qn +) állapothalmaz. 1, ... , qn + m), és az M 1 és M 2 gépek programjaiból a következőképpen kapjuk meg: mindenhol az M 1 gép programjában, ahol vannak q 1 jelű "hármasok" (a a gép végállapota M 1), azt a q 0" szimbólum helyettesíti (a gép kezdeti állapota M 2); az M 1 és M 2 gépek programjaiban az összes többi szimbólum változatlan marad (a végén, hátra van az M gép összes állapotának újraszámozása: (q 0, q 1 ", q 2, ..., qn, q 0 ", q 2", ..., qm ")).
A kompozíció úgy kezd "működni", mint az M 1 gép, de azokban az esetekben, amikor az M 1 gépnek le kell állnia, átvált az M 2 gép programjára, mivel q 1 q 0-ra cserélődik. "Nyilván, a kompozíciós művelet asszociatív, de nem kommutatív.
Működése megegyezik a T1 és T2 gépek szekvenciális működésével.
Az ábra a Turing-gépek összetételét mutatja, amely megvalósítja a szuperpozíciós operátort n = 1 és m = 1 esetén.
1. kép
Meghatározás.
Az M Turing-gép iterációja egy gép
2. Elágazás működése.
Legyenek M 1, M 2 és M 3 Turing-gépek azonos külső ábécével A «(a 0, a 1, ..., ai, ..., aj, ..., ap), és ennek megfelelően a állapotkészletek: Q1 «(q 0, q 1, ..., qn), Q2« (q 0 ", q 1", ..., qm "), Q3« (q 0 ", q 1", ... , ql ").
Meghatározás.
Az M 1, M 2 és M3 Turing-gépeken végzett elágazási művelet eredményét M Turing-gépnek nevezzük, melynek programját az M 1, M 2 és M 3 gépek programjaiból a következőképpen kapjuk meg: a gép programja M1-et írunk, majd az M 2 és M 3 gép programjait hozzárendeljük. Ha az a i szimbólumot az M1 gép q 1 végállapotában figyeljük meg, akkor a vezérlés átkerül az M 2 gépre, azaz. a q 1 szimbólumot a q 0 " szimbólum váltja fel, és az M 2 gép elkezd dolgozni. Ha az aj szimbólumot az M 1 gép q 1 végállapotában figyeljük meg, akkor a vezérlés átkerül az M 3 gépre, azaz a q 1 szimbólumot a q 0" szimbólum váltja fel, és az M 3 gép működésbe lép. Az M 1 és M 2 gépek programjaiban szereplő összes többi szimbólum változatlan marad. Az M gép a q 1 végállapotban ér véget (a végén marad az M gép állapotainak végpontok közötti újraszámozása).
Az M 1, M 2 és M3 Turing gépeken végzett elágazás eredményét a következőképpen jelöljük:
A kétbetűs Turing-gépeknél (kétbetűs ábécével rendelkező Turing-gépek) a tetszőleges M1, M2 és M3 Turing-gépeken végzett elágazási műveleteket a következőképpen jelöljük:
azok. ha az M1 gép működése közben q 1 állapotban az a 0 szimbólumot észleljük, akkor a vezérlés átkerül az M2 gépre, ellenkező esetben az M3 gépre.
3. Looping működése.
Legyen M Turing-gép A «(a 0, a 1, ..., a p) ábécéjével és Q« állapothalmazával (q 0, q 1, ..., q n).
Meghatározás.
A hurkolási művelet eredménye egy Turing-gép, amelyet (i = 0,2,3, ..., n; j = 0,1,2, ..., p; s = 0,2,3, ) jelölünk. .., n)
melynek programját az M gép programjából úgy kapjuk meg, hogy a qiaj ®q parancs következményében 1 atr, rÎ (L, R, L), t = 0,1,2, ... p helyettesítjük a q szimbólumot. 1 a q s szimbólummal.
2 .4 Turing-gép változatok
A Turing-gép modellje bővíthető. Tekinthetünk tetszőleges számú szalaggal rendelkező Turing-gépeket és különféle megkötésekkel rendelkező többdimenziós szalagokat. Azonban ezek a gépek mindegyike Turing-komplett, és hagyományos Turing-géppel modellezték őket.
Az ilyen egyenértékűség példájaként vegyük fontolóra bármely MT redukálását félvégtelen szalagon működő MT-vé.
Tétel: Bármely Turing-géphez létezik egy ezzel egyenértékű Turing-gép, amely félvégtelen szalagon működik.
Bizonyíték:
Tekintsük Yu. G. Karpov bizonyítékát. Ennek a tételnek a bizonyítása konstruktív, azaz megadunk egy algoritmust, amellyel bármely Turing-gépre megszerkeszthető a deklarált tulajdonságú ekvivalens Turing-gép. Először véletlenszerűen megszámozzuk az MT munkaszalag celláit, azaz meghatározzuk az információ új helyét a szalagon:
1. kép
Ezután újraszámozzuk a cellákat, és feltételezzük, hogy a "*" szimbólum nem szerepel az MT szótárban:
1. kép
2.5 Turing-számíthatóság és eldönthetőség
A fentiekben bebizonyosodott, hogy a rekurzív függvényekkel, Turing-gépekkel vagy normál Markov-algoritmusokkal kiszámítható függvényosztályok egybeesnek. Ez lehetővé teszi számunkra, hogy a "számítási algoritmus" fogalmát a leírási módszerrel invariánsnak tekintsük. Különbségek csak az algoritmikus objektumok használatában figyelhetők meg. Ha rekurzív függvényeknél az objektumok számok és numerikus függvények, és a számítási folyamatot a szuperpozíció, a rekurzió, a minimalizálás és az iteráció operátorai határozzák meg, akkor a Turing-gépeknél az ilyen objektumok a külső és belső memória ábécéinek szimbólumai, és a A számítási folyamatot egy protokoll határozza meg, amely kilépést, átmenetet és a fej mozgatását használja. A normál Markov-algoritmus esetében az ilyen objektumok szavak vagy karaktersorozatok, és a számítási folyamatot helyettesítési szabályok vagy produkciók határozzák meg, amelyek megváltoztatják az eredeti karaktersorozat összetételét és szerkezetét a kívánt eredményre.
Az aritmetikai (numerikus) függvény olyan függvény, amelynek értéktartománya az N halmaz egy részhalmaza, a definíciós tartomány pedig az N halmaz egyik eleme.
Algoritmikus problémák esetén tipikus helyzet az, amikor egy f (x 1, x 2,…, xn) numerikus függvény kiszámításához algoritmust kell találni, az x 1, x 2 argumentumok egész értékétől függően, …, x n.
Az f: N n → N függvényt kiszámíthatónak nevezzük, ha létezik egy algoritmus, amely lehetővé teszi argumentumai bármely értékkészletét a függvény értékének kiszámításához (vagy jelzi, hogy a függvény nincs definiálva ebben a halmazban). Mivel a kiszámítható függvény meghatározása az algoritmus intuitív koncepcióját használja, az "intuitív módon kiszámítható függvény" kifejezést gyakran használják a "számítható függvény" kifejezés helyett. Így egy tömegfeladatnak van megoldása, ha a feladatnak megfelelő számtani függvény intuitív módon kiszámítható.
Egy f (x 1, x 2, ..., xn) függvényt akkor nevezünk effektíven kiszámíthatónak, ha adott k 1, k 2, ..., kn értékekre megtaláljuk az f (k) függvény értékét. 1, k 2, ..., kn) valamilyen meglévő mechanikai eljárás (algoritmus) segítségével.
Az algoritmus fogalmának tisztázása helyett megfontolható a "számítható függvény" fogalmának finomítása. Általában a következő séma szerint járnak el:
1. Mutasson be egy pontosan meghatározott függvényosztályt.
2. Győződjön meg arról, hogy ebben az osztályban minden függvény kiszámítható.
3. Elfogadják azt a hipotézist (tézist), hogy a kiszámítható függvények osztálya egybeesik a bevezetett függvényosztállyal.
Egy függvényt akkor nevezünk kiszámíthatónak, ha van egy algoritmus, amely kiszámolja. A „számíthatóság” az algoritmusok elméletének egyik alapfogalma, invariáns a számított függvény és az algoritmus szempontjából. A kiszámítható függvény és az algoritmus közötti különbség a függvény leírása és az értékek kiszámításának módja közötti különbség a független argumentumok adott értékeihez.
Turing tézise. Bármilyen intuitív algoritmus megvalósítható valamilyen Turing-gép segítségével.
Turing téziséből következik, hogy ha algoritmikus problémák merülnek fel, akkor azokat Turing-gépek felépítése, azaz egy meglehetősen formalizált algoritmusfogalom alapján kell megoldani. Sőt, algoritmikus problémákban gyakran jön nem egy algoritmus felépítéséről, hanem néhány speciálisan felépített függvény kiszámíthatóságáról.
Megjegyzendő, hogy ezekben az esetekben elegendő az ábécé (0, |) használata, ahol a 0 egy üres karakter. Például a természetes számok, beleértve a 0-t is, ebben az ábécében a következőképpen vannak kódolva: 0 - |; 1 - ||; 2 -
N - || ... | (n + 1-szer). Egy parciális numerikus n - helyi f (x1, x2, ..., xn) függvényt Turing-számítógépnek nevezünk, ha van egy M gép, amely a következő értelemben számítja ki: 1. Ha az argumentumértékek halmaza
AZ ÖNALKALMAZHATÓSÁG PROBLÉMÁJA
A Turing-gép definíciója szerint ez egy hármas T =
P: q i a a j a ® q r a a s a Utca a , a = 1, 2, ..., k , ahol S 1- R, S 2- L, S 3- C . (*)
Ebben az esetben feltételezhetjük, hogy van néhány gyakori ábécé A 0és Q 0 ahol a karakterek vannak írva a és q minden Turing-géphez. Aztán a szimbólumok q i a, a j a, q r a, a s a, Utca a az ábécé szimbólumai A 0és Q 0.
Ez a megközelítés lehetővé teszi az összes Turing-gép számozását, vagyis minden géphez hozzá lehet rendelni egy bizonyos, csak erre a gépre jellemző számot (kódot), amellyel meg lehet különböztetni a többi géptől. Itt megvizsgáljuk az egyik számozási módszert.
Turing-gépek Gödel-számozása. Hadd p 1, p 2, p 3 , ... prímszámok sorozata növekvő sorrendben, például 2, 3, 5, 7, 11, 13, ...
Turing-gép száma programmal (*) hívta a számot
n (T) = .
Példa
A funkciót megvalósító gép S(x)= x + 1 , van egy program az ábécében {0, } ... Ennek a programnak a száma, figyelembe véve azt a tényt, hogy egy 0 = 0 , egy 1= | lesz egy szám :.
n (T) = 2 1 3 1 5 1 7 1 11 1 13 1 17 0 19 0 23 1 29 3.
Nyilvánvaló, hogy nem minden természetes szám Turing-gép szám. Másrészt ha n Ha valamelyik gép száma közönséges ábécékben van, akkor ezzel a számmal egyértelműen visszaállítható a programja.
Autó T szóra alkalmazható n(T)(azaz a saját számának kódjára), önalkalmazhatónak nevezzük .
Önalkalmazható és nem önalkalmazható gépeket egyaránt készíthet. Például az adott példában szereplő gép önérvényesítő. Autó T, amelynek nincs törés szimbóluma a program jobb részében (a táblázat törzsében), nem alkalmazható egyetlen szóra sem, és ezért a szóra. n(T).
Önalkalmazhatósági probléma a következőkből áll: jelöljön meg egy algoritmust, amely bármely Turing-gép esetén meghatározza, hogy az önállóan alkalmazható-e vagy sem.
A Turing-tézis szerint egy ilyen algoritmust egy Turing-gép formájában kell keresni. Ennek a gépnek az összes Turing-gép számkódjaira alkalmazhatónak kell lennie, és a tesztelt gépek kódjainak feldolgozási eredményétől függően eltérő végső konfigurációval rendelkezik.
Legyen például az adott autó T kódra vonatkozik n(T * ) ... Ha az autó T * önállóan alkalmazható, akkor a gép végső konfigurációja T van formája egy " q 0 | B", és abban az esetben, ha az autó T * nem önállóan alkalmazható, akkor a gép végleges konfigurációja T van formája egy " q 0 0 B ". Itt a ", B", a ", B"- a szavak.
Tétel Az önalkalmazhatósági probléma algoritmikusan megoldhatatlan, vagyis nincs olyan Turing-gép, amely ezt a problémát a fenti értelemben megoldaná.
A tételből az következik, hogy nincs általános algoritmus A probléma megoldásaönalkalmazhatóság. Különleges esetekben létezhetnek ilyen algoritmusok.
Ennek a tételnek az eredményeit fogjuk felhasználni annak bizonyítására, hogy a kezdeti szóra való alkalmazhatóság problémája eldönthetetlen.
A kezdőszóra való alkalmazhatóság problémája a következő: hozzon létre egy algoritmust, amely a gép szerint Tés a szót x telepítené, gép alkalmazható T mellesleg x vagy sem (egyébként leállási probléma).
A Turing-gépek vonatkozásában, hasonlóan az önalkalmazhatósági probléma megfogalmazásához, ez a probléma a következőképpen fogalmazódik meg: lehetséges-e olyan gépet építeni, amely az alak minden szavára alkalmazható lenne? n(T) 0 x , ahol T tetszőleges gép, x - tetszőleges szó, és abban az esetben, ha a gép T szóra alkalmazható x egy " q 0 | B " , és abban az esetben, ha az autó T szóra nem vonatkozik x , a végső konfigurációhoz vezetne egy " q 0 0 B" . Itt a ", B"és a ", B"- önkényes szavak.
Tétel A kezdőszóra való alkalmazhatóság problémája algoritmikusan megoldhatatlan, vagyis nincs olyan Turing-gép, amely ezt a problémát a fenti értelemben megoldaná.
Ahogy fentebb az önalkalmazhatósági probléma kapcsán említettük, az első előzetes lépés a számozás. Ezért az alábbiakban ezt a problémát következetesen megvizsgáljuk és megoldjuk az algoritmusokra és annak három fő algoritmikus modelljére vonatkozóan.
Algoritmus számozás
Az algoritmusok számozása fontos szerepet játszik kutatásukban és elemzésükben. Mivel bármely algoritmus megadható véges szóként (egy bizonyos ábécé véges szimbólumsorozataként ábrázolva), és a véges ábécé összes véges szavának halmaza megszámlálható, az összes algoritmus halmaza is megszámlálható. Ez egy az egyhez leképezés meglétét jelenti a természetes számok halmaza és az algoritmusok halmaza között, vagyis azt, hogy minden algoritmushoz számot lehet rendelni.
Az algoritmusok számozása egyben az összes algoritmikusan kiszámítható függvény számozása, és bármely függvénynek végtelen számú száma lehet.
A számozás megléte lehetővé teszi, hogy ugyanúgy dolgozzunk az algoritmusokkal, mint a számokkal. A számozás különösen hasznos olyan algoritmusok vizsgálatakor, amelyek más algoritmusokkal működnek együtt.
Legyen egy bizonyos tömegprobléma X kezdeti objektumok halmazával és Y kívánt objektumok halmazával. A tömegprobléma megoldásához szükséges, hogy az X és Y halmazok elemei konstruktív objektumok legyenek. Ebből következően ezeknek a halmazoknak az elemei természetes számokkal is felsorolhatók. Legyen x∈ X valamilyen kezdeti objektum, a számát jelöljük n (x)-el. Ha az eredeti x objektum tömegfeladatában meg kell kapni a kívánt y∈ Y objektumot n (y) számmal, akkor definiálunk egy f: Nn → N aritmetikai függvényt úgy, hogy f (n (x)) = n (y).
Példaként a tömegfeladatok aritmetikai függvényeinek összeállítására vegye figyelembe a tömegfeladatokat.
1. Ha adott egy természetes számok tömbje], akkor hozzárendelhető egy 2x1, 3x2, ... p (n) xn természetes számhoz, ahol p (n) - n-edik prím szám. Vegyünk például egy 5 hosszúságú tömböt:
] 2x13x25x37x411x5.
Ez a számozás határozza meg az f számtani függvényt (például f (73500) = f (22315372110) = 20315272113 = 4891425).
2. Minden racionális számnak van természetes száma. A feladat kívánt objektumkészletének számozása triviális:
("Igen", "nem") a (1, 0). Ehhez a tömegproblémához megszerkeszthet egy argumentum aritmetikai függvényét az előző példa technikájával, vagy figyelembe vehet három argumentum függvényét (az eredeti hármas három elemszáma).
3. A programszövegek számozása a következőképpen történhet: bármely program felfogható úgy, mint egy számot a 256-os számrendszerben (ha ASCII karaktereket használtunk a program írásához).
A tömegfeladatról az aritmetikai függvényre való átmenet lehetővé teszi, hogy a tömegprobléma megoldásának kérdését a létezés kérdésére redukáljuk. hatékony mód egy aritmetikai függvény értékeinek kiszámítása argumentuma(i) alapján.
Számok számozási halmazai
Az algoritmusok elméletében elterjedt egy olyan technika, amely lehetővé teszi több változó függvényének tanulmányozását egy változó függvényeinek vizsgálatára redukálni. Számhalmazok számozásán alapszik oly módon, hogy a számhalmazok és a számok között bijektív megfelelés van, és azok a függvények, amelyek számhalmazok alapján határozzák meg a számát, és maga a számhalmaz általános rekurzív. . Például egy két független változót (x, y) tartalmazó függvény esetén ez a h (x, y) leképezés a következő lehet:
1. kép
Legyenek (x, y) párok egy részlegesen rendezett N (2) halmazt. Adott h (x, y) = n, akkor van egy inverz leképezés: x = h -1 1 (n) és y = h -1 2 (n), azaz h (h -1 1 (n), h - 1 2 (n)) = n. Ez lehetővé teszi bármely pár (x, y) n számának kiszámítását, és fordítva, az n szám felhasználását az x és y értékeinek kiszámításához:
Ezekkel a szabályokkal kiszámítható a hármasok számozása h 2 (x, y, z) = h (h (x, y), z) = n, és fordítva, a hármas számmal - az x értékek , y, z. Például, ha h 2 (x, y, z) = n, akkor z = h -1 2 (n), y = h -1 2 (h -1 1 (n)), x = h -1 1 ( h -1 1 (n)), h 2 (x, y, z) = h (h (h -1 1 (h -1 1 (n)), h -1 2 (h -1 1 (n)))) ) , h-1 2 (n)). A tripletek (x, y, z) egy részlegesen rendezett N (3) halmazt alkotnak. Hasonlóképpen tetszőleges számú számhoz a következőt kapjuk:
h n-1 (x1, x2,…, xn) = h (h… h (h (x1, x2), x3)… x n-1), xn). Ha h n-1 (x1, x2, ..., xn) = m, akkor xn = h -1 2 (m), x n-1 = h -1 2 (h -1 1 (m)), . .. .................................., x2 = h -1 2 (h -1 1 (. .. h -1 1 (m) ...)), x1 = h -1 2 (h (... h (m) ...)).
Adott az N (1), N (2), ..., N (i), ..., N (n) halmazok számozása, ahol N (i) az (i) számhalmazok halmaza , megállapíthatjuk tetszőleges halmazok kombinált számozását az M = N (1) N (2) ... N (i) .. N (n), ahol M N. Bármely n N-re van h (x1, x2) , ..., xn) = h (hn −1 (x1, x2, ..., xn), n −1).
Ha h (x, 1x, 2 ..., x) n = m, akkor hn − 1 (x, 1x, 2 ..., x) n = h -1 1 (m), n = h -1 2 (m) +1. A fenti képletekkel visszaállíthatja az x1, x2, ..., xn értékeket.
Hasonló információk.
A Turing-gép működése:
Az algoritmus három fő fogalma közül a második a gépi matematikához kapcsolódik. Az algoritmust a legegyszerűbb determinisztikus eszköznek tekintik, amely bármikor képes a legegyszerűbb műveletek végrehajtására. Az alapmodell egy Turing-gép.
A Turing-gép három ábécével működik:
1.beviteli ábécé A={egy 0…a n), melynek segítségével rögzítésre kerül a bemeneti, köztes, kimeneti információ. egy 0- üres karakter (jelentéktelen nulla, Ù, V, #), egy 1- 1 vagy |
2.belső ábécé, vagy állapotok ábécéje K={q 0…q m}, q 0- végső állapot q 1- kezdeti állapot q 0 ... q n- munkafeltétel
3. Ábécé eltolása (L, W, N) vagy (-1, +1, 0) (balra, jobbra, a helyén)
A Turing-gép a következő részekből áll:
1) szalag, potenciálisan végtelen mindkét irányban. A potenciális végtelenség azt jelenti, hogy minden időpillanatban egy végső szót rögzítenek a szalagon, de szükség esetén a kívánt számú cellát a szótól balra és jobbra is ki lehet egészíteni. A szalag cellákra van osztva, amelyek mindegyike csak a bemeneti ábécé egy karakterét tartalmazza. Az üres cellák üres karaktert tartalmaznak. Ha egy cellában lévő információt törölni kell, akkor elég egy üres szimbólumot írni bele.
2) vezérlő eszköz(UU), amely a program segítségével vezérli a Turing-gépet. Az UU minden időpillanatban csak az ábécé egyik állapotában lehet K.
3) fej(olvasó és író) bármikor végrehajtja a következő műveleteket
Beolvas egy cellába írt karaktert
Lecseréli az ábécé egy másik karakterére A vagy ugyanazt hagyja
A szalag mentén egy cellával jobbra, balra mozog vagy a helyén marad
A Turing-gép ökölszabálya:
Turing gép, állapotban lenni q iés elolvassa a karaktert a j, ebbe a cellába írja a karaktert a k, bemegy az államba q e, műszakot végez. Ugyanakkor azt mondják, hogy a gép végrehajtott egy parancsot: a j q i® a k q e S SÎ (L, P, N)
A parancsgyűjteményt MT programnak nevezzük.
a j q i- a parancsok eredeti szimbólumainak eltérőnek kell lenniük. Ha ez a feltétel teljesül, a gépet hívják meghatározó , másképp - nem determinisztikus ... A gép meghatározott időpontokban működik.
Ily módon Teljes leírás A Turing-gép minden időpillanatban, amellyel meghatározható a további viselkedése, információkat tartalmaz a következőkről:
a gép belső állapota, a szalagra írt szó és a beolvasott karakter Ebben a pillanatban idő. A Turing-gép teljes állapotát hívják meg konfigurációt.
A Turing-gép működése konfigurációk sorozataként ábrázolható k 1® k 2®…® k n.
Az alapértelmezett kezdeti konfiguráció a bal szélső, nem üres karakter beolvasása az állapotba q 1
Szabványos végső konfiguráció – A gép belépett a végső állapotba:
Ha a gép belépett a végső állapotba, akkor erre a bemeneti szóra vonatkozik, ha korlátlan ideig fut, akkor a gép nem alkalmazható erre a szóra.
Az MT egy gyűjtemény, amely egy beviteli ábécéből, állapotok ábécéjéből és egy programból áll. M =
A gép programja a következőképpen állítható be:
1) a parancsok listája: a j q i® a k q n S
2) táblázat segítségével
| egy 0 | egy 1 | a 2 | |
| q 0 | a k, q m, S | ||
| q 1 |
3) predikátumgráf használatával (a csúcsok állapotok, minden parancs egy ívnek felel meg)
Turing gép tervezése:
A Turing-gép megalkotása annyit tesz, mint a program elkészítése. Két szakaszban zajlik:
1) a megoldandó probléma algoritmusának szóbeli leírása
2) az algoritmus szóbeli leírásának lefordítása a Turing-gép nyelvére (ehhez A, K, P)
Példa: készítsünk egy Turing-gépet, amely kiszámolja az f (n) = n + 1 függvényt, ahol n adott a bináris rendszerben.
A={0,1,egy 0), a Q halmaz a program felépítése során kerül meghatározásra.
Algoritmus:
1.A fej mozgatása a jobb szélső állapotból a bal szélső helyzetbe
2. ha a jobb szélső pozícióban a gép 0-t mutat, akkor tedd az 1-es cellába és állj meg, ha a fej 1-et, akkor tedd a 0-s cellába és lépj egy lépést balra.
Ismételje meg a 2. lépést
Példa: A szalag természetes decimális számot tartalmaz. Olyan Turing-gépet kell megszerkeszteni, amely ezt a számot 1-gyel növeli. Kezdetben a fej a szám első számjegyére mutat. A következőt kapjuk: A = (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, a 0), Q = (q 1, q 2, q 0). P - lásd a táblázatot.
| q 1 | 0> q 1 | 1> q 1 | 2> q 1 | 3> q 1 | 4> q 1 |
| q 2 | 1 = q 0 | 2 = q 0 | 3 = q 0 | 4 = q 0 | 5 = q 0 |
| egy 0 | |||||
| 5> q 1 | 6> q 1 | 7> q 1 | 8> q 1 | 9> q 1 | egy 0 |
| 6 = q 0 | 7 = q 0 | 8 = q 0 | 9 = q 0 | 0
|
Alapötlet - mozgassa a fejet a szám utolsó számjegyére, és ha ez a számjegy nem 9, akkor növelje eggyel, ellenkező esetben fordítsa nullára, és lépjen az előző cellába.
A gépek összetétele:
A gépek összeállítása két gép egymás utáni végrehajtása.
T 1=(A 1, Q 1, N 1) T 2=(A 2, Q 2, P 2) Q 1Ç Q 2=Æ
Fogalmazás gépek T 1° T 2 hívta az autót T(A, K, P), ahol A=A 1È A 2; K=(Q 1È Q 2)\{q 10} (q 10- végső állapot T 1). Autó T a következő szabály szerint működik: U- néhány szót, T(U)=T 1° T 2(U)=T 2(T 1(U))
Tétel. A gépek összetétele T 1° T 2 létezik.
Q 1={q 10, q 1,…, q n}
Q 2={q 20, q` 1 , …, q` n), majd a Q megalkotásához eltávolítjuk a q 10 állapotot, átnevezve a következőre q n +1, ami egybeesik a második gép kezdeti állapotával, és az összes többi állapot ebben van q` i = q n + 1 .
Turing-számított függvények:
Az f (x 1 ... x n) függvényt meghívjuk Turing kiszámítható ha van egy Turing-gép, amely kiszámolja ennek a függvénynek az értékét, ha megadja az argumentumok értékeit. Az f (x 1… x n) függvény adott a természetes számok halmazán, de az algoritmuselmélet a természetes számok NÈ (0) kiterjesztett halmazát veszi figyelembe.
Az f (x 1 ... x n) függvény argumentumai a szalagon a következő szóként vannak ábrázolva:
Minden érvnek annyi pálcája van, amennyi az érv értéke. Ha az f függvény az x 1 ... xn változó adott értékkészletén van definiálva, akkor a Turing-gép működése eredményeként ilyen számú pálcika maradjon sorba írva a szalag, amely megegyezik a függvény értékével ezen a halmazon. Ha az f függvény nincs definiálva egy adott halmazon, akkor a Turing-gépnek korlátlanul kell futnia.
Kezdeti konfiguráció - a bal szélső bot leolvasása.
