Gyakran különböző bonyolultságú feladatokat oldunk meg: hétköznapi, matematikai stb. Van, amelyik könnyen megoldható, van, amelyik sok átgondolást igényel, és van, amelyre soha nem találunk megoldást.

Általános esetben a probléma megoldásának módja (ha van ilyen) véges számú elemi művelettel írható le.

Például egy másodfokú egyenlet megoldása:

1. Alakítsa át az egyenletet kanonikus alakra \(a x^2 + b x + c = 0\)
2. Ha \(a=0\) , akkor ez egy lineáris egyenlet a \(x=\frac(-c)(b)\) megoldással. Probléma megoldódott. Ellenkező esetben folytassa a 3. lépéssel.
3. Számítsa ki a diszkriminánst \(D=b^2-4 a c\)
4. Számítsa ki az egyenletmegoldásokat \(x_(1,2) = \frac(-b\pm\sqrt(D))(2 a)\). Probléma megoldódott.

Bevezethetjük az algoritmus következő intuitív fogalmát:

Az algoritmus egy olyan utasításkészlet, amely leírja azt az eljárást, amellyel az előadónak véges számú művelettel kell elérnie a probléma megoldásának eredményét bármely kezdeti adathalmaz esetén.

Ez természetesen nem szigorú definíció, de leírja az algoritmus fogalmának lényegét.

Az algoritmusokat egy adott alapján állítják össze előadó, ezért olyan nyelven kell lennie, amelyet az előadó megérthet.

Az algoritmus végrehajtója lehet egy személy, vagy lehet számítógép, vagy más automata, például szövőszék.

Az algoritmusok következő tulajdonságait különböztetjük meg:

Az algoritmus diszkrétsége különálló, jól definiált lépések (műveletek) bizonyos sorozatának kell lennie. Ezen műveletek mindegyikének időbeli végesnek kell lennie. A meghatározottság az algoritmus minden lépésénél, a következő lépést egyedileg a rendszer aktuális állapota határozza meg. Ennek következtében az algoritmus ugyanazon kiindulási adatokon mindig ugyanazokat az eredményeket adja vissza, függetlenül attól, hogy hányszor kerül végrehajtásra. Érthetőség Az algoritmust az előadó számára érthető nyelven kell megfogalmazni. Ha számítógépről beszélünk, akkor az algoritmus csak azokat a parancsokat használja, amelyeket a számítógép ismer, és amelyek műveleteinek eredménye szigorúan meghatározott. Végesség Az algoritmusnak véges számú lépésben kell végrehajtania. Az algoritmus tömegkarakterének alkalmazhatónak kell lennie a különböző bemeneti adatokra. Vagyis az algoritmusnak alkalmasnak kell lennie a megoldásra osztály feladatokat. Visszatérve a másodfokú egyenlet példájára, az algoritmus alkalmas a megoldásra minden másodfokú egyenletek, nem csak egy vagy több. Az algoritmusnak egy bizonyos eredménnyel kell végződnie. Mondjuk egy probléma megoldásával vagy a megoldások hiányának megállapításával. Ha az algoritmus nem vezet eredményre, akkor nem világos, hogy egyáltalán miért van rá szükség.

A probléma megoldásának nem minden módja egy algoritmus. Tegyük fel, hogy az algoritmus nem tartalmaz választási lehetőséget. Például a legtöbb főzési recept nem algoritmus, mert olyan kifejezéseket használ, mint a „sózzuk ízlés szerint”. Ennek következtében a determinizmus követelménye sérül.

Nem minden problémára, amelyre van megoldás, létezik megoldási algoritmus is. Például a képfelismerés problémája még mindig nagyrészt megoldatlan, és természetesen nem egy szigorú algoritmus segítségével. A neurális hálózatok használata azonban elég jó eredményeket ad.

Általában egy algoritmushoz vannak halmazok elfogadható beviteli adat. Furcsa lenne egy egyenletmegoldó algoritmust alkalmazni a vacsora főzésére, vagy fordítva.

Ezen túlmenően a végrehajtó lehetséges cselekményeinek köre is korlátozott, hiszen ha bármilyen cselekmény megengedhető lenne, akkor közöttük kellene „megengedhetetlennek” is lennie.

Az algoritmus szigorú meghatározása

A fent megadott algoritmus-definíció nem szigorú. Ez bizonyos nehézségeket okoz. Egy ilyen definícióval különösen lehetetlen szigorúan bizonyítani, hogy egy adott problémaosztály megoldható-e egy algoritmussal.

Kiderült, hogy van egy osztály algoritmikusan megoldhatatlan problémák- olyan problémák, amelyek megoldására nem lehet algoritmust létrehozni. De ahhoz, hogy szigorúan bizonyítsuk az algoritmus eldönthetetlenségét, először szigorúan meg kell határozni az algoritmust.

A XX. század 20-30-as éveiben különböző matematikusok dolgoztak az algoritmus szigorú meghatározásának problémáján, különösen Alan Turing, Emil Leon Post, Andrey Andreevich Markov, Andrey Nikolaevich Kolmogorov, Alonzo Church és mások. Munkájuk végül elvezetett az algoritmusok elméletének, a kiszámíthatóság elméletének és a számítások különféle megközelítéseinek megjelenéséhez és fejlődéséhez, és mellesleg a programozáshoz általában. Munkájuk egyik eredménye az algoritmus számos szigorú definíciójának megjelenése volt, amelyeket különböző módon vezettek be, de egymással egyenértékűek.

Részletesen kitérünk Turing definíciójára, és átfutjuk Post, Church és Markov egyenértékű definícióit.

Turing gép

Az algoritmus formális definíciójának bevezetésére Turing feltalált és leírt egy absztrakt számítógépet, amelyet Turing-számítógépnek, vagy egyszerűen csak Turing-gépnek neveznek.

Alan Turing (1912-1954)

Egy angol matematikus, logikus, kriptográfus, talán a világ első "hackere" állt a számítástechnika és a mesterséges intelligencia elméletének eredeténél. Jelentősen hozzájárult a szövetséges erők győzelméhez a második világháborúban.

A Turing-gép bemeneteként használják a szavak, némelyikkel összeállítva ábécé, vagyis egy készlet karakterek.

A Turing-gép kimenete szintén szavak.

Azt a szót, amelyre az algoritmust alkalmazzák, hívják bemenet. A szó, amely a munka eredménye hétvége.

Meghívjuk azt a szókészletet, amelyre az algoritmust alkalmazzuk az algoritmus hatóköre.

Szigorúan véve lehetetlen bizonyítani, hogy bármely tárgy ábrázolható-e valamilyen ábécében összeállított szavak formájában - ehhez szükségünk lenne az objektum szigorú meghatározására. Ellenőrizhető azonban, hogy bármely véletlenszerűen kiválasztott, objektumon működő algoritmus átalakítható úgy, hogy az algoritmus lényegének megváltoztatása nélkül működjön szavakon.

A Turing-gép leírása

A Turing-gép összetétele tartalmaz egy mindkét irányban korlátlan, cellákra osztott szalagot és egy vezérlőeszközt (ún. olvasó/író fej, vagy egyszerűen gép), amely a sok állapot egyikében lehet. A vezérlőkészülék lehetséges állapotainak száma véges és pontosan adott.

