Turingi masina poolt äratuntav keel on definitsiooni järgi stringide komplekt, mida ta aktsepteerib. Kui masinale antakse sisend, siis see kas aktsepteeritakse või mitte.
Millist keelt Turingi masin aktsepteerib?
A TM aktsepteerib a keelt, kui see läheb mis tahes sisendstringi lõppolekusse w Keel on rekursiivselt loendatav (genereeritud 0-tüüpi grammatika abil), kui selle aktsepteerib Turingi masin. TM otsustab keele, kui ta seda aktsepteerib, ja siseneb tagasilükkamise olekusse mis tahes sisendi puhul, mis ei ole selles keeles.
Mis on Turingi äratuntav keel?
Keel, mis on Turingi äratuntav kui on olemas masin, mis peatab ja aktsepteerib ainult selles keeles olevaid stringe, mitte aga, siis see TM kas keeldub või ei peatu üldse.… Keelt nimetatakse Turingi äratuntavaks, kui mõni Turingi masin selle ära tunneb.
Kas Turingi masin aktsepteerib keelt?
Tuurimismasin aktsepteerib kõiki keeli, kuigi need on rekursiivselt loendatavad. Rekursiivne tähendab sama reeglistiku kordamist suvalise arvu kordi ja loendatav tähendab elementide loendit.
Mis on mälukaardi keel?
TM-i keel on määratletud kõigi stringide komplektina, mida see aktsepteerib. Mitte iga keel ei ole Turingi masina keel – see on üks teoreetilise arvutiteaduse märgilisi tulemusi.
