Algel definíciók

Ez az oldal a korábbi SCH wiki-ről lett áthozva. Az eredeti változata itt érhető el.

Ha úgy érzed, hogy bármilyen formázási vagy tartalmi probléma van vele, akkor kérlek javíts rajta egy rövid szerkesztéssel.

Ha nem tudod, hogyan indulj el, olvasd el a migrálási útmutatót

Rendezés, keresés

• Keresés és rendezés összefoglaló
• Keresőfa összefoglaló

Bonyolultságelmélet

TG helyzete

(Nem hivatalos def, de könnyebb vele fogalmazni): a TG aktuális állapota, fejeinek állása, a fejek alatt lévő karakterek.

TG megáll

Az adott helyzetre nincs szabály, így nem tud továbblépni.

TG elfogad

Az adott bemenetre a gép megáll, mégpedig elfogadó állapotban. Nem determinisztikus esetben: van legalább egy végrehajtási út, amin megáll elfogadó állapotban.

TG nem fogad el

Az adott bemenetre a gép nem áll meg, vagy nem elfogadó állapotban áll meg. Nem determinsztikus: nincsen olyan végrehajtási út, amin elfogad.

Nem determinisztikus turing gép

Olyan TG, melynek van többértékű szabálya. (képletesen: van olyan helyzet, melyből több másikba is léphet)

co előtag

coX az X-be tartozó nyelvek koplementereiból képzett halmaz.

RE : rekurzíve felsorolható nyelvek

Azok a nyelvek, melyhez létezik TG, ami pontosan a nyelv szavait fogadja el. (A nyelven kívüli szavakra nem kötelező megállnia.)

R : rekurzív nyelvek

Azok a nyelvek, melyhez létezik TG, ami pontosan a nyelv szavait fogadja el, és mindig megáll. (R részhalmaza RE-nek)

R = coR

Egy R-beli nyelvet felisemrő automata elfogadás és elutasítás esetén is kötelezően megáll. Így a nyelv komplementerét is felismerhetjük ezzel a géppel, ha felcseréljük az elfogadó és elutasító állpotokat, és ez is mindig meg fog állni.

R = (RE ∩ coRE)

Vegyünk egy tetszőleges nyelvet a halmazból!

• A nyelv eleme RE, így TG₁ a nyelv szavaira mindig megáll elfogadó állapotban.
• A nyelv eleme coRE, így TG₂ a nyelven kívüli szavakra mindig megáll elfogadó állapotban.

Írjunk egy olyan TG-t, ami TG1-et és TG2-t futtatja párhuzamosan (egy lépést az egyik, egyet a másik). TG₁ és TG₂ valamelyike biztosan megáll. Ha TG₁ elfogad, akkor elfogadunk. Ha TG₂ fogad el, elutasítunk.

Időkorlátos TG

Ha n hosszú inputon legfeljebb t(n) lépést tesz meg.

TIME(t(n)) nyelosztály

Azok a nyelvek, melyekhez létezik c*t(n) időkorlátos TG. c nyelvenként más. (TIME(t(n)) eleme R)

P nyelvosztály

Polinom időben felismerhetőek. Azok a nyelvek, melyekhez létezik c*t(n) időkorlátos TG, ahol t(n) egy polinom.

NP nyelvosztály

Nem determinisztikus TG-pel polinom időben felismerhetőek. Azok a nyelvek, melyekhez létezik c*t(n) időkorlátos nem determinisztikus TG, ahol t(n) egy polinom.

-- SzaMa - 2005.05.22.

Univerzális Turing-gép

Képes szimulálni más gépeket. w#s bemenetre U(w#s) = elutasít, ha nem létezik w kódú TG; egyébként U(w#s) = M_w(s).

Univerzális nyelv

Az univerzális Turing-gép által elfogadott nyelv, azaz azon w#s szavak halmaza, melyre létezik w kódú Turing-gép, továbbá ez a gép s bemenetre elfogad. (L_u ∈ RE, hiszen az Univerzális Turing-gép elfogadja; de L_u ∉ R)

Diagonális nyelv

Azon w szavak halmaza, melyre létezik w kódú Turing-gép, és ez a gép nem fogadja el a w szót. (L_d ∉ RE)

Megállási nyelv

Azon w#s szavak halmaza, melyre létezik w kódú Turing-gép, és ez a gép megáll az s bemenetre. (L_h ∈ RE, de L_h ∉ R)

függvény ((parciálisan) rekurzív)

Ez egy olyan TG ami tartalmazási kérdés helyett függvényt számol ki (egy output szalagra), és nem biztos hogy megáll.

-- P.G. - 2005.06.11.