A vezérlőeszköz balra-jobbra mozoghat a szalagon, beolvashat és a cellákba írhat valamilyen véges ábécé karaktereit. A rendszer egy speciális üres karaktert foglal le, amelyet \(a_0\) vagy \(\Lambda\) jelöl, amely kitölti a szalag összes celláját, kivéve azokat (véges szám), amelyekre a bemeneti adatok vannak írva.

A vezérlőeszköz az átmeneti szabályok szerint működik, amelyek a Turing-gép által megvalósított algoritmust reprezentálják. Mindegyik átmeneti szabály arra utasítja a gépet, hogy az aktuális állapottól és az aktuális cellában megfigyelt szimbólumtól függően új szimbólumot írjon ebbe a cellába, lépjen az új állapotba, és mozgassa egy cellát balra vagy jobbra. A Turing-gép egyes állapotai terminálisnak jelölhetők, és ezek bármelyikére való átállás a munka végét, az algoritmus leállását jelenti.

Míg a Turing-gép egy elvont fogalom, elég könnyű elképzelni egy ilyen gépet (bár véges szalaggal), és vannak még ilyen demonstrációs gépek is:

A Turing-gép algoritmusát célszerű táblázat formájában ábrázolni: a táblázat oszlopai a szalagon lévő aktuális (megfigyelt) karakternek, a sorok az automata aktuális állapotának felelnek meg, a cellák pedig rögzítenek. a parancs, amelyet az automatának végre kell hajtania.

A parancs pedig a következő felépítésű lehet:

\[ a_k \left\lbrace \begin(mátrix) L \\ N \\ R \end(mátrix)\right\rbrace q_m \]

Először jön az ábécé karaktere, amelyet az aktuális cellába kell írni \(a_k\) , majd az automata mozgása balra (L), jobbra (R) vagy sehova (maradjon a helyén, N) jelzett. A végén megjelenik egy új állapot, amelybe a \(q_m\) automatának be kell mennie.

A táblázat celláját egyértelműen az aktuális karakter \(a_i\) és az automata aktuális állapota \(q_j\) határozza meg.

Egyezzünk meg abban, hogy a munka elején a Turing-gép be van kapcsolva kezdeti állapot, jelölése \(q_1\) , és átlépéskor stop állapot\(q_0\) az algoritmus befejeződött, és a gép leáll.

Példa

Írjunk egy algoritmust egy Turing-gépre, amely 1-et ad a bemeneti szóhoz, ami egy decimális szám.

Ezután leíró jelleggel az algoritmus a következőképpen fogalmazható meg:

1. Jobbra haladva keresse meg a beviteli szó elejét
2. Jobbra haladva keresse meg a beviteli szó végét
3. Adjon hozzá egyet a bemeneti szó aktuális bitjéhez. Ha van egy szám 0 és 8 között, lépjen ki. Ellenkező esetben írjon 0-t, lépjen balra, és térjen vissza a 3. lépéshez.

Ezt az algoritmust táblázat formájában írjuk fel. Az ábécé 0 és 9 közötti számokból és az „üres karakterből” \(\Lambda\) áll. Szükségünk van még az automata 4 állapotára, a stop állapotot számolva, az algoritmus leírásának lépései szerint.

Egyetértünk abban, hogy az \(1\) kezdeti állapot a bemeneti szó elejét keresi, a \(2\) a bemeneti szó végét, a \(3\) pedig az 1 hozzáadása.

Nézzük meg, hogyan működik ez az algoritmus egy példán keresztül. Az első sor a szalagnak felel meg, a második a gép helyzetét és pillanatnyi állapotát jelzi.

Az 1. állapotban az automata egy üres cella felett van. A megfelelő parancs a „ΛP1” táblázatból, azaz hagyja üresen a cellát, lépjen jobbra, és maradjon az 1-es állapotban:

Most az automata „1” értéket észlel. A megfelelő parancs „1H2”, azaz hagyja az „1”-et a cellában, ne mozduljon el, és lépjen „2” állapotba:

„2” állapotban a gép az „1” értéket figyeli. A megfelelő parancs „1P2”, azaz hagyja el az „1”-et, lépjen jobbra, és maradjon „2” állapotban:

A helyzet megismétlődik:

Most a 3-as állapotban és a „9” szimbólumot figyelve az automata végrehajtja a „0L3” parancsot:

A helyzet megismétlődik:

„0” állapot – stop állapot. Az algoritmus elkészült.

Formális leírás

Matematikailag a Turing-gép a következőképpen írható le:

Turing gép (MT)

ez a forma rendszere \(\(A, a_0, Q, q_1, q_0, T, \tau\)\), ahol

• Az \(A\) az MT ábécé véges szimbólumkészlete
• \(a_0 \in A\) – az ábécé üres karaktere
• \(Q\) – MT állapotok véges halmaza
• \(q_1 \in Q\) – az MT kezdeti állapota
• \(q_0 \in Q\) – MT végső állapot (stop állapot)
• \(T = \(L, P, H\)\) az MT eltolásainak halmaza
• \(\tau\) – MT program, vagyis a leképezést meghatározó függvény \(\tau: A\times Q\backslash \(q_0\) \rightarrow A\times T \times Q\)

Az algoritmusok elméletének kulcsa az Turing tézise.

Lazán megfogalmazva Turing tézise a következő:

Turing tézise Bármilyen algoritmikusan megoldható probléma esetén létezik egy Turing-gép, amely megoldja ezt a problémát. egyébként minden algoritmushoz létezik egyenértékű Turing-gép.

Turing tézise lehetővé teszi, hogy egy meglehetősen egyszerű matematikai apparátus segítségével beszéljünk algoritmusokról. Ráadásul maga a Turing-gép is az univerzális működtető eszköz, és egy ilyen képzeletbeli gép létrehozásának lehetősége is alkalmat adott arra, hogy beszéljünk az univerzális számítástechnika létrehozásáról.

Alternatív algoritmus-definíciók

A Turing-gépen kívül számos független definíció létezik, amelyek egyenértékűek a Turing-definícióval.

Különösen a postagépen, a Church lambda-számításon, a normál Markov-algoritmuson keresztül történő definíció.

Tekintsük ezeket a módszereket.

Postagép

Egy évvel Turing után Emil Leon Post amerikai matematikus önállóan javasolt egy másik absztrakt univerzális számítógépet, amely némileg leegyszerűsíti a Turing-féle számítógépet.

A Postaautomata kétjegyű ábécével működik, az automata belső állapotát helyettesíti programsor.

Egyébként a Postagép hasonló a Turing-géphez: van egy automata, és van egy végtelen cellás szalag.

A Postagép a következő parancsokat tudja végrehajtani:

1. Írjon 1-et, lépjen a program i-edik sorába
2. Írjon 0-t, lépjen a program i-edik sorába
3. Váltás balra, menjen a program i-edik sorába
4. Váltás jobbra, menjen a program i-edik sorába
5. Feltételes elágazás: ha a megfigyelt cella 0, akkor menjen a program i-edik sorába, ellenkező esetben lépjen a program j-edik sorába.
6. Állj meg.

