Eine Sprache L "teilmenge" "Sigma* " heißt rekursiv (entscheidbar), wenn eine Turingmaschine existiert, die immer hält und Eingaben w "element" "Sigma" genau dann akzeptiert, wenn w "element" L ist.
Der Nachweis der Nicht-Rekursivität einer Sprache bedeutet, dass man die Suche nach einem Algorithmus für das Problem aufgeben kann, das durch die Sprache beschrieben wird. Wenn es nämlich keine Turingmaschine gibt, die ein solches "Entscheidungsproblem" löst, so gibt es nach der Churchschen These überhaupt keinen Algorithmus für das Problem. Man beschränkt sich bei dieser Definition auf Entscheidungsprobleme, also auf Probleme, deren Antwort nur 'Ja' oder 'Nein' sein kann. Man kann zeigen, dass dies keine wirkliche Einschränkung bedeutet. Durch diese Beschränkung kann man alle Probleme auf Sprachen zurückführen; diese können u.a. durch (Chomsky-) Grammatiken beschrieben werden: Ein (Entscheidungs-) Problem mit der Eingabe w ist somit genau dann wahr, wenn w in der dem Problem zugehörigen Sprache L liegt. Somit besteht eine Brücke zwischen dem "erzeugenden" Grammatik-Modell und dem "akzeptierenden" Automaten-Modell. In der Tat kann man zu jeder Chomsky-Grammatik-Klasse eine Automatenklasse finden, die genau die Sprachen der jew. Klasse akzeptiert und umgekehrt.
Die Menge der rekursiven Sprachen ist echte Teilmenge der Chomsky-Typ-0 (oder rekursiv aufzählbaren) Sprachen und echte Obermenge der Chomsky-Typ-1 Sprachen: - Das Halteproblem ist rekursiv aufzählbar, aber nicht rekursiv - *** ist rekursiv, aber nicht Typ 1 (auch kontextsensitiv genannt)
Der Unterschied zu den rekursiv aufzählbaren Sprachen ist definitionsgemäß, dass eine Turingmaschine auf rekursiven Sprachen immer halten, auf rekursiv aufzählbaren jedoch nur halten muss, wenn das Wort in der Sprache liegt.