Matematika | Felsőoktatás » Definíciók számításelméletből

Definíciók Számításelméletből Ábécé: Véges, nem üres szimbólumhalmaz. Általában T-vel jelöljük Univerzális ábécé: Szimbólumok egy rögzített, megszámlálhatóan végtelen számosságú halmaza. Jele: ∑ Minden ábécéről feltesszük, hogy ennek véges részhalmaza Betű: Valamely ábécé egy eleme. Szó: Valamely ábécé elemeiből képzett véges sorozat. Ha lényeges az ábécé, akkor T-feletti szóról beszélünk (ahol T egy ábécé). A T ábécé feletti szavak összességét T* jelöli. Nyelv: Valamely ábécé szavainak egy halmaza. Ha lényeges az ábécé, akkor T-feletti nyelvről beszélünk (ahol T egy ábécé). A T ábécé feletti nyelvek összességét 2 T* jelöli. Absztrakt feladat: Legyenek I, O tetszőleges absztrakt halmazok. Absztrakt feladatnak nevezzük az F  I  O alakú relációkat. Egy F feladat esetében D F  I a feladat értelmezési tartománya, R F  O a feladat értékkészlete, míg valamely i  D F esetén

F(i) ( R F ) az i-hez rendelt O-beli elemek összessége. Jól definiált absztrakt feladat: Olyan F absztrakt feladat, mely esetében I, O minden elemének és magának F-nek is létezik véges leírása. Véges leírás: Általános esetben az univerzális ábécé elemeiből képzett véges sorozat. Megmutatható, hogy a leírások céljára elegendő egy T legalább 2 elemű ábécé feletti szavakat használni. (A ∑ elemeiből képzett véges sorozatok halmaza kódolható a T feletti szavakkal) Konkrét feladat: Legyen T tetszőleges ábécé. Konkrét feladatnak nevezzük az F  T*  T alakú relációkat. Jól definiált konkrét feladat: Olyan F konkrét feladat, ahol F-nek létezik véges leírása. Programok megállási problémája: Adott programozási nyelv esetében egy olyan „univerzális” program készítése, mely egy tetszőleges program és annak tetszőleges bemenete esetén (véges idő alatt) eldönti, hogy a program az adott bemenetre megáll-e.

Utazó ügynök probléma: Egy ügynök az érdekkörében lévő n darab várost úgy szeretné körbejárni, hogy közben mindegyik várost csak egyszer érintse. Az absztrakcióval kapott feladat: egy adott gráfban olyan kör keresése, mely minden pontot pontosan egyszer érint (Hamilton-kör). (A valós és absztrakt világ megfeleltetése: a városoknak a gráf pontjai, az összekötő utaknak a gráf élei felelnek meg.) Nyelvtan: A (formális) nyelvtanok olyan generátorok, melyekkel valamely T ábécé feletti szavakat lehet előállítani. Egy G nyelvtan a következő négyes: G= <T, N, P, S>, ahol T: a terminális jelek ábécéje, N: a nyelvtani jelek ábécéje, T∩N = , P: szabályok véges halmaza, S: kezdőjel, N egy eleme. A szabályok p q alakban írt párok, ahol p  (TN)* N (TN), q  (TN). p-t az adott szabály baloldalának, q-t a jobboldalának hívjuk. A nyelvtan szabályai segítségével definiáljuk G-ben a levezetéseket. Van egy