A Postagépnek több tiltott parancsa is van:

1. Írjon az 1-es cellába, amikor már van 1.
2. Írás a 0-s cellába, amikor már 0 van.

Az ilyen események összeomláshoz vezetnek.

A következő jelöléssel írhatunk programokat a postagéphez:

1. ∨ i - írjon 1-et, lépjen a program i-edik sorába
2. × i – írjon 0-t, lépjen a program i-edik sorába
3. ← i - balra váltás, ugrás a program i-edik sorába
4. → i - eltolás jobbra, ugrás a program i-edik sorára
5. ? én; j – feltételes átmenet: ha a megfigyelt cella 0, lépjen a program i-edik sorába, ellenkező esetben a program j-edik sorába.
6. ! - állj meg.

Program példa:

1. → 2 2. ? egy; 3 3. × 4 4. ← 5 5. !

Ez a program törli az első címkét (1) az automata kezdőpozíciójától jobbra, és leállítja az automatát a bal oldali cellában.

Nagyjából a Postagép az előfutár parancsoló programozási nyelvek, mint a C, Fortran stb.

A Postagép egyenértékű a Turing-géppel. Más szóval, bármely Turing-gép programhoz írhatunk egyenértékű postagépi programot, és fordítva.

Ennek az egyenértékűségnek az egyik fontos következménye az bármely ábécé bináris kódra redukálható.

Turing téziséhez hasonlóan itt is létezik Post tézise.

Post tézise Minden algoritmus ábrázolható Postagépként.

Normál Markov algoritmus

A normál Markov-algoritmusokat úgy tervezték, hogy különféle ábécé szavakra alkalmazzák.

Minden normál algoritmus definíciója két részből áll:

1. ábécé algoritmus
2. Rendszer algoritmus

Magára az algoritmusra alkalmazzák szavak, azaz karaktersorozatok ábécé.

A normál algoritmus sémája véges rendezett halmaz ún helyettesítési képletek, amelyek mindegyike lehet egyszerű vagy végső. Az egyszerű helyettesítési képletek \(L\-D\) formájú kifejezések, ahol \(L\) és \(D\) az algoritmus ábécéjéből összeállított két tetszőleges szó (ezt a bal és jobb oldali résznek nevezik a helyettesítési képlet). Hasonlóképpen, a végső helyettesítési képletek \(L\to\cdot D\) formájú kifejezések, ahol \(L\) és \(D\) az algoritmus ábécéjéből összeállított két tetszőleges szó.

Feltételezzük, hogy a \(\to\) és \(\to\cdot\) segédkarakterek nem tartoznak az algoritmus ábécéjéhez.

A normál algoritmus tetszőleges \(V\) szóra történő alkalmazásának folyamata a következő műveletsor:

