Définition de langage récursif et récursivement énumérable pour un profane

J'ai rencontré de nombreuses définitions de langages récursifs et récursivement énumérables. Mais je ne pouvais pas vraiment comprendre ce que c'était.

Quelqu'un peut-il me dire de quoi il s'agit en termes simples?

Pas vraiment. Vous devriez lire quelques livres. Nous pouvons peut-être en recommander.

Cela dit, un langage est récursif s'il existe une machine de Turing qui peut toujours répondre "oui" ou "non" si une chaîne donnée fait partie de ce langage. Si nous levons cette exigence pour simplement dire «oui» pour les chaînes du langage (il peut s'exécuter indéfiniment s'il ne l'est pas), alors nous avons un langage récursivement énumérable. Il n'est pas difficile de voir qu'un langage récursif peut être décidé par une machine Turing, tandis qu'un langage récursivement énumérable peut avoir ses chaînes répertoriées (par exemple, en exécutant un nombre infini de machines Turing en parallèle - oui c'est possible, voir dove-tailing - sur toutes les chaînes de l'alphabet, et sortie d'une chaîne si la MT correspondante accepte). Il existe de très nombreuses définitions équivalentes.

Un problème est récursif ou décidable si une machine peut calculer la réponse.

Un problème est récursivement énumérable ou semi - décidable si une machine peut être convaincue que la réponse est positive.

Une langue n'est qu'un ensemble de chaînes. Peut-être d'une cardinalité infinie.

Une langue est récursive énumérable s'il existe une MT qui continue à produire des chaînes qui appartiennent à la langue (et seulement de telles chaînes), de sorte que finalement chaque chaîne de la langue sera dans la sortie.

Une langue est récursive si, la TM ci-dessus non seulement génère toutes les chaînes de la langue, mais le fait également dans l'ordre! (disons lexicographiquement).

Je suis sûr que vous pouvez facilement penser aux langages récursifs (et construire une MT qui les sort par ordre). Il est assez difficile de trouver des langages énumérables récursifs (qui ne sont pas récursifs), sauf si vous en lisez un peu plus sur l'indécidabilité et la diagonalisation. Mais de telles langues existent.

Certaines langues récursives sont décidables par certaines machines de Turing, c'est-à-dire qu'il existe une MT qui peut, étant donné n'importe quelle chaîne d'entrée (sur l'alphabet approprié), répondre correctement oui si la chaîne est dans la langue, ou non si ce n'est pas le cas.

Les langues récursivement énumérables ne sont reconnues que, c'est-à-dire qu'il existe une machine de Turing qui accepte quand la chaîne est dans la langue mais elle peut boucler indéfiniment si la chaîne n'est pas dans la langue.

Je pense que la principale différence entre les langues récursives et récursivement énumérables est que la machine de Turing récursive s'arrête dans un état non final si elle n'accepte pas une chaîne

La machine de Turing récursivement énumérable si elle n'accepte pas une chaîne peut s'arrêter dans un état non final ou en boucle pour toujours ce qui n'est pas le cas pour les langages récursifs

==> Une langue est récursive s'il existe une machine Turing qui accepte chaque chaîne de la langue et la rejette si elle ne l'est pas. par exemple, prenons la machine de Turing M et la chaîne w: si la chaîne w est membre de la machine de Turing M, alors M s'arrête dans son état final sinon il rejette le calcul. ==> ==> Une langue est récursive énumérable s'il existe une machine Turing qui accepte chaque chaîne dans la langue et rejette si elle n'est pas dans la langue peut être bouclée pour toujours. par exemple, prenons la machine de Turing M et la chaîne w: si la chaîne w est dans le langage, alors M s'arrête dans son état final. Sinon, il rejette le calcul ou peut être exécuté indéfiniment.