Recursiva
Origem: Wikipédia, a enciclopédia livre.
Uma linguagem eh dita recursiva quando existe uma <a href="http://pt.wikipedia.org/wiki/M%C3%A1quina_de_Turing">Máquina de Turing</a> que sempre pára, com "sim" ou 1" para instâncias positivas e "nao" ou "0" para instâncias negativas do programa