1. Legyen \(V"\) az algoritmus előző lépésében kapott szó (vagy az eredeti szó, ha az aktuális lépés az első).
2. Ha a helyettesítési képletek között nincs olyan, amelynek a bal oldali része benne lenne \(V"\) -ben, akkor az algoritmus munkája befejezettnek, a \(V"\) szó pedig a \(V"\) szó eredményének tekinthető. ez a munka.
3. Ellenkező esetben a helyettesítési képletek közül, amelyek bal oldali részét \(V"\) tartalmazza, a legelső kerül kiválasztásra.
4. A \(V"\) szó \(RLS\) formában (ahol \(R\) egy előtag, és \(L\) egy utótag) lehetséges ábrázolásai közül az egyiket úgy kell kiválasztani, hogy \(R) \) a legrövidebb , amely után a \(V"=RDS\) behelyettesítés történik.
5. Ha a helyettesítési képlet véges volt, akkor az algoritmus a \(V"\) eredménnyel zárult. Ellenkező esetben folytassa az 1. lépéssel (következő lépés).

Bármely normál algoritmus egyenértékű valamilyen Turing-géppel, és fordítva, bármely Turing-gép egyenértékű valamilyen normál algoritmussal.

A Turing-tézis analógját a normál algoritmusokra általában ún normalizálási elv.

Példa

Ez az algoritmus a bináris számokat „egyes” számokká alakítja (amelyben egy N nem negatív egész szám rekordja N pálcikából álló karakterlánc). Például a 101-es bináris szám 5 pálcikává alakul: |||||.

Ábécé: ( 0, 1, | ) Szabályok:

1. 1 → 0|
2. |0 → 0||
3. 0 → (üres karakterlánc)

1. 0|00|
2. 00||0|
3. 00|0|||
4. 000|||||
5. 00|||||
6. 0|||||
7. |||||

Rekurzív függvények

A Turing-géppel egyenértékű rendszer matematikai függvények alapján építhető fel. Ehhez a következő függvényosztályokat kell bevezetnünk:

• primitív rekurzív függvények
• általános rekurzív függvények
• részben rekurzív függvények

Az utolsó osztály megegyezik a Turing-számítható függvények osztályával (azaz olyan függvényekkel, amelyeket egy Turing-gép algoritmusa kiértékelhet).

Az algoritmus rekurzív függvények szerinti meghatározása lényegében a lambda-számítás alapját képezi, és a megközelítés is erre épül. funkcionális programozás.

Primitív rekurzív függvények

A primitív rekurzív függvények osztálya tartalmazza alapvető funkciókatés az alapfüggvényekből az operátorok segítségével nyert összes függvény helyettesítésekés primitív rekurzió.

Az alapvető funkciók a következők:

• A \(O()=0\) nullfüggvény egy argumentum nélküli függvény, amely mindig a \(0\) értéket adja vissza.
• Az \(S(x)=x+1\) szukcessziós függvény egy olyan függvény, amely bármilyen \(x\) természetes számot társít a következő számhoz: \(x+1\)
• Funkciók \(I_n^m(x_1,\ldots,x_n) = x_m\), ahol \(0

A többi osztályfüggvény összeállításához a következő operátorokat kell használni:

• Helyettesítések. \(m\) változóból álló \(f\) függvény és \(n\) változóból \(g_1,\ldots,g_m\) függvény esetén a \(g_k\) helyettesítésének eredménye in \( f\) egy függvény \(h(x_1,\ldots,x_n) = f(g_1(x_1,\ldots,x_n),\ldots,g_m(x_1,\ldots,x_n))\)\(n\) változókból.
• primitív rekurzió. Legyen \(f(x_1,\ldots,x_n)\) \(n\) változó függvénye, \(g(x_1,\ldots,x_(n+2))\) pedig \( n+ 2\) változó. Ekkor a primitív rekurziós operátor \(f\) és \(g\) függvényekre történő alkalmazásának eredménye a \(n+1\) változó \(h\) függvénye a következő formában: \[ h(x_1,\ldots,x_n,0) = f(x_1,\ldots,x_n) \] \[ h(x_1,\ldots,x_n,y+1) = g(x_1,\ldots,x_n, y, h(x_1,\ldots,x_n,y)) \]

Részben rekurzív függvények

A részlegesen rekurzív függvények osztályába tartoznak a primitív rekurzív függvények, és ezen kívül minden olyan függvény, amely primitív rekurzív függvényekből származik az argumentumminimalizálási operátor használatával:

Érvminimalizáló operátor

Legyen \(f\) a \(n\) \(x_i \in \mathbb(N)\) változók függvénye. Ekkor az argumentumminimalizálási operátor \(f\) függvényre történő alkalmazásának eredménye az \(n-1\) argumentum \(h\) függvénye, a következőképpen definiálva:

\[ h(x_1,\ldots,x_(n-1)) = \min y, \] ahol \ Ez azt jelenti, hogy a \(h\) a \(f\) függvény utolsó argumentumának minimális értékét adja vissza, amelynél az \(f\) értéke nulla.

Míg a primitív rekurzív függvények mindig kiszámíthatók, a részben rekurzív függvények bizonyos argumentumértékeknél definiálatlanok lehetnek.

Pontosabban, a részlegesen rekurzív függvényeket "részlegesen meghatározott rekurzív függvényeknek" kell nevezni, mivel ezek csak az argumentumok lehetséges értékeinek egy részén vannak definiálva.

Általános rekurzív függvények

Az általános rekurzív függvények az összes argumentumértékhez definiált részlegesen rekurzív függvény alosztálya. Az a probléma, hogy egy adott részben rekurzív függvény általános rekurzív-e algoritmikusan eldönthetetlen. Ezzel el is érkeztünk a kiszámíthatóság elméletéhez és a megállási problémához.

A kiszámíthatóság elmélete és a megállási probléma

Képzeletünk összességében elismeri a megoldhatatlan problémák létezését, vagyis olyan problémákat, amelyekre nem lehet algoritmust összeállítani.

A kiszámíthatóság elmélete ilyen problémák vizsgálatával foglalkozik.

Példák az algoritmikusan megoldhatatlan problémákra stop problémaés levezethetőség felismerési probléma. Tekintsük őket részletesebben.

A leállítási probléma Az A algoritmus leírása és a \(x\) bemenet ismeretében meg kell találni, hogy az \(A\) algoritmus megáll-e az \(x\) bemeneten.

A leállítási probléma algoritmikusan eldönthetetlen. Bizonyítsuk be.

Legyen egy univerzális algoritmus, amely megoldja a megállási problémát. Tekintsük ezután az algoritmusok egy osztályát, amely algoritmusokat leíró szövegeket dolgoz fel.

A leállítási probléma megoldására egy univerzális algoritmus létezése miatt van egy algoritmus, amely meghatározza, hogy az említett osztályból származó algoritmus megáll-e a saját szövegén vagy sem. Jelöljön egy ilyen algoritmust \(B\) .

Építsünk egy \(C\) algoritmust, aminek a bemenete az \(A\) algoritmus szövege, amely a saját szövegét dolgozza fel:

1. Futtassa a \(B\) algoritmust a \(A\) helyen.
2. Ha a \(B\) algoritmus megállapítja, hogy az \(A\) megáll a szövegénél, folytassa az 1. lépéssel. Ellenkező esetben folytassa a 3. lépéssel.
3. A \(C\) algoritmus vége.

A \(C\) algoritmust próbálva alkalmazni a \(C\) algoritmusra, nyilvánvaló ellentmondáshoz jutunk: ha \(C\) megáll a saját szövegénél, akkor nem állhat meg, és fordítva. Ezért nincs \(B\) algoritmus. \(\nem \Delta\)

A megállási probléma általánosabb megfogalmazása a származtathatóság meghatározásának problémája.

A levezethetőség felismerésének problémája

Legyen definiálva egy bizonyos ábécé, ennek az ábécé szavai (képletei), és az ábécé szavai feletti formális transzformációk rendszere (azaz logikai kalkulus épül fel)

Létezik-e bármely két \(R\) és \(S\) szóra \(R\)-től \(S\)-ig vezető deduktív lánc az adott logikai számításon belül?

1936-ban Alonzo Church bebizonyította Church tételét.

Church tétele A levezethetőség felismerésének problémája algoritmikusan eldönthetetlen.

Church a lambda-számítás formalizmusát használta ennek bizonyítására. 1937-ben, tőle függetlenül, Turing a Turing-gép formalizmusával bebizonyította ugyanezt a tételt.

Mivel az algoritmusok összes definíciója ekvivalens egymással, létezik egy olyan fogalomrendszer, amely nem kapcsolódik egy algoritmus konkrét definíciójához, és a fogalommal működik. kiszámítható függvény.

A kiszámítható függvény olyan függvény, amely egy algoritmussal kiértékelhető.

Vannak olyan problémák, amelyekben a bemeneti és kimeneti adatok közötti kapcsolat nem írható le algoritmussal. Ilyen tulajdonságok kiszámíthatatlan.

Példa egy nem kiszámítható függvényre

Vegyük a \(h(n)\) függvényt, amely a \(\forall n \in \mathbb(N)\) függvényben van definiálva:

\[ h(n) = \begin(esetek) 1, & \text(if )\pi\text( pontosan )n\text( 9.) \\ 0, & \text(egyébként ) \end( esetek) \]

Ehhez a függvényhez megkaphatjuk a \(1\) értéket, azonban a \(0\) értékhez ellenőriznünk kell a \(\pi\) szám végtelen decimális kiterjesztését, ami végesben nyilvánvalóan lehetetlen idő. Ez a függvény tehát nem számítható.

Tegyük fel, nagyon régen... De valójában a Turing-gép létrehozása előtt gépeket hoztak létre különféle műveletek végrehajtására. Például fel kell venni a logaritmust, nos, szegecseljünk egy gépet, amely beolvassa a számot és felveszi a logaritmust. Vagy mondjuk hozzá kell adni két számot – itt van egy gép két szám összeadására. Igen, és most vannak ilyen gépek, például számológépek. Mit tehetnek? Összeadás, kivonás, szorzás és tervezés – akár koszinusz vagy szinusz is. Kiderült, hogy ezek a hülye gépek a bennük rögzített műveleteken kívül semmit nem tudtak és nem is tudnak végrehajtani.

Nagyon érdekes lenne tehát egy olyan gépet készíteni, ami nem számokat vagy szimbólumokat olvasna, hanem egy algoritmust, és azt végrehajtaná, vagyis létrehozna egy programozható gépet. Ezt tette Turing (mondom, hogy Turingén kívül sok ilyen absztrakció van). És előállt egy ilyen gép modelljével. Kiderült, hogy az összetett algoritmusok végrehajtásához nem kell más, mint egy kazetta, egy végtelenített szalag, valamint a szalagra írt értékek megváltoztatásának és azon való mozgásának képessége. Kiderült, hogy ebből az absztrakcióból tulajdonképpen valódi gépet is lehet csinálni, csak azzal a korláttal, hogy végtelen szalaggal nem tudjuk ellátni a gépet, de nagyon hosszú szalagot készíthetünk;)

Visszavonulás. Valójában nem kell elmondani, hogyan működik a Turing-gép, mint mondtam, nagyon könnyen megtalálható. Ezért feltételezzük, hogy már tudja, hogyan működik.

Nos, a Turing-gép végrehajt néhány egyszerű algoritmust, ez vitathatatlan. De mi a helyzet a komplexekkel? És például hogyan lehet ciklust szervezni az MT segítségével? Vagy hogyan lehet kitalálni az elágazást? Kiderült, hogy vannak olyan tételek, amelyek bizonyítják, hogy az MT képes ciklusokat és elágazásokat végrehajtani, ami azt mondja nekünk, hogy egy nagyon egyszerű mechanizmussal egyszerű blokkokból, például ágakból és hurkokból lehet programokat összeállítani, ami azt jelenti, hogy mindent programozhat, ami csak lehetséges. programozott. És itt elméletileg kellene egy kis magyarázat, hogy vannak nem számítható függvények is, tehát megoldhatatlan problémák is, és ezeket a problémákat nem lehet MT segítségével megoldani. Itt van, hogyan.

De senki sem talált ki menőbbet, mint egy Turing-gép, így az általunk használt összes programozási nyelv nem tud többet programozni, mint egy Turing-gép. Innen származik a Turing-teljesség fogalma, ami azt jelenti, hogy egy nyelv (vagy valami más) akkor Turing-teljes, ha képes megírni az összes Turing-gépen futó algoritmust. És bebizonyíthatja, hogy a nyelv Turing-teljes, ha ír rá egy Turing-gép emulátort. Ezek a piték.

Matematika szempontjából baromság a poszt, de egyértelmű, minek, kellett egy Turing-gép. Nos, az algoritmusok írása ehhez a géphez egy érdekes rejtvény. Elhiszem azoknak, akik azt mondják, hogy miután Turing gépen programozta az exp(x)-et, igazán megértette, mi az az algoritmus. Még nem próbáltam, de érdekes kihívás.

A Turing-gép a 20. század egyik legérdekesebb és legizgalmasabb szellemi felfedezése. Ez a számítástechnika (számítógépes és digitális) egyszerű és hasznos absztrakt modellje, amely elég általános bármilyen számítógépes feladat végrehajtásához. Egyszerű leírásának és matematikai elemzésének köszönhetően az elméleti számítástechnika alapját képezi. Ez a kutatás a digitális számítógépek és a számítástechnika mélyebb megértéséhez vezetett, beleértve azt a felismerést, hogy vannak olyan számítási problémák, amelyeket általános felhasználói számítógépeken nem lehet megoldani.

Mi ez és ki készítette

Alan Turing egy mechanikus eszköz legprimitívebb modelljét próbálta leírni, amely ugyanazokkal az alapvető képességekkel rendelkezik, mint egy számítógép. Turing először 1936-ban írta le a gépet "On Computable Numbers with an Application to the Decidability Problem" című könyvében, amely a Proceedings of the London Mathematical Society-ben jelent meg.

A Turing-gép egy olyan számítástechnikai eszköz, amely egy olvasó/író fejből (vagy "szkennerből") áll, amelyen egy papírszalag fut át. A szalag négyzetekre van osztva, amelyek mindegyikén egyetlen szimbólum látható - "0" vagy "1". A mechanizmus célja, hogy egyrészt be- és kilépési eszközként, másrészt munkamemóriaként szolgáljon a számítások közbenső szakaszainak eredményeinek tárolására.

Miből készült a készülék?

Mindegyik ilyen gép két részből áll:

1. Korlátlan szalag. Mindkét irányban végtelen, és cellákra oszlik.
2. A gép egy vezérelt program, egy lapolvasó fej az adatok olvasására és írására. Bármelyik pillanatban a sok állapot egyikében lehet.

Mindegyik gép két véges adatsort kapcsol össze: az A = (a0, a1, ..., am) bemeneti szimbólumok ábécéjét és a Q = (q0, q1, ..., qp) állapotok ábécéjét. A q0 állapotot passzívnak nevezzük. Úgy gondolják, hogy a készülék akkor fejezi be a munkáját, amikor eltalálja. A q1 állapotot kiindulási állapotnak nevezzük - a gép elkezdi a számításokat, és abban az elején áll. A beviteli szó minden pozícióban egy betűvel kerül a szalagra. Mindkét oldalán csak üres cellák találhatók.

Hogyan működik a mechanizmus

A Turing-gép alapvető különbséggel rendelkezik a számítástechnikai eszközökkel szemben - tárolóeszköze végtelen szalaggal rendelkezik, míg a digitális eszközök esetében egy ilyen eszköz egy bizonyos hosszúságú szalaggal rendelkezik. Minden feladatosztályt csak egy megszerkesztett Turing-gép old meg. A különböző típusú feladatok egy új algoritmus írását foglalják magukban.

A vezérlőeszköz egy állapotú lévén a szalag mentén bármely irányba mozoghat. A cellákba ír, és kiolvassa belőlük a végső ábécé karaktereit. Az áthelyezés során egy üres elem kerül kiosztásra, amely kitölti a bemeneti adatokat nem tartalmazó pozíciókat. A Turing-gép algoritmusa határozza meg a vezérlőeszköz átmeneti szabályait. A következő paramétereket állítják be az író-olvasó fejbe: új karakter írása a cellába, áttérés új állapotba, mozgás balra vagy jobbra a szalagon.

Mozgás tulajdonságai

A Turing-gépnek, mint más számítástechnikai rendszereknek, megvannak a benne rejlő jellemzői, és ezek hasonlóak az algoritmusok tulajdonságaihoz:

1. diszkrétség. A digitális gép csak az előző befejezése után lép tovább a következő n+1 lépésre. Minden befejezett lépés kijelöli, hogy mi lesz az n+1.
2. Világosság. A készülék ugyanahhoz a cellához csak egy műveletet hajt végre. Beír egy karaktert az ábécéből, és egyetlen mozgást végez: balra vagy jobbra.
3. Határozottság. A mechanizmusban minden pozíció az adott séma egyetlen változatának felel meg, és minden szakaszban a cselekvések és végrehajtásuk sorrendje egyértelmű.
4. Hatékonyság. Az egyes lépések pontos eredményét a Turing-gép határozza meg. A program végrehajtja az algoritmust és véges számú lépésben átjut a q0 állapotba.
5. Tömegjelleg. Minden eszköz az ábécében szereplő engedélyezett szavak felett van meghatározva.

A Turing-gép funkciói

Az algoritmusok megoldása során gyakran van szükség függvény implementációra. Attól függően, hogy lehetséges-e láncot írni a számításhoz, a függvényt algoritmikusan eldönthetőnek vagy eldönthetetlennek nevezzük. Természetes vagy racionális számok halmazaként egy gépnél egy véges N ábécé szavakat, egy B halmaz sorozatát tekintjük - szavak a B=(0.1) bináris kód ábécé keretében. Ezenkívül a számítás eredménye figyelembe veszi azt a „meghatározatlan” értéket, amely akkor fordul elő, amikor az algoritmus „lefagy”. A funkció megvalósításához fontos, hogy a véges ábécében legyen formális nyelv, és megoldható legyen a helyes leírások felismerésének problémája.

Eszköz szoftver

A Turing-mechanizmus programjai táblázatokba vannak rendezve, amelyekben az első sor és oszlop tartalmazza a külső ábécé szimbólumait és az automata lehetséges belső állapotainak értékeit - a belső ábécét. A táblázatos adatok olyan parancsok, amelyeket a Turing-gép elfogad. A problémamegoldás a következőképpen zajlik: a fej által beolvasott betű abban a cellában, amely felett éppen található, és az automatafej belső állapota határozza meg, hogy melyik parancsot kell végrehajtani. Pontosabban, egy ilyen parancs a külső ábécé és a belső ábécé szimbólumainak metszéspontjában található, a táblázatban.

Komponensek a számításokhoz

Egy adott probléma megoldására szolgáló Turing-gép felépítéséhez a következő paramétereket kell meghatározni.

külső ábécé. Ez egy véges szimbólumhalmaz, amelyet az A jellel jelölünk, és amelynek alkotóelemeit betűknek nevezzük. Az egyiknek – a0-nak – üresnek kell lennie. Például egy bináris számokkal dolgozó Turing-eszköz ábécéje így néz ki: A = (0, 1, a0).

A szalagra rögzített betűk-szimbólumok folyamatos láncolatát szónak nevezzük.

Az automata olyan eszköz, amely emberi beavatkozás nélkül működik. A Turing-gépben több különböző állapota van a problémák megoldására, és bizonyos feltételek mellett egyik pozícióból a másikba mozog. Az ilyen kocsiállapotok halmaza a belső ábécé. Olyan betűjellel rendelkezik, mint Q=(q1, q2...). Ezen pozíciók egyike - q1 - legyen a kezdő, vagyis az, amelyik elindítja a programot. Egy másik szükséges elem a q0 állapot, amely a végső állapot, vagyis az, amelyik befejezi a programot és a készüléket leállítási helyzetbe állítja.

Ugróasztal. Ez a komponens az eszköz kocsi viselkedésének algoritmusa, a gép aktuális állapotától és az olvasott karakter értékétől függően.

Algoritmus az automatához

A Turing-eszköz szállítását működés közben egy program vezérli, amely minden lépésben a következő műveletek sorozatát hajtja végre:

1. A külső ábécé karakterének írása egy pozícióba, beleértve az üreset is, a benne található elem cseréje, beleértve az üreset is.
2. Mozgassa egy lépcsős cellát balra vagy jobbra.
3. Változtasd meg a belső állapotodat.

Így az egyes karakterpárokra vagy pozíciókra vonatkozó programok írásakor három paramétert kell pontosan leírni: a i - egy elem a kiválasztott A ábécéből, a kocsieltolás iránya ("←" balra, "→" a jobb, "pont" - nincs mozgás) és q k - az eszköz új állapota Például az 1. parancs "←" q 2 jelentése "cserélje ki a karaktert 1-gyel, mozgassa a kocsifejet egy lépéscellával balra, és tegye az átmenet a q 2 állapotba”.

Turing gép: példák

1. példa A feladat egy olyan algoritmus megalkotása, amely a szalagon található adott szám utolsó számjegyéhez hozzáad egyet. Bemeneti adatok - szó - egy egész decimális szám számjegyei, a szalagon egymás utáni cellákba írva. A kezdeti pillanatban az eszköz a jobb szélső karakterrel - a szám számjegyével - szemben található.

Döntés. Ha az utolsó számjegy 9, akkor azt 0-ra kell cserélni, majd hozzáadni egyet az előző karakterhez. A program ebben az esetben egy adott Turing-eszközhöz így írható fel:

Itt q 1 a számjegy megváltoztatásának állapota, q 0 a stop. Ha q 1-ben az automata a 0..8 sorból rögzít egy elemet, akkor azt rendre lecseréli az 1..9 egyikére, majd q 0 állapotba kapcsol, vagyis a készülék leáll. Ha a kocsi rögzíti a 9-es számot, akkor 0-ra cseréli, majd balra mozog, megállva q 1 állapotban. Ez a mozgás addig folytatódik, amíg a készülék ki nem rögzít egy 9-nél kisebb számjegyet. Ha minden karakter egyenlő 9-cel, akkor nullákra cseréljük őket, a legmagasabb elem helyére 0 kerül, a kocsi balra mozog, és 1-et ír egy üres cella. A következő lépés az átmenet a q 0 - stop állapotba.

2. példa Adott a nyitó és záró zárójeleket jelölő szimbólumok sorozata. Fel kell építeni egy Turing-eszközt, amely eltávolít egy pár kölcsönös zárójelet, azaz egy sorban elhelyezett elemeket - „()”. Például a kiindulási adat: „) (() (()), a válasz a következő legyen: „) . . . ((”. Megoldás: a q 1 -ben lévő mechanizmus a karakterlánc bal szélső elemét elemzi).

q 1 állapot: ha a "(" szimbólumot találja, akkor váltson jobbra, és menjen a q 2 pozícióba; ha "a 0" van megadva, akkor álljon meg.

q 2 állapot: a „(” zárójelet a párosítás meglétére elemezzük, egyezés esetén a „)”-t kell megkapni. Ha az elem egy pár, akkor tegyen egy kocsit balra, és menjen a q 3-ra.

Állítsa be a q 3-at: először törölje a „(”, majd a „)” karaktert, és lépjen a q 1-re.

szimulátor egy univerzális előadó tanulmányozásához

Ami?

A Turing-gép szimulátor egy univerzális végrehajtó (absztrakt számítógép) képzési modellje, amelyet A. Turing javasolt 1936-ban az algoritmus fogalmának tisztázására. Turing tézise szerint bármely algoritmus felírható programként egy Turing-gépre. Bebizonyosodott, hogy a Turing-gép képességeiben egyenértékű a Post-géppel és a normál Markov-algoritmusokkal.

A Turing-gép egy kocsiból (olvasó- és írófejekből) és egy végtelen, cellákra osztott szalagból áll. A szalag minden cellája tartalmazhat valamilyen A=(a 0 ,a 1 ,…,a N ) ábécé karakterét. Bármely ábécé tartalmaz egy szóköz szimbólumot, amelyet 0-val vagy Λ-vel jelölünk. Parancsok beírásakor a szóközt aláhúzásjel „_” helyettesíti.

A Turing-gép egy automata, amelyet egy asztal vezérel. A táblázat sorai a kiválasztott A ábécé szimbólumainak, az oszlopok pedig a Q=(q 0 ,q 1 ,…,q M ) automata állapotainak felelnek meg. A művelet kezdetén a Turing-gép q 1 állapotban van. A q 0 állapot a végső állapot: ebbe bekerülve az automata befejezi a munkáját.

A táblázat egyes celláiban, amelyek valamilyen a i szimbólumnak és valamilyen q j állapotnak felelnek meg, három részből álló parancs található:

1. egy karakter az A ábécéből;
2. mozgás iránya: > (jobbra),
3. új gépállapot

hírek

1. Falina I.N. A "Turing-gép" téma a számítástechnika iskolai kurzusában (inf.1september.ru).
2. Mayer R.V. Posta és Turing gépek (komp-model.narod.ru).
3. Pilshchikov V.N., Abramov V.G., Vylitok A.A., Hot I.V. Turing-gép és Markov algoritmusok. Problémamegoldás, Moszkva: Moszkvai Állami Egyetem, 2006.
4. Beckman I.N. Számítástechnika. 7. előadás. Algoritmusok (profbeckman.narod.ru)
5. Szolovjov A. Diszkrét matematika képletek nélkül (lib.rus.ec)
6. Ershov S.S. Az algoritmusok elméletének elemei, Cseljabinszk, SUSU Publishing Center, 2009.
7. Varpakhovsky F.L. Az algoritmusok elméletének elemei, M: Enlightenment, 1970.
8. Verescsagin N.K., Shen A. Kiszámolható függvények, M: MTsNMO, 1999.

Mit kell vele csinálni?

A program tetején található egy szerkesztő mező, amelyben szabad formában megadhatjuk a probléma feltételét.

A szalag balra és jobbra mozgatható a tőle balra és jobbra található gombokkal. Egy szalagcellára duplán kattintva (vagy jobb gombbal) módosíthatja annak tartalmát.

A menü használata Szalag tárolhatja a szalag állapotát a belső pufferben, és visszaállíthatja a szalagot a pufferből.

A terepen Ábécé a kiválasztott ábécé karakterei be vannak állítva. A beírt karakterek közé automatikusan szóköz kerül.

A program be van írva az ablak alján található táblázatba. Az első oszlop alfabetikus karaktereket tartalmaz, és automatikusan kitöltődik. Az első sor felsorolja az összes lehetséges állapotot. A táblázat (állapot) oszlopait a táblázat felett található gombokkal adhatja hozzá és távolíthatja el.

A táblázat cellájába történő parancs beírásakor először egy új karaktert kell megadni, majd az átmenet irányát és az állapotszámot. Ha egy karaktert kihagyunk, az alapértelmezés szerint nem változik. Ha az állapotszámot kihagyjuk, az automata állapota alapértelmezés szerint nem változik.

Pont a terepen Megjegyzés a megoldáshoz bármilyen formában megjegyzést írhat. Leggyakrabban elmagyarázzák, mit jelentenek a Turing-gép egyes állapotai.

A program végrehajtható folyamatosan (F9) vagy lépésenként (F8). A most végrehajtandó parancs zöld háttérrel van kiemelve. A végrehajtási sebesség menüben állítható Sebesség.

A Turing-géphez tartozó feladatok fájlokban tárolhatók. A feladat feltétele, az ábécé, a program, a megjegyzések és a szalag kezdeti állapota mentésre kerül. Feladat fájlból való betöltésekor és fájlba mentésekor a szalag állapota automatikusan a pufferbe kerül.

Ha hibát észlel, vagy javaslata, észrevétele, panasza, kérése, nyilatkozata van, írjon a címre.

Technikai követelmények

A program a vonal operációs rendszerei alatt fut ablakok bármely modern számítógépen.

Engedély

A program nem kereskedelmi használatra ingyenes. A program forráskódja nem kerül terjesztésre.

A program jár hozzá amint az”, azaz a szerző nem vállal felelősséget a használatából eredő összes lehetséges következményért, beleértve az erkölcsi és anyagi veszteségeket, a berendezés meghibásodását, a testi és lelki sérüléseket.

A program más weboldalakon történő elhelyezésekor a forrásra mutató hivatkozás szükséges.

1. 1) anyagok közzététele bármilyen formában, beleértve az anyagok közzétételét más webhelyeken;
2. 2) hiányos vagy módosított anyagok forgalmazása;
3. 3) anyagok felvétele a gyűjteményekbe bármilyen adathordozón;
4. 4) kereskedelmi haszon megszerzése anyagok értékesítéséből vagy egyéb felhasználásából.

