Existe-t-il un nombre indéniable de langage décidable de Turing?

17

Il y a beaucoup (et je veux dire beaucoup) de langues dénombrables qui sont décidables par Turing. Est-ce qu'une langue innombrable peut être décidable de Turing?

Jyotirmoy Pramanik
la source
2
Si la langue de tous les mots possibles est indénombrable (ce qui nécessite un alphabet indénombrable), elle fournit immédiatement un exemple de langue indénombrable décidable de Turing (trivialement). Si ce n'est pas le cas (c'est-à-dire qu'il est dénombrable), les sous-langues ne sont pas non plus innombrables.
Marc van Leeuwen

Réponses:

25

Chaque langue sur un alphabet fini (ou même dénombrable) est dénombrable. En supposant que l'alphabet de votre machine Turing est fini, toute langue qu'il peut éventuellement accepter est dénombrable.

Yuval Filmus
la source
Qu'en est-il de l'ensemble de toutes les langues d'un nombre fini de chaînes sur un alphabet infiniment comptable? Est-ce dénombrable ou innombrable? De plus, je n'ai pas pu penser à la preuve que "la langue sur un alphabet infiniment comptable est dénombrable".
anir
Votre ensemble est également dénombrable.
Yuval Filmus
Cela prouve que "un ensemble de langues sur un alphabet fini est dénombrable". Je pense que nous pouvons prouver que "un ensemble de langues contenant des chaînes infiniment dénombrables sur un alphabet fini est dénombrable" suivant la même approche de preuve en raison de l'alphabet fini. Mais je ne peux pas imaginer comment cette approche peut être adaptée à un alphabet infiniment comptable.
anir
Vous ne pouvez pas le prouver car c'est faux. Le nombre de séquences binaires infinies est déjà indénombrable.
Yuval Filmus
12

Nous ne pouvons avoir d'innombrables langues que si nous autorisons des mots de longueur infinie, voir par exemple la langue régulière Omega . Ces langues sont appelées -langues. Un autre exemple sera le langage d'un sous-ensemble de réels qui contient, disons, des extensions décimales de tous les nombres réels.ω

Il existe certains modèles dans lesquels les machines de Turing sont modifiées pour accepter les langues . Certains de ces modèles utilisent la condition Buchi pour l'acceptation. Puisque vous ne pouvez pas voir l'intégralité de l'entrée en temps fini, nous disons que l'entrée est acceptée si la machine de Turing entre dans l'état d'acceptation infiniment de fois. Si nous pouvons le prouver en analysant l'entrée (et non en l'exécutant), nous disons que l'entrée est acceptée.ω

Shreesh
la source
1
Pourquoi l'alphabet devrait-il être dénombrable?
leftaroundabout
2
Chaque modèle étudié a un alphabet fini. Si l'alphabet devient également infini (dénombrable ou non dénombrable), il est difficile d'avoir un modèle raisonnable.
Shreesh
@Shreesh Eh bien, si l'alphabet est indénombrable, une cartographie naïve d'un FSM (avec des transitions indénombrables entre un nombre fini d'états) pourrait être plutôt puissante?
Yakk
1
Certes, ce sont le type d'extensions, qui peuvent avoir des classes de langues qui peuvent être des super-classes de langues RE ou récursives. Mais ils ne sont pas bien étudiés, voire pas du tout. Le plus gros problème est, à mon avis, comment pouvons-nous donner une représentation finie de la machine. Ensuite, vous devez écrire le symbole dans une cellule de bande. Même l'humble cellule peut avoir besoin d'une mémoire infinie pour stocker la description du symbole de bande en cours d'écriture.
Shreesh
Ceci est une excellente explication. J'ajouterais que même si un critère habituel d'acceptation / rejet est utilisé, on pourrait en quelque sorte dire qu'il existe encore certaines langues qu'une machine de Turing pourrait décider et aurait techniquement un nombre incalculable de chaînes, mais uniquement parce que la grande majorité des caractères sont " inutile "à la langue.
Owen
5

La calculabilité classique traite des fonctions sur des chaînes finies d'un alphabet fini. Par conséquent, toutes les langues, qu'elles soient décidables ou indécidables, sont dénombrables.

Pour considérer les langages innombrables, nous devons regarder des chaînes infinies à la place des chaînes finies. (AFAIK, avoir un alphabet infini n'est pas très intéressant et ne correspond pas à un modèle de calcul réaliste en soi.)

Il existe des modèles de calcul où nous pouvons traiter des chaînes infinies qui nous permettent de représenter des objets de domaines innombrables comme des nombres réels. Ceux-ci sont souvent représentés comme des calculs de type supérieur. Un modèle qui utilise des machines Turing est le modèle TTE. Dans ce modèle, l'entrée peut être des chaînes infinies et les machines peuvent accéder à n'importe quel élément de la chaîne souhaitée. La machine n'a pas besoin de s'arrêter, cependant il y a des conditions pour s'assurer que la sortie de la machine converge.

Supposons que l'entrée de notre machine provient de , c'est-à-dire des chaînes infinies de l'alphabet Σ , par exemple Σ = { 0 , 1 } . Il y a alors Σ N = 2 NΣωΣΣ={0,1}ΣN=2N chaînes. Il existe donc langues possibles. Le nombre de machines TTE Turing est toujours comptabilisable. La plupart de ces langues sont donc indécidables.22N

Mais il y a quelque chose d'encore plus intéressant ici: si vous voulez que la machine s'arrête toujours, elle ne pourra lire qu'une partie initiale finie de l'entrée. En conséquence, nous avons ce qui suit: Soit une machine TTE qui s'arrête toujours (en temps fini). Il existe alors un langage sans préfixe L Σ et la machine de Turing N tels que pour tout x Σ ω , M accepte x ssiMLΣNxΣωMx accepte la partie initiale de x qui est en L .NxL

En termes simples, le calcul des machines TTE Turing qui s'arrêtent toujours est déterminé par le calcul d'une machine Turing sur des chaînes finies.


Permettez-moi de donner un exemple de langages décidables et indécidables de chaînes infinies:

  1. Pour tout le langage des chaînes infinies dont la k ème position est 0 est décidable. La même chose avec k ème position étant 1. L'intersection de deux langages décidables est décidable, par exemple des chaînes dont la 3 ème position est 0 et la 6 ème position est 1.kNkk36

  2. L'union de deux langues décidables est décidable. Par exemple, les chaînes qui commencent par ou 10 .010

  3. Soit une liste énumérable de langues décidables. Alors L = i L i est semi-décidable, autrement dit , il est machine qui arrête et accepte chaque fois qu'un chaînes en L et n'accepte pas quand les chaînes ne sont pas en L . S'il n'est pas dans L, la machine peut ne pas s'arrêter. Toute langue semi-décidable peut être obtenue en prenant l'union d'une liste énumérable de langues de la forme donnée au point 1 ci-dessus.LiL=iLiLLL

  4. Une langue est décidable si la langue et son complément sont semi-décidables.

  5. kk


xlgxxlgx à nous.


f{0,1}f1(1)". Il existe également de nombreuses autres références sur le site Web de Computability and Complexity in Analysis Network .

Kaveh
la source
1
" En conséquence, toutes les langues sont finies " - Voulez-vous dire dénombrable?
Anton Trunov
Je pense que oui, M. Trunov.
Jyotirmoy Pramanik
C'est un bon article, mais je ne vois pas ce que sa masse a à voir avec la question spécifique posée ici. Peut-être que vous vouliez créer une paire question-réponse?
Raphael