Existe-t-il des propriétés indécidables des automates non complets de Turing?

Existe-t-il des propriétés indécidables des automates linéaires bornés (en évitant l'astuce de la langue vide)? Et pour un automate fini déterministe? (mettre de côté l'intraçabilité).

J'aimerais obtenir un exemple (si possible) d'un problème indécidable défini sans utiliser de machines Turing explicitement les .

Turing l'exhaustivité d'un modèle est-il nécessaire pour prendre en charge des problèmes non calculables?

Problèmes indécidables concernant les grammaires sans contexte, et donc les accepteurs de refoulement, qui sont des MT restreintes de Wikipedia ...

1. Étant donné un CFG, génère-t-il la langue de toutes les chaînes sur l'alphabet des symboles terminaux utilisé dans ses règles?

2. Étant donné deux CFG, génèrent-ils le même langage?

3. Étant donné deux CFG, la première peut-elle générer toutes les chaînes que la seconde peut générer?

Il existe de nombreux autres sur les CFG / PDA ainsi que les CSG / LBA et de nombreux autres modèles «plus simples que TM».

Ce que vous demandez dans la dernière partie de la question n'est pas clair, principalement parce que "un problème concernant un modèle de machine" n'est pas défini.

J'aimerais obtenir un exemple (si possible) de problème indécidable sans avoir besoin de Turing Machine

Soit une classe de machines et permet d'utiliser i comme code de M i . Nous pouvons aussi interpréter i comme le code de i th TM et demander que, étant donné M i, le i th TM s'arrête? Et ce problème concernant M i s est indécidable.$\{M_i\}$$i$$M_i$$i$$i$$M_i$$i$$M_i$

Une langue n'est qu'un ensemble de chaînes, quelle interprétation vous attribuez aux chaînes n'a aucun effet sur la décidabilité de la langue. À moins que vous ne définissiez formellement ce que vous entendez par un modèle de machine et un problème concernant ces machines, vous ne pourrez pas répondre à vos questions ultérieures.

Turing complète-t-il la machinerie minimale pour prendre en charge un problème indécidable?

Encore une fois, le point que j'ai mentionné ci-dessus s'applique. Une question plus raisonnable serait: toutes les preuves d'indécidabilité passent-elles par quelque chose de similaire à l'indécidabilité du problème d'arrêt des MT? (La réponse est: il existe d'autres moyens).

Une autre question possible est: quel est le plus petit sous-ensemble de MT où le problème d'arrêt pour eux est indécidable. Évidemment, une telle classe devrait contenir des problèmes qui ne s'arrêtent pas (sinon le problème est trivialement décidable). Nous pouvons facilement créer des sous-ensembles artificiels de MT où le problème d'arrêt n'est pas décidable sans être en mesure de calculer quoi que ce soit d'utile. Une question plus intéressante concerne les grands ensembles de MT décidables où l'arrêt est décidable pour eux.

Voici un autre point: dès que vous avez une très petite capacité à manipuler des bits (par exemple une taille polynomiale ), vous pouvez créer une machine N avec trois entrées: e , x et c de telle sorte qu'elle produise 1 ssi c est un arrêt de l'acceptation du calcul de TM M e sur l'entrée x . Ensuite, vous pouvez poser les problèmes comme: y a-t-il un c st N ( e , x , c ) est 1? ce qui est un problème indécidable.$\mathsf{CNF}$$N$$e$$x$$c$$c$$M_e$$x$$c$$N(e,x,c)$

Il existe un problème indécidable très simple pour les automates à états finis. Divisez l'alphabet en deux moitiés , où les lettres en ˉ Σ sont des copies "barrées". Maintenant, étant donné un automate à états finis A sur Σ ∪ ˉ Σ, décidez s'il accepte une chaîne telle que la partie non barrée est égale à la partie barrée (si nous ignorons les barres). Par exemple, la chaîne a a ˉ a ˉ a b ˉ b ˉ a a serait correcte (les deux parties épelent a a b a ).$\Sigma \cup \bar\Sigma$$\bar\Sigma$$A$$\Sigma\cup\bar\Sigma$$a a \bar a \bar a b\bar b \bar aa$$aaba$

Oui, c'est un problème de post-correspondance caché dans un automate à états finis. L'exhaustivité de Turing est loin d'être évidente dans la question. Il est là, en arrière-plan, alors que les deux copies (non barrées et barrées) codent ensemble une file d'attente, elle-même de puissance Turing.

"Est-il possible de construire un problème indécidable pour un automate moins puissant qu'une machine de Turing?" "

Oui. Un automate est une formulation axiomatique cohérente de la théorie des nombres (par exemple, voir (1) ) et, par conséquent, selon le premier théorème d'incomplétude de Gödel, il doit inclure des propositions indécidables.

Exemple:

Tout problème indécidable pour une MT est également indécidable pour tout automate qu'une MT peut simuler. Pourquoi? Parce que si un automate moins puissant qu'une MT peut décider d'un langage qu'une MT ne peut pas décider, une MT devrait pouvoir le décider en simulant l'automate avec renvoie une contradiction.

Emil Post a voulu trouver la réponse à cette question: y a-t-il un ensemble non récursif (non calculable) qui ne résout pas le problème d'arrêt. Il n'a réussi qu'en partie, mais ce qu'il a fait, c'est créer ce qu'on appelle des ensembles simples .

De Wikipédia:

Un sous-ensemble des naturels est appelé simple s'il est co-infini et récursivement énumérable, mais chaque sous-ensemble infini de son complément ne peut pas être énuméré récursivement. Les ensembles simples sont des exemples d'ensembles énumérables récursivement, qui ne sont pas récursifs. Jetez un oeil à l'article Wikipedia pour plus d'informations et de références, ensemble simple .