Rekursivt nummererbare språk

I matematikk, informatikk og logikk er et rekursivt nummererbart språk (også kalt turinggjenkjennelig språk) et språk som kan gjenkjennes av ei turingmaskin. Sagt på en annen måte, hvis det eksisterer ei turingmaskin som vil kunne ta alle gyldige strenger for det gitte språket. En annen definisjon på det er hvis språket er en rekursivt nummererbar delmengde av mengden av alle mulige ord over alfabetet av språket.

I Chomskyhierarkiet er turinggjenkjennelige språk kjent som type-0 språk og utgjør det ytterste laget i hierarkiet. Det betyr at alle regulære språk, kontekstfrie språk, kontekstsensitive språk og rekursive språk er turinggjenkjennelige.

Eksempler

Stoppeproblemet er turinggjenkjennelig, men ikke turingavgjørbart. Det betyr altså at man kan lage ei turingmaskin som tar ei turingmaskin N som input og som aksepterer om N stopper. Men det finnes inga turingmaskin som bestemmer om N vil stoppe eller ikke. Da ville det også vært turingavgjørbart.

Et annet velkjent eksempel på et turinggjenkjennelig språk er posts korrespondanseproblem. Dette er heller ikke turingavgjørbart fordi det finnes inga turingmaskin for å bestemme problemet, med mindre det er over et alfabet bestående av et symbol.

Egenskaper

Turinggjenkjennelige språk er lukket under følgende operasjoner. Det vil altså si at for to turinggjenkjennelige språk L og P, så vil resultatet av operasjonen fortsatt være et turinggjenkjennelig 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, Springer.