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

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?

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.

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.$\omega$

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.$\omega$

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 $\Sigma^\omega$$\Sigma$$\Sigma = \{0,1\}$$\Sigma^\mathbb{N} = 2^\mathbb{N}$ 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.$2^{2^\mathbb{N}}$

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 ssi$M$$L \in \Sigma^*$$N$$x\in \Sigma^\omega$$M$$x$ accepte la partie initiale de x qui est en L .$N$$x$$L$

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.$k\in \mathbb{N}$$k$$k$$3$$6$

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

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.$L_i$$L = \cup_i L_i$$L$$L$$L$

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

5. $k$$k$

$x \mapsto \lg x$$x$$\lg x$ à nous.

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