lépéses (közvetlen) levezetés (jele G ), és több lépéses (közvetett) levezetés (jele * G ). Mindkettő bináris reláció (TN)* -on, melyek jelentése a következő: α G β  ha léteznek olyan α 1 , α 2 (T N)* szavak, valamint olyan p q szabály P-ben, amelyekre α = α 1 pα 2 , és β = α 1 qα 2 . α G β-t úgy olvassuk ki, hogy α-ból közvetlenül levezethető β. α * G β  ha létezik olyan k ≥ 0 egész és léteznek az α 0 , α 1 ,, α k szavak úgy, hogy a követező közvetlen levezetési lánc (levezetés) minden lépése igaz: α = α 0 G α 1 G α 2 G . G α k = β α * G β-t úgy olvassuk ki, hogy α-ból közvetetten levezethető (vagy csak egyszerűen levezethető) β. (A k számot, mely a több lépéses levezetésben az alkalmazott közvetlen levezetések száma, a levezetés hosszának nevezzük.) A G = T, N, P, S nyelvtan által generált nyelv, L(G) a következő: L(G):= {u: u összessége.) T* és S G u}. (A kezdőjelből

levezethető terminális szavak Absztrakt algoritmus. (Intuitív megfogalmazás) Olyan véges leírások, melyeket bizonyos képzési szabályok – a szintaxis – szerint állítunk elő, s melyek jelentésük alapján – szemantika - meghatároznak valamely leképezést (transzformációt). A szintaxist konstruktív módon adjuk meg, elemi algoritmusok (utasítások) és felépítő operátorok segítségével. A szemantika megadás a szintaxis alapján történik és annak a transzformációnak a leírását jelenti, melyet az algoritmus megvalósít. Ezt a transzformációt az algoritmus hatásfüggvényének nevezzük. A hatásfüggvény megadására többféle módszer létezik, mi az úgynevezett operációs szemantika megadást használjuk erre a célra Absztrakt algoritmus hatásfüggvénye: Az A absztrakt algoritmus hatásfüggvénye valamely fA : I O alakú függvény (I, O absztrakt halmazok, a lehetséges bemenetek,illetve kimenetek halmazai). Értelmezési

tartományát D fA -val, míg értékkészletét R f A -val jelöljük Az i inputról i D fA esetén azt mondjuk, A az i hatására az fA (i) értékkel terminál, míg i D fA esetén A nem terminál. Algoritmusok hatásfüggvényének definíciójára szolgáló módszerek:  Denotációs vagy funkcionális szemantika megadás. Az elemi utasításoknak függvények felelnek meg, míg a konstrukciós szabályoknak bizonyos függvénykonstrukciós műveletek. A hatásfüggvény – az elemi utasítások és a konstrukciós szabályok jelentését használva – a szintaxis alapján konstruált összetett függvény lesz. (Például a rekurziót megengedő algoritmusok jelentését így szokás megadni.)  Operációs szemantika megadás. Az algoritmus végrehajtását lépésekre bontottnak képzeljük. Minden lépés az algoritmust jellemző pillanatnyi adatsor, konfiguráció megváltoztatását idézi elő. A jelentés definíciója ezeknek a konfiguráció átmeneteknek

(számítás) a leírását jelenti. Az algoritmus egy kezdőkonfigurációból indul (a bemenő adatokkal) és konfigurációk során halad át. Ha nincs további végrehajtható lépés, akkor a konfiguráció termináló konfiguráció. A számítás eredménye – mely a termináló konfigurációból olvasható ki – szolgáltatja a hatásfüggvény értékét. Megoldás: Azt mondjuk, hogy az F  I ×O absztrakt feladatot az A absztrakt algoritmus megoldja, ha 1. D F  D f A (a feladat értelmezési tartománya része az algoritmus értelmezési tartományának), 2. Minden i D f A esetén f A (i) F(i). Algoritmikusan megoldható feladat. Az F absztrakt feladat algoritmikusan megoldható, ha létezik olyan A absztrakt algoritmus, mely megoldja. Konkrét algoritmus: Olyan absztrakt algoritmus, melynek hatásfüggvénye valamely T ábécé feletti f A : T* T leképezés. (Megjegyzés: Mivel az előadás döntő részében ilyen konkrét algoritmusokkal foglalkoztunk,

ezért a konkrét algoritmusokra egyszerűen csak algoritmusokként fogunk hivatkozni a definíciókban.) Parciálisan eldöntő algoritmus: Olyan A algoritmus, melynek hatásfüggvénye csak két előre rögzített értéket (u 0 és u 1 , a hamis és igaz logikai értékek reprezentációi) vehet fel. Azt mondjuk, hogy A felismeri, más szóval elfogadja u-t, ha f A (u)=igaz. Amennyiben f A (u)= hamis, akkor A nem ismeri fel, más szóval elutasítja u-t. A felismert szavak összességét az algoritmus által felismert, más szóval elfogadott nyelvnek nevezzük és L(A) -val jelöljük. Totálisan eldöntő algoritmus: Olyan parciálisan eldöntő algoritmus, melynek hatásfüggvénye mindenütt értelmezve van. Más szavakkal ez azt jelenti, hogy az algoritmus minden u T* inputra terminál. Követelmények az algoritmusokkal szemben: Legyen T egy rögzített, legalább kettő elemű ábécé. Megjegyzés: Ha csak ezen T feletti szavakon operáló algoritmusokkal foglalkozunk a

tételek kimondása és bizonyítása során, az nem megy az általánosság rovására (más ábécé feletti feladatok algoritmikusan átkódolhatók T feletti feladattá). Elvárásaink az algoritmusok felé:    lépésenkénti determinisztikus végrehajtás, T* elemeivel történő véges, prefixmentes kódolhatóság, Olyan univerzális algoritmus létezése, mely egy v T* szóról el tudja dönteni, hogy annak eleje algoritmus kódja-e, s ha igen, akkor szimulálni tudja a kódolt algoritmusnak a – v-ből az algoritmus kódjának elhagyásával kapott maradék szóval – történő működését. Az algoritmusok prefixmentes kódolása azt jelenti, hogy nem létezik két olyan algoritmus, melyek esetében az egyik kódja kezdőszelete a másik kódjának. Kiszámítási feladat: F  T* × T alakú konkrét feladat. Algoritmikusan kiszámítható feladat: Olyan F kiszámítási feladat, melyhez van olyan A algoritmus, mely megoldja. Eldöntési feladat

(probléma): L  T* alakú nyelv. (Minden eldöntési feladat tekinthető kiszámítási feladatnak, ha L-et azonosítjuk a karakterisztikus függvényével, továbbá T* két kitüntetett elemét u 0 -t és u 1 -et azonosítjuk a 0 és 1, illetve a hamis és igaz értékekkel.) Parciális eldöntés: Az L  T* eldöntési feladatot (problémát, nyelvet) az A parciálisan eldöntő algoritmus parciálisan eldönti, ha L(A) = L . (Megjegyzés: u L esetén tehát A igaz válasszal terminál, míg u L esetén az algoritmus vagy hamis értékkel terminál vagy nem is terminál). Totális eldöntés: Az L  T* eldöntési feladatot (problémát, nyelvet) az A totálisan eldöntő algoritmus totálisan eldönti, ha L(A) = L . (Megjegyzés: u L esetén tehát A igaz válasszal terminál, míg u L esetén hamissal. A totális eldöntés olyan parciális eldöntés, ahol az eldöntő algoritmus mindig terminál.) Parciálisan rekurzív nyelv: Olyan L  T* nyelv, melyhez van őt

parciálisan eldöntő algoritmus. Összességüket L ParRek jelöli Rekurzív nyelv: Olyan L  T* nyelv, melyhez van őt totálisan eldöntő algoritmus. Összességüket L Rek jelöli. (Megjegyzés: Világos, hogy minden rekurzív nyelv parciálisan is rekurzív, tehát L Rek  L ParRek .) L átló : Az algoritmusoknak és T* elemeinek létezik algoritmussal is megvalósítható felsorolása. (az algoritmusokat - pontosabban szólva a T feletti leírásaikat – úgy soroljuk fel, hogy felsoroljuk T* elemeit, majd az univerzális algoritmussal eldöntjük az éppen aktuális T feletti szóról, hogy az algoritmus kódja-e. Ha igen, az adott szót a felsorolás következő tagjának választjuk, egyébként elhagyjuk). Jelölje tetszőleges i pozitív egészre A i az i algoritmust, míg u i a T* felsorolásánál az i. szót Legyen L átló a következő nyelv: L átló = {u i , u i T* u i L(A i ) }. Az L átló komplementerét co(L átló ) –val jelöljük Turing-gép: Az

intuitív algoritmus fogalom egy egzakt formája. Egy M Turing-gép alatt a következő hatost értjük: M = <Q, T, δ, q 0 , B, F>, ahol Q: véges halmaz, az állapotok halmaza, T: véges halmaz, a bemenő (input) ábécé, δ: Q × T Q × T × {L,R,S} parciális függvény, az átmenetfüggvény, q 0: a kezdőállapot, q 0 Q, B: az üres cella jele, F: a végállapotok halmaza, F  Q. (A Turing-gép egy olyan egyszerű számítási modell, mely egy véges kapacitású központi egységből és egy mindkét irányban potenciálisan végtelen, de minden pillanatban véges, cellákra osztott szalagból áll. A gép diszkrét időskálában, az aktuális input jel és állapot függvényében determinisztikusan működik, konfigurációról konfigurációra lépve. Kezdetben a szalagon az input szó van (első betűjén az olvasó fejjel), a központi egység kezdőállapotban van. A gép akkor szolgáltat eredményt, ha megáll Ilyenkor a szalag tartalma, illetve a kialakult

állapot határozza meg az eredményt.) Turing-gép konfigurációja: Konfigurációnak a következő alakú hármasokat nevezzük: [α 1 , q, α 2 ]. Itt q  Q az aktuális állapot, α 1 (T U{B})* az olvasó fejtől balra lévő szalagtartalom, α 2  (T U{B})* nem üres szó az olvasófejtől jobbra lévő szalagtartalom, a fej α 2 első elemére mutat. Rákövetkezési relációk a Turing-gép konfigurációin: A gép átmeneti függvénye segítségével definiáljuk M-ben a konfiguráció átmeneteket. Van egy lépéses (közvetlen) konfiguráció átmenet (jele M ), és több lépéses (közvetett) konfiguráció átmenet (jele * M ). Mindkettő bináris reláció a konfigurációkon, melyek jelentése a következő: [α 1 , q, α 2 ] M [β 1 , q’, β 2 ]  x,y,z  T U{B} γ, σ  (T U{B})* (α 1 = γ z α 1 = ε ) α 2 = xσ (δ(q, x)= (q’, y, L) (α 1 ≠ ε β 1 = γ β 2 = zyσ α 1 =ε β 1 = ε β 2 = Byσ) δ(q, x)= (q’, y, R) β1= α1y β 2 = σ

δ(q, x)= (q’, y, S) β 1 = α 1 β 2 = y σ ). k M k’ úgy olvassuk ki, hogy k-nak közvetlen rákövetkezője k’. k * M k’  n  0  k 0 , k 1 , ,k n (k 0 = k k n = k’ j=1,2,,n (k j-1 konfiguráció átmenet hossza. k M k j ) ). Itt n a * M k’ úgy olvassuk ki, hogy k-nak (közvetett) rákövetkezője k’. u  T* szót tartalmazó kezdőkonfiguráció: konfiguráció, ahol α 1 = ε, q=q 0 , α 2 = u. Jelölése k 0 (u). Olyan [α 1 , q, α2] Termináló konfiguráció: olyan konfiguráció, melynek nincs rákövetkezője. Elfogadó konfiguráció, olyan termináló konfiguráció, melyben az állapot  F. Elutasító konfiguráció, olyan termináló konfiguráció, melyben az állapot F. Turing-gép hatásfüggvénye: Az M Turing-gép hatásfüggvényét f M –el jelöljük. f M (u) = v  olyan [α 1 , q, α 2 ] termináló konfiguráció, melyre (k 0 (u) *M [α 1 , q, α 2 ] és v = h(α 1 α 2 )), ahol h olyan leképezés, mely egy tetszőleges

(T U{B})* -beli sorozatból kihagyja a B-ket. Világos, hogy f M T* -ból T -ba ható parciális leképezés. Turing-gép által felismert, elfogadott nyelv: Az M Turing-gép által felismert, elfogadott nyelvet L(M) –el jelöljük. Jelentése a következő: L(M) = { u; u  T* és  k elfogadó konfiguráció, melyre k 0 (u) M k }. Világos, hogy L(M) T feletti nyelv. Számítás hossza az M Turing-gépen: Jelölje T M (u) az u bemenő szót tartalmazó kezdő konfigurációból induló maximális konfiguráció-átmenet hosszát (végtelent értve alatta, ha a számítás nem terminál). T M (u) – t az u hatására történő számítás hosszának nevezzük Az M Turing-gép időbonyolultsága: Legyen n  0 tetszőleges egész. Jelölje T M (n) az n hosszúságú bemenetekre történő számítások hosszainak maximumát (végtelen, ha valamelyik n hosszú szóra a gép nem áll meg). A T M (n) függvényt az M időbonyolultságának hívjuk Értékes cella: Nevezzük az

M Turing-gép valamely működése során egy cellát értékesnek, ha abban vagy a bemenet egy jele van, vagy a számítás során valamikor a gép jelet olvasott belőle. Számítás tárigénye az M Turing-gépen: Jelölje S M (u) az u bemenő szót tartalmazó kezdő konfigurációból induló maximális konfiguráció-átmenet értékes celláinak számát (esetleg végtelen is lehet, ha a számítás nem terminál). S M (u) –t az u hatására történő számítás tárigényének nevezzük. Az M Turing-gép tárbonyolultsága: Legyen n  0 tetszőleges egész. Jelölje S M (n) az n hosszúságú bemenetekre történő számítások tárigényeinek maximumát (végtelen, ha valamelyik n hosszú szóra a tárigény végtelen). S M (n) -et az M tárbonyolultságának hívjuk t(n) időkorlátos, illetve s(n) tárkorlátos Turing-gép: Legyenek t és s: N  N alakú, mindenütt értelmezett függvények, melyekre t(n), s(n)  n teljesül. Azt mondjuk, hogy az M Turing-gép

t(n) időkorlátos, illetve s(n) tárkorlátos, ha T M (n) = O(t(n)), illetve S M (n) = O(s(n)). (Világos, hogy egy t(n) időkorlátos Turing-gép minden bemenetére megáll.) t(n) időkorlátos és s(n) tárkorlátos nyelvek családja: A t(n) időkorlátos Time(t(n)) és s(n) tárkorlátos Space(t(n)) nyelvek családját a következő módon definiáljuk: Time(t(n)) = {L, LT* és  M t(n) időkorlátos Turing-gép, melyre L(M)=L} Space(t(n)) = {L, LT* és  M s(n) tárkorlátos Turing-gép, melyre L(M)=L}. (Megjegyzés: Hasonlóan definiálhatók az f: T*  T függvényekre az FTime(t(n)) és FSpace(t(n)) függvényosztályok.) Polinomiális futási idő mellett felismerhető nyelvek: Azon T feletti nyelvek családja, melyekhez van az input szó hossza függvényében polinom időkorlátos, totálisan felismerő Turing-gép. Jele: P P elemei a felismerési idő szempontjából hatékonyan – a gyakorlatban használható módon – felismerhető nyelvek. Formálisan P=

 i1 Time(ni). Köbös tárigény mellett felismerhető nyelvek: Azon T feletti nyelvek családja, melyekhez van az input szó hossza függvényében harmadfokú polinom időkorlátos, totálisan felismerő Turing-gép. Jele: Space(n3) Space(n3) elemei a tárigény szempontjából hatékonyan – a gyakorlatban használható módon felismerhető nyelvek. Nemdeterminisztikus Turing-gép: A determinisztikus Turing-gép olyan általánosítása, ahol a működés nem determinisztikusan zajlik. Nem valós számítási modell, de elméleti vizsgálatokban jól hasznosítható. Egy M nemdeterminisztikus Turing-gép alatt a következő hatost értjük: M = <Q, T, δ, q 0 , B, F>, ahol Q: véges halmaz, az állapotok halmaza, T: véges halmaz, a bemenő (input) ábécé, δ: Q × T Q × T × {L,R,S} nemdeterminisztikus függvény (reláció), az átmenetfüggvény, q 0: a kezdőállapot, q 0 Q, B: az üres cella jele, F: a végállapotok halmaza, F  Q. A

nemdeterminisztikus Turing-gép esetében a fogalmak döntő része ugyanúgy adható meg, mint a determinisztikusok esetében. Csak az eltérően definiálandó fogalmakat adjuk meg Közvetlen rákövetkezés az M nemdeterminisztikus Turing-gépen: Az egy lépéses (közvetlen) konfiguráció átmenet (jele M ) bináris reláció a konfigurációkon, melyek jelentése a következő: [α 1 , q, α 2 ] M [β 1 , q’, β 2 ]  x,y,z  T U{B} γ, σ  (T U{B})* (α 1 = γ z α 1 = ε ) α 2 = xσ ( (q’, y, L)  δ(q, x) (α 1 ≠ ε β 1 = γ β 2 = zyσ α 1 =ε β 1 = ε β 2 = Byσ) (q’, y, R)  δ(q, x) (q’, y, S)  δ(q, x ) k M β1= α1y β 2 = σ β 1 = α 1 β 2 = y σ ). k’ úgy olvassuk ki, hogy k-nak közvetlen rákövetkezője k’. Az M nemdeterminisztikus Turing-gépen felismert, elfogadott nyelv: L(M): = {u, u T* és  k elfogadó konfiguráció, melyre k 0 (u) M k}. Ez a nemdeterminisztikusság szemantikájának úgynevezett gyenge változata.

Számítás hossza az M nemdeterminisztikus Turing-gépen: Jelölje T M (u) az u bemenő szót tartalmazó kezdő konfigurációból induló lehetséges konfiguráció-átmenetek hosszának maximumát (végtelent értve alatta, ha van köztük akármilyen hosszú számítás, illetve nem termináló számítás). T M (u) – t az u hatására történő számítás hosszának nevezzük Az M nemdeterminisztikus Turing-gép időbonyolultsága: Legyen n  0 tetszőleges egész. Jelölje T M (n) az n hosszúságú bemenetekre történő számítások hosszainak maximumát (végtelen, ha valamelyik n hosszú szóra T M (u) végtelen). A T M (n) függvényt az M időbonyolultságának hívjuk. Értékes cella: Nevezzük az M Turing-gép valamely működése során egy cellát értékesnek, ha abban vagy a bemenet egy jele van, vagy a számítás során valamikor a gép jelet olvasott belőle. Számítás tárigénye az M nemdeterminisztikus Turing-gépen: Jelölje S M (u) az u bemenő

szót tartalmazó kezdő konfigurációból induló lehetséges konfiguráció-átmenetek értékes celláinak számát (végtelent értve alatta, ha van köztük akármilyen sok, illetve nem termináló számítás esetén végtelen sok értékes cellával bíró számítás). S M (u) –t az u hatására történő számítás tárigényének nevezzük. Az M nemdeterminisztikus Turing-gép tárbonyolultsága: Legyen n  0 tetszőleges egész. Jelölje S M (n) az n hosszúságú bemenetekre történő számítások tárigényeinek maximumát (végtelen, ha valamelyik n hosszú szóra a tárigény végtelen). S M (n) -et az M tárbonyolultságának hívjuk. t(n) időkorlátos, illetve s(n) tárkorlátos nemdeterminisztikus Turing-gép: Legyenek t és s: N  N alakú, mindenütt értelmezett függvények, melyekre t(n), s(n)  n teljesül. Azt mondjuk, hogy az M nemdeterminisztikus Turing-gép t(n) időkorlátos, illetve s(n) tárkorlátos, ha T M (n) = O(t(n)), illetve S M (n) =

O(s(n)). (Világos, hogy egy t(n) időkorlátos Turing-gép minden bemenetére megáll.) Nemdeterminisztikusan t(n) időkorlátos és s(n) tárkorlátos nyelvek családja: A nemdeterminisztikusan t(n) időkorlátos NTime(t(n)), illetve s(n) tárkorlátos NSpace(t(n)) nyelvek családját a következő módon definiáljuk: NTime(t(n)) = {L, LT* és  M t(n) időkorlátos Turing-gép, melyre L(M)=L} NSpace(t(n)) = {L, LT* és  M s(n) tárkorlátos Turing-gép, melyre L(M)=L}. (Megjegyzés: Hasonlóan definiálhatók az f: T*  T függvényekre az NFTime(t(n)) és NFSpace(t(n)) függvényosztályok.) Nemdeterminisztikus Turing-gépen polinomiális futási idő mellett felismerhető nyelvek: Azon T feletti nyelvek családja, melyekhez van az input szó hossza függvényében polinom időkorlátos, totálisan felismerő nemdeterminisztikus Turing-gép. Jele: NP Tételek a számításelmélet témaköréből Tétel: A formális nyelvtanokkal leírható nyelvek

összessége megegyezik a logikai állításokkal leírható nyelvek összességével. (Nem bizonyítottuk) Tétel. Létezik olyan F  T* ×T kiszámítási feladat, mely algoritmikusan nem kiszámítható. (Számossági meggondolással bizonyítottuk.) Tétel. Létezik olyan L  T* meggondolással bizonyítottuk.) probléma, mely nem parciálisan eldönthető. (Számossági Tétel: Nincs olyan algoritmus, mely parciálisan felismerné L átló -t (azaz L átló (Cantor–féle átlós módszerrel bizonyítottuk), L ParRek) . Tétel. co(L átló ) felismerhető parciálisan eldöntő algoritmussal (azaz co(L átló ) (Megadtunk egy parciálisan felismerő algoritmust co(L átló ) –hoz.) L ParRek ). Tétel. Egy nyelv pontosan akkor ismerhető fel totálisan, ha mind ő, mind a komplementere parciálisan felismerhető. (A parciálisan rekurzív nyelvhez adtunk totálisan eldöntő algoritmust). Következmény. L Rek  L ParRek Tétel. Nem létezik olyan algoritmus, mely

egy tetszőleges algoritmus és annak tetszőleges inputja esetén (totálisan) eldönti, hogy az adott algoritmus az adott inputra megáll-e. (A megállási probléma nem (totálisan) eldönthető.) (Indirekt bizonyítottuk, L átló L ParRek -kel kerültünk ellentmondásba.) Tétel. A Turing-gépekre teljesülnek az algoritmusokra tett elvárásaink (A lépésenkénti determinisztikus működés a Turing-gép definíciója miatt teljesül, a prefix mentes kódolást megadtuk, az univerzális Turing-gép létét nem bizonyítottuk). Következmény. Mindazok a tételek, melyeket az intuitív algoritmusokra bizonyítottunk, igazak lesznek a Turing-gépekkel modellezett algoritmusokra is. Tétel: A Turing-géppel parciálisan eldönthető nyelvek osztálya megegyezik a nyelvtanok segítségével generálható nyelvek osztályával. (A szükséges kétirányú szimulációt vázoltuk) Church-tézis. Az feladatok algoritmikus megoldhatósága szempontjából minden algoritmusmodell

egyenértékű a Turing-géppel. (Nem tétel, de az eddig feltalált algoritmusmodellekre bizonyíthatóan igaz.) Tétel: Egy NP-beli nyelvhez mindig lehet készíteni olyan determinisztikus Turing-gépet, mely az input hosszának exponenciális függvényében fel tudja ismerni az adott nyelvet. (Teljes keresés egy általában exponenciális méretű halmazon.) Sejtés: P  NP. (A tartalmazás világos, csak a valódi tartalmazás a kérdéses)