Az anyagok letöltése azt jelenti, hogy elfogadta a jelen licencszerződés feltételeit.

Letöltés

Az archívum kicsomagolása után a program működőképes, és nem igényel további telepítést.

Turing gép (MT)- absztrakt végrehajtó (absztrakt számítógép). Alan Turing javasolta 1936-ban, hogy formalizálják az algoritmus fogalmát.

A Turing-gép a véges automata kiterjesztése, és Church - Turing tézise szerint, képes utánozni minden előadót(átmeneti szabályok megadásával), amelyek valamilyen módon megvalósítják a lépésről lépésre történő számítási folyamatot, amelyben a számítás minden lépése meglehetősen elemi.

Vagyis bármilyen intuitív algoritmus megvalósítható valamilyen Turing-gép segítségével.

Enciklopédiai YouTube

1 / 5

✪ 09 – Bevezetés az algoritmusokba. Turing gép

✪ Turing gép - Alexander Shen

✪ 20. előadás: Turing-gép

✪ Turing gép. Munka példa

✪ 16 - Kiszámíthatóság. Turing gépek. Motiváció és példák

Feliratok

Turing gép eszköz

A Turing-gép összetétele mindkét irányban korlátlan szalag(lehetséges Turing-gépek, amelyek több végtelen szalaggal rendelkeznek), cellákra osztva, és vezérlő eszköz(más néven olvasó/író fej (GZCH)), képes az egyikben lenni állapotok halmazai. A vezérlőkészülék lehetséges állapotainak száma véges és pontosan adott.

