L nyelv rekurziv ha minden T turinggép amely (L eleme szigma az xediken) minden w eleme szigma az xediken esetén T megáll w-n és T elfogadja w-t ebbõl következik w eleme Lnek (minden bemenõ szón megáll és pontossan a nyelv szavait fogadja el)

L nyelv rekurziv felsorolható: ha mindet T turinggép (L eleme szigma az x-en) amelyre igaz: minden w eleme szigma az xediken-val T elfogadja w-t ha pontossan akkor ha w eleme L-nek (itt nem feltételelzük, hogy minden inputra megáll) van ami a nyelvet ismeri fel, de nem minden esetben áll meg.

-------
rekurzívnak nevezünk, ha van olyan T Turing-gép, ami bármely x bemenettel (vagyis elso szalagjára
x-et írva, a többit üresen hagyva) véges ido után megáll, és az elso szalagjára az f(x) szó lesz írva.

Definíció: Az L beli nyelvet rekurzívnak hívjuk, ha karakterisztikus függvénye:
fL(x) = {1, ha x eleme L ; 0, ha x eleme az elemi abcnek - L}

Nyilvánvaló, hogy minden véges nyelv rekurzív

rekurzíve fölsorolhatónak ha csak L beli elemeket fogad el és megállás után csak ezeket kapjuk vissza