„Algel definíciók” változatai közötti eltérés

A VIK Wikiből
Ugrás a navigációhoz Ugrás a kereséshez
(Új oldal, tartalma: „{{GlobalTemplate|Infoalap|AlgElDefiniciok}} ==Rendezés, keresés== * Keresés és rendezés összefoglaló * [[AlgElKeresofaOss…”)
 
 
1. sor: 1. sor:
{{GlobalTemplate|Infoalap|AlgElDefiniciok}}
 
 
 
 
==Rendezés, keresés==
 
==Rendezés, keresés==
  

A lap jelenlegi, 2013. január 29., 20:06-kori változata

Rendezés, keresés

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 TG1 a nyelv szavaira mindig megáll elfogadó állapotban.
  • A nyelv eleme coRE, így TG2 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). TG1 és TG2 valamelyike biztosan megáll. Ha TG1 elfogad, akkor elfogadunk. Ha TG2 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) = Mw(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. (Lu ∈ RE, hiszen az Univerzális Turing-gép elfogadja; de Lu ∉ 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. (Ld ∉ 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. (Lh ∈ RE, de Lh ∉ 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.