A Turing-gép által felismert nyelv definíció szerint az általa elfogadott karakterláncok halmaza. Amikor egy bemenetet adnak a gépnek, azt vagy elfogadja, vagy nem.
Melyik nyelvet fogadja el a Turing-gép?
A TM elfogadja a egy nyelvet, ha bármely bemeneti karakterláncra végleges állapotba kerül w Egy nyelv rekurzívan felsorolható (a 0-s típusú nyelvtan által generált), ha elfogadja egy Turing-gép. A TM dönt egy nyelvről, ha elfogadja azt, és elutasító állapotba lép minden olyan bemenet esetén, amely nem az adott nyelven van.
Mi az a Turing-felismerhető nyelv?
Egy Turing által felismerhető nyelv ha van egy gép, amely csak az adott nyelven lévő karakterláncokat állítja le és fogadja el, és nem azon a nyelven, akkor a TM vagy elutasítja, vagy egyáltalán nem áll meg.… Egy nyelvet Turing felismerhetőnek neveznek, ha néhány Turing-gép felismeri.
Elfogadja a Turing-gép a nyelvet?
A turinggép az összes nyelvet elfogadja, annak ellenére, hogy rekurzívan felsorolhatók. A rekurzív azt jelenti, hogy ugyanazt a szabályrendszert tetszőleges számú alkalommal megismételjük, a felsorolás pedig az elemek listáját.
Mi a TM nyelve?
A TM nyelve az általa elfogadott karakterláncok halmazaként van meghatározva. Nem minden nyelv a Turing-gép nyelve – ez az elméleti számítástechnika egyik mérföldkőnek számító eredménye.