A vezérlőeszköz balra-jobbra mozoghat a szalagon, beolvashat és a cellákba írhat valamilyen véges ábécé karaktereit. Egy különleges üres szimbólum, amely a szalag összes celláját kitölti, kivéve azokat (véges szám), amelyekre a bemeneti adatok rögzítve vannak.

A vezérlőkészülék a szerint működik átmenet szabályai, amelyek az algoritmust képviselik, megvalósítható adott Turing gép. Mindegyik átmeneti szabály arra utasítja a gépet, hogy az aktuális állapottól és az aktuális cellában megfigyelt szimbólumtól függően új szimbólumot írjon ebbe a cellába, lépjen az új állapotba, és mozgassa egy cellát balra vagy jobbra. A Turing-gép egyes állapotait így lehet felcímkézni terminál, és bármelyikre való áttérés a munka végét, az algoritmus leállását jelenti.

Turing-gépet hívnak meghatározó ha a táblázatban szereplő állapot- és szalagszimbólum minden kombinációja legfeljebb egy szabálynak felel meg. Ha van egy "szalag szimbólum - állapot" pár, amelyhez 2 vagy több utasítás tartozik, akkor egy ilyen Turing-gépet ún. nem determinisztikus.

A Turing-gép leírása

Egy adott Turing-gépet az A ábécé betűkészletének elemeinek, a Q állapothalmaznak és a gép működéséhez szükséges szabályoknak a felsorolásával határozhatunk meg. Így néznek ki: q i a j →q i1 a j1 d k három lehetőség: egy cella balra (L), egy cella jobbra (R), marad a helyén (N)). Minden lehetséges konfigurációhoz pontosan egy szabály van (egy nem determinisztikus Turing-gépre több szabály is lehet). Nincsenek szabályok csak a végső állapotra, amikor egyszer a gép leáll. Ezenkívül meg kell adnia a vég- és kezdési állapotot, a kezdeti konfigurációt a szalagon és a gépfej helyét.

