Encontrei muitas definições de linguagens recursivas e recursivamente enumeráveis. Mas eu não conseguia entender direito o que são.
Alguém pode me dizer o que são em palavras simples?
Na verdade não. Você deveria ler alguns livros. Talvez possamos recomendar alguns.
Dito isto, uma linguagem é recursiva se houver uma máquina de Turing que sempre pode responder "sim" ou "não" se uma determinada sequência de caracteres fizer parte dessa linguagem. Se levantarmos esse requisito para simplesmente dizer "sim" para cadeias de caracteres da linguagem (ele pode ser executado para sempre, se não for), teremos uma linguagem recursivamente enumerável. Não é difícil ver que uma linguagem recursiva pode ser decidida por uma máquina de Turing, enquanto uma linguagem recursivamente enumerável pode ter suas cadeias listadas (por exemplo, executando um número infinito de máquinas de Turing em paralelo - sim, isso é possível, consulte cauda de pomba - em todas as seqüências de caracteres do alfabeto e emitindo uma sequência se a TM correspondente aceitar). Existem muitas, muitas definições equivalentes.
Um problema é recursivo ou decidível se uma máquina puder calcular a resposta.
Um problema é recursivamente enumerável ou semidecidável se uma máquina puder estar convencida de que a resposta é positiva.
Um idioma é apenas um conjunto de strings. Possivelmente de cardinalidade infinita.
Um idioma é recursivo enumerável se existir uma TM que continue produzindo strings que pertencem ao idioma (e somente esses strings), de modo que eventualmente todas as strings do idioma estejam na saída.
Um idioma é recursivo se, a TM acima não apenas exibir todas as seqüências de caracteres no idioma, mas também fazê-lo em ordem! (digamos, lexicograficamente).
Tenho certeza de que você pode facilmente pensar em linguagens recursivas (e criar uma TM que as produz por ordem). É muito difícil criar linguagens recursivas enumeráveis (que não sejam recursivas), a menos que você leia um pouco mais sobre indecidibilidade e diagonalização. Mas essas línguas existem.
Idiomas recursivos são decidíveis por algumas máquinas de Turing, ou seja, existe uma TM que pode, dada qualquer sequência de entrada (sobre o alfabeto apropriado) responder corretamente sim se a sequência estiver no idioma ou não se não estiver.
Linguagens recursivamente enumeráveis são reconhecidas apenas, ou seja, existe uma Máquina de Turing que aceita quando a string está no idioma, mas pode ser repetida para sempre se a string não estiver no idioma.
fonte
Eu sinto que a principal diferença entre linguagens recursivas e recursivamente enumeráveis é que a máquina Recursive Turing pára no estado não final se ela não aceita uma string
A máquina de Turing recursivamente enumerável, se ela não aceita uma string, pode parar no estado não final ou loop para sempre, o que não é o caso de linguagens recursivas
fonte
==> Um idioma é recursivo se existir uma máquina de Turing que aceite todas as cadeias de caracteres no idioma e rejeite se não estiver no idioma. por exemplo, vamos pegar a máquina de Turing M e a String w: se a string w for um membro da máquina de Turing M, então M parará em seu estado final, caso contrário ela rejeitará o cálculo. ==> ==> Uma linguagem é recursiva enumerável se existir uma máquina de Turing que aceite todas as seqüências de caracteres na linguagem e rejeite se não estiver na linguagem. por exemplo, vamos usar a máquina de Turing M e a String w: se a string w estiver no idioma, então M parará em seu estado final. Caso contrário, ele rejeita o cálculo ou pode ser executado para sempre.
fonte