Algel definíciók

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.