Példa a Turing-gépre

Adjunk példát MT-re számok szorzására az unáris számrendszerben. A „q i a j →q i1 a j1 R/L/N” szabály beírását a következőképpen kell érteni: q i - a szabály végrehajtásának állapota, a j - annak a cellának az adatai, amelyben a fej található, q i1 - az állapot, ahová menni akar, a j1 - amit a cellába kell írni, R/L/N - parancs a mozgáshoz.

A gép a következő szabályok szerint működik:

Az állapotok leírása:

Szorozza meg az MT 3 segítségével 2-vel az egységrendszerben. A protokoll jelzi az MT kezdeti és végső állapotát, a kezdeti konfigurációt a szalagon és a gépfej helyét (aláhúzott szimbólum).

Rajt. q 0 állapotban vagyunk, bevittük az adatokat a gépbe: *111x11=*, a gépfej az első * karakteren található.

1. lépés. Megnézzük a szabálytáblázatot, hogy mit fog csinálni a gép, ha q 0 állapotban van és a „*” szimbólum fölött van. Ez a szabály az 5. sor 1. oszlopából származik - q 0 *→q 0 *R. Ez azt jelenti, hogy átlépünk a q 0 állapotba (azaz nem változtatjuk meg), a szimbólum „*” lesz (vagyis nem változik), és haladunk a beírt „*111x11=*” szövegen. jobbra egy pozícióval (R), akkor az 1. karakterhez 1. A q 0 1 állapotot (1. oszlop 1. sor) viszont a q 0 1→q 0 1R szabály dolgozza fel. Vagyis megint csak egy átmenet van jobbra 1 pozícióval. Ez addig történik, amíg az "x" szimbólumon nem állunk. És így tovább: vesszük az állapotot (index q-nál), vesszük a szimbólumot, amelyen állunk (aláhúzott szimbólum), összekapcsoljuk őket, és megnézzük a kapott kombináció feldolgozását a szabálytáblázat szerint.

