Digszám 03 Turing nyelvek Flashcards
(15 cards)
Mi a Turing-gép négy komponense?
Állapotok halmaza, szalag ábécé, átmeneti függvény, kezdőállapot
Mit csinál a Turing-gép működés közben?
Szimbólumot olvas a szalagról, felülírja azt, balra vagy jobbra lép, és új állapotba kerül
Mi az a konfiguráció a Turing-gép esetén?
A gép aktuális állapota, a szalagon az olvasott szimbólum, és a szalag bal és jobb oldala
Mikor áll meg egy Turing-gép?
Ha az átmeneti függvény nem definiált a jelenlegi állapotra és szimbólumra
Mi a Machine Schema célja?
Bonyolult Turing-gépek moduláris felépítése kisebb gépekből, egy kapcsolófüggvény vezérli a végrehajtást
Miből áll egy Machine Schema?
(m, η, M₀): ahol m az al-gépek halmaza, η a kapcsolófüggvény, M₀ a kezdőgép
Mi az a Turing-elfogadható nyelv?
Olyan nyelv, amelyre létezik Turing-gép, ami a nyelv szavaira megáll (de más szavakra nem feltétlen)
Mi az a Turing-eldönthető nyelv?
Olyan nyelv, amelyre létezik Turing-gép, ami minden bemenetre megáll és eldönti, hogy az a szó része-e a nyelvnek
Mi történik
ha egy szó nem eleme egy Turing-elfogadható nyelvnek?
Hogyan viselkedik egy Turing-gép Turing-eldönthető nyelv esetén?
Minden bemenetre megáll és a szalagra írja Y (igen) vagy N (nem)
Milyen műveletekre zártak a Turing-eldönthető nyelvek?
Unió, metszet, komplementer
Milyen műveletekre zártak a Turing-elfogadható nyelvek?
Unió, konkatenáció, Kleene-csillag
Mi a kapcsolat a Turing-eldönthető és Turing-elfogadható nyelvek között?
Minden Turing-eldönthető nyelv Turing-elfogadható is
Mikor eldönthető egy nyelv a Turing-gépek szerint?
Ha a nyelv és komplementere is Turing-elfogadható
Miben különbözik a Machine Schema az univerzális Turing-géptől?
Machine Schema moduláris gépvezérlésre szolgál, az UTM más gépeket szimulál egyetlen gépként
