Rekursivt nummererbare språk

I matematikk, informatikk og logikk er eit rekursivt nummererbart språk (òg kalla turinggjenkjenneleg språk) eit språk som kan kjennast att av ei turingmaskin. Sagt på ein annan måte, viss det eksisterer ei turingmaskin som vil kunne ta alle gyldige strengar for det gjevne språket. Ein annan ekvivalent definisjon på det er viss språket er ei rekursivt nummererbar delmengde av mengda av alle moglege ord over alfabetet av språket.

I Chomskyhierarkiet er turinggjenkjennelege språk kjende som type-0 språk og utgjer det ytste laget i hierarkiet. Det tyder at alle regulære språk, kontekstfrie språk, kontekstsensitive språk og rekursive språk er turinggjenkjennelege.

Døme

Stoppeproblemet er turinggjenkjennelig, men ikkje turingavgjerbart. Det tyder altså at ein kan laga ei turingmaskin som tek ei turingmaskin N som input og som aksepterer om N stoppar. Men det finst inga turingmaskin som avgjer om N vil stoppa eller ikkje. Då ville det òg vore turingavgjerbart.

Eit anna velkjent døme på eit turinggjenkjennelig språk er korrespondanseproblemet til post. Dette er heller ikkje turingavgjerbart fordi det finst inga turingmaskin for å avgjera problemet, med mindre det er over eit alfabet av berre eit einskilt symbol.

Eigenskapar

Turinggjenkjennelege språk er lukka under dei følgjande operasjonane. Det vil altså seia at for to turinggjenkjennelege språk L og P, så vil resultatet av operasjonen framleis vera eit turinggjenkjenneleg språk.

• Kleenestjerna av L
• Konkateneringa av L og P
• Unionen av L og P
• Snittet av L og P

Litteratur

• Sipser, M. (1996), Introduction to the Theory of Computation, PWS Publishing Co.
• Kozen, D.C. (1997), Automata and Computability, Springar.