Egyszerűen fogalmazva a szorzási algoritmus a következő: megjelöljük a 2. tényező 1. mértékegységét „a” betűvel helyettesítve, és a teljes 1. tényezőt az egyenlőségjelen túlra visszük. Az átvitel úgy történik, hogy az 1. szorzó egységeit felváltva "a"-ra cseréljük, és ugyanannyi egységet adunk a sor végére (a jobb szélső "*"-tól balra). Ezután az összes "a"-t az "x" szorzójelig visszacseréljük egységekre. És a ciklus megismétlődik. Valójában az A szorozva B-vel A + A + A B-szeresen ábrázolható. Most a 2. szorzó 2. egységét jelöljük "a" betűvel, és ismét átvisszük az egységeket. Ha nincs mértékegység a „=” jel előtt, akkor a szorzás befejeződik.

Turing teljesség

Azt mondhatjuk, hogy a Turing-gép a legegyszerűbb lineáris memóriaszámítógép, amely formális szabályok szerint a bemeneti adatokat a sorozat segítségével alakítja át. elemi cselekvések.

A cselekvések elemi jellege, hogy a művelet csak egy kis adatot változtat meg a memóriában (Turing-gép esetén csak egy cellát), és a lehetséges műveletek száma véges. A Turing-gép egyszerűsége ellenére minden kiszámítható rajta, ami bármely más gépen kiszámítható, amely elemi műveletek sorozatával végez számításokat. Ezt a tulajdonságot ún teljesség.

Az egyik természetes módszer annak bizonyítására, hogy az egyik gépen megvalósítható számítási algoritmusok egy másik gépen is megvalósíthatók, az első gép szimulálása a másodikon.

Az utánzás a következő. Az első gép programjának (működési szabályainak) leírása a második gép bemenetére kerül D (\displaystyle D)és bemenet X (\displaystyle X), amelyeknek az első gép bemenetére kellett volna érkezniük. Egy ilyen programot (a második gép működési szabályait) le kell írni, hogy a számítások eredményeként a kimenet ugyanaz legyen, mint az első gép, ha adatot kapna bemenetként. X (\displaystyle X).

Mint elhangzott, egy Turing-gépen lehetőség van az összes többi végrehajtó szimulálására (az átmeneti szabályok beállításával), amelyek valamilyen módon megvalósítják a lépésről lépésre történő számítás folyamatát, amelyben a számítás minden lépése meglehetősen elemi.

A Turing-gépen szimulálhat egy Post-gépet, normál Markov-algoritmusokat és bármilyen olyan programot a közönséges számítógépekhez, amely a bemeneti adatokat valamilyen algoritmus szerint konvertálja kimeneti adatokká. Különböző absztrakt végrehajtókon viszont lehetséges a Turing-gép utánzása. Olyan művészeket hívnak, akiknek ez lehetséges Turing kész(Turing kész).

Vannak olyan programok a hagyományos számítógépekhez, amelyek egy Turing-gép működését utánozzák. De meg kell jegyezni, hogy ez a szimuláció nem teljes, mivel a Turing-gépnek van egy absztrakt végtelen szalagja. Egy végtelen adatszalag nem szimulálható teljesen véges memóriájú számítógépen (a számítógép teljes memóriája - RAM, merevlemezek, különféle külső adathordozók, processzorregiszterek és gyorsítótár stb. - lehet nagyon nagy, de ennek ellenére mindig véges ).

Turing-gép változatok

A Turing-gép modellje lehetővé teszi a bővítést. Tekinthetünk tetszőleges számú szalaggal rendelkező Turing-gépet és különböző korlátokkal rendelkező többdimenziós szalagokat. Azonban ezek a gépek mindegyike Turing-komplett, és egy szokásos Turing-gép modellezi őket.

Félvégtelen szalagon futó Turing-gép

Példaként egy ilyen redukcióra tekintsük a következő tételt: Bármely Turing-géphez létezik egy ekvivalens Turing-gép, amely félvégtelen szalagon fut (vagyis olyan szalagon, amelyik egy irányban végtelen).

Tekintsük Yu. G. Karpov bizonyítását az Automata elmélete című könyvében. Ennek a tételnek a bizonyítása konstruktív, azaz adunk egy algoritmust, amellyel bármely Turing-gépre megszerkeszthető egy deklarált tulajdonságú ekvivalens Turing-gép. Először tetszőlegesen megszámozzuk az MT munkaszalag celláit, azaz meghatározzuk az információ új helyét a szalagon:

Ezután újraszámozzuk a cellákat, és feltételezzük, hogy a "*" szimbólum nem szerepel az MT szótárban:

Végül megváltoztatjuk a Turing-gépet úgy, hogy megkétszerezzük az állapotok számát, és megváltoztatjuk az író-olvasó fej eltolását úgy, hogy az egyik állapotcsoportban a gép működése egyenértékű legyen a sötétített zónában, a másik állapotcsoportban pedig a gép működésével. a gép úgy működik, ahogy az eredeti gép működik.árnyékolatlan területen. Ha az MT működése közben a ’*’ szimbólumot találjuk, akkor az író-olvasó fej elérte a zónahatárt:

Egy új Turing-gép kezdeti állapota az egyik vagy másik zónában van beállítva, attól függően, hogy az eredeti szalagon hol helyezkedett el az író-olvasó fej az eredeti konfigurációban. Nyilvánvaló, hogy a "*" korlátozó jelölőktől balra a szalagot nem használják az egyenértékű Turing-gépben.

Kétdimenziós Turing-gépek

• Ant Langton

Lásd még

• JFLAP cross-platform automata szimulátor, Turing gépek, nyelvtan, automata gráf rajz