Redigerer Rekursivt nummererbare språk

I [[matematikk]], [[informatikk]] og [[logikk]] er et '''rekursivt nummererbart språk''' (også kalt '''turinggjenkjennelig språk''') et [[Formelt språk|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ært språk|regulære språk]], [[Kontekstfritt språk|kontekstfrie språk]], [[kontekstsensitive språk]] og [[rekursive språk]] er turinggjenkjennelige.

== Eksempler ==
[[Stoppeproblemet]] er turinggjenkjennelig, men ikke [[Rekursive språk|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.
* [[Kleenestjerne|Kleenestjerna]] av L
* [[Konkatenering|Konkateneringa]] av L og P
* [[Union]]en av L og P
* [[Snitt (mengdelære)|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.

[[Kategori:Formelle språk]]