Mi az, ami felismerhető és eldönthető?
Pontszám: 4,3/5 ( 73 szavazat )Egy nyelvről azt mondják, hogy eldönthető, ha van egy gép, amely elfogadja a nyelvben lévő karakterláncokat, és elutasítja a nem a nyelvben lévő karakterláncokat . 2. Egy nyelvet Turing Felismerhetőnek nevezünk, ha valamilyen Turing-gép felismeri.
Mi a különbség az eldönthető és a felismerhető között?
Ha L eldönthető, akkor L-t egy TM M ismeri fel, amely minden bemeneten megáll . Vegye figyelembe, hogy az L-t más TM M' felismerheti, amely nem mindig áll meg. Ha L felismerhető, akkor lehet olyan TM M, amely felismeri L-t, de örökké fut, ahelyett, hogy elutasítana néhány, L-ben nem szereplő bemenetet.
Mit jelent az, ha egy nyelv felismerhető?
Egy nyelv felismerhető, ha van egy Turing-gép, amely csak az adott nyelvben lévő karakterláncokat állítja meg és fogadja el, és a nem a nyelven lévő karakterláncok esetében a TM vagy elutasítja, vagy egyáltalán nem áll le.
Mit jelent az, hogy egy Turing-gép felismerhető?
A felismerhetőség azt jelenti, hogy létezik egy Turing-gép, amely leállítja és elfogadja bármely bemeneti szót, és megáll vagy nem (de nem megáll és elfogad!) bármely bemenetre.
Minden felismerhető nyelv eldönthető?
Megjegyzés: Az eldönthető nyelvek a kiegészítés alatt zárva vannak, de a felismerhető nyelvek nem . – A csak írás azt jelenti, hogy (a) a kimeneti szalagon lévő szimbólum nem befolyásolja az átmeneteket, és (b) a szalagfej csak jobbra mozog. Megjegyzés M-nek nem kell sorrendben felsorolnia a karakterláncokat.
Dönthetőség és eldönthetetlenség
Melyik nyelv dönthető el?
Egy nyelvet Decidable-nak vagy Rekurzívnak nevezünk, ha létezik egy Turing-gép , amely elfogad és leállít minden w bemeneti karakterláncot. Minden eldönthető nyelv Turing-elfogadható. Egy P döntési probléma eldönthető, ha a P-hez tartozó összes igen példány L nyelve eldönthető.
Mi a különbség a PDA és a TM között?
Válasz. A PDA csak a verem tetejére férhet hozzá, míg a TM a végtelen szalag bármely pozíciójához hozzáférhet . Egy automata, amely nem csak egy, hanem két veremhez fér hozzá, szimulálhat egy TM-et, és így egyenértékű számítási teljesítménnyel rendelkezik.
Hogyan bizonyítja, hogy Turing felismerhető?
Annak bizonyítása, hogy egy adott nyelv Turing által felismerhető: Készítsünk egy algoritmust, amely pontosan azokat a karakterláncokat fogadja el, amelyek a nyelvben vannak . El kell utasítania, vagy ismételnie kell minden olyan karakterláncot, amely nem a nyelven található.
A TM felismerhető?
Egy nyelv akkor is felismerhető, ha a TM befejezi és elutasítja a karakterláncot, vagy egyáltalán nem fejeződik be . Ez azt jelenti, hogy a TM folytatja a számítást, ha a megadott bemenet nem a nyelven található.
Mi a különbség a döntő és a felismerő Turing-gép között?
A Turing-gép dönt egy nyelvről, ha leállítja és elfogadja az adott nyelv összes karakterláncát , és leállítja és elutasítja a nem azon a nyelven lévő karakterláncokat. A totális Turing-gép vagy a döntéshozó olyan gép, amely a bemenettől függetlenül mindig megáll.
Hogyan állapítható meg, hogy egy nyelv eldönthető vagy eldönthetetlen?
Egy nyelv akkor és csak akkor határozható meg, ha az és kiegészítése felismerhető . Bizonyíték. Ha egy nyelv eldönthető, akkor a komplementere is eldönthető (a kiegészítés alatti lezárással).
Honnan tudod, hogy egy nyelv felismerhető-e?
Egy L nyelv akkor és csak akkor ismerhető fel, ha létezik ellenőrző L nyelvre, ahol a hitelesítő egy Turing-gép, amely minden bemenetre és minden w∈Σ∗, w∈L↔∃c∈Σ∗ esetén megáll. V elfogadja a ⟨w,c⟩-t.
Honnan tudod, hogy egy halmaz eldönthető-e?
A természetes számok M halmazát akkor mondjuk eldönthetőnek, ha létezik egy általános rekurzív f függvény, amelyre M={n:f(n)=0} . Ebben az esetben f egy algoritmus annak ellenőrzésére, hogy egy természetes szám M-hez tartozik-e: valóban, n∈M ekvivalens f(n)=0-val.
Az alábbiak közül melyik a megoldható probléma?
1) Ez a Turing-gép megállítási problémájának egy változata, és eldönthetetlen. 2) A CFL nincs komplement alá zárva, így eldönthetetlen. 3) A reguláris nyelvek kiegészítése is szabályos. ... 4) A Recursvie nyelv a komplement alatt zárva van , így eldönthető.
Mi az a félig eldönthető nyelv?
Ha azt mondjuk, hogy egy L nyelv félig eldönthető, az azt jelenti , hogy van egy algoritmus, amely pontosan elfogadja az L-beli karakterláncokat ; azonban egy x /∈ L karakterlánc esetén az algoritmus vagy elutasítja, vagy nem állítja le. Ahhoz, hogy ez az intuíció érvényes legyen, el kell fogadnunk a Church-Turing-tézist.
Az alábbiak közül melyik dönthető el?
Az alábbiak közül melyik dönthető el? Magyarázat: (A) Két reguláris nyelv metszéspontja reguláris, és eldönthető, hogy egy reguláris nyelv végtelen-e .
Miért nem dönthető el az ATM?
D elutasítja (D), de ekkor H elfogadja (D,(D)) és ebből D elfogadja (D), ellentmondás! Tehát D nem létezhet , így H sem létezhet (D H-ból épült). Ez azt jelenti, hogy az ATM eldönthetetlen.
Felismerhető a megállás?
és a HALT eldönthetetlen. Nem lehet eldönteni, hogy egy TM elfogadja-e vagy végül megszűnik. és a HALT felismerhetőek . Mindig futtathatunk egy TM-et egy w karakterláncon, és elfogadhatjuk, ha a TM elfogadja vagy leáll.
Mit értesz nem determinisztikus TM alatt?
Az elméleti számítástechnikában a nemdeterminisztikus Turing-gép (NTM) a számítás olyan elméleti modellje, amelynek irányító szabályai egynél több lehetséges műveletet határoznak meg, amikor bizonyos helyzetekben . ... Az NTM-eket néha gondolatkísérletekben használják a számítógépek képességeinek és korlátainak vizsgálatára.
Az ATM-kiegészítés eldönthető?
Következmény 4.23: Az ATM Turing által felismerhető, de nem eldönthető , így a kiegészítő ATM NEM Turing által felismerhető.
Mi az, hogy Turing felismerhetetlen?
~ A TM a Turing által felismerhetetlen nyelv kanonikus példája. Ez azt jelenti, hogy nem létezik olyan Turing-gép, amely elfogadja az összes <M,w> gép-karakterlánc pár halmazát úgy, hogy M NEM áll meg, ha w-n fut. Ennek bizonyítéka nagyon rövid: Lemma: A TM Turing által felismerhető.
Az ETM eldönthető?
ETM = {< M > |M egy TM és L(M) = /0} eldönthetetlen . Bizonyíték: Csökkentse az ATM-et ETM-re. Tegyük fel, hogy az ETM eldönthető. ... NETM = {< M > |M egy TM és L(M) = /0} Turing által felismerhető, de nem eldönthető.
Melyik az erősebb PDA vagy DFA?
Egy DFA véges mennyiségű információra képes megjegyezni, de egy PDA végtelen mennyiségű információra képes megjegyezni. A Pushdown automata egyszerűen egy NFA, kiegészítve egy "külső verem memóriával". ... Ahhoz, hogy egy elemet beolvassunk a verembe, a legfelső elemeket ki kell emelni, és elvesznek. A PDA erősebb, mint az FA.
Melyik az erős véges automata?
Mint láthatjuk, az FA kisebb teljesítményű, mint bármely más gép. Fontos megjegyezni, hogy a DFA és az NFA azonos erejű, mivel minden NFA átalakítható DFA-vá, és minden DFA átalakítható NFA-vá. A Turing-gép, azaz a TM minden más gépnél erősebb.
Miért jobb a Turing gép, mint a PDA?
A Turing-gép egyszerre tud a szalagra írni és olvasni róla . A PDA csak a veremből LIFO módon olvas. A DFA-nak nincs adathordozója, amivel bármit is írhatna – mindennek véges állapotában kell lennie. A számítás egyik lépése megváltoztatja az aktuális állapotot, a fej aktuális pozícióját és a szalag tartalmát az aktuális pozícióban.