Par exemple, dans les langages de programmation, il est courant d'écrire un compilateur / interprète X-in-X, mais à un niveau plus général, de nombreux systèmes Turing-complets connus peuvent se simuler de manière impressionnante (par exemple, simuler le jeu de la vie de Conway dans le jeu de la...
Le problème de décision CNF-SAT peut être décrit comme suit: Entrée: Une formule booléenne ϕϕ\phi sous forme normale conjonctive. Question: Existe-t-il une affectation de variable qui satisfait ϕϕ\phi ? J'envisage plusieurs approches différentes pour résoudre CNF-SAT avec une machine de Turing à...
J'ai lu quelque part qu'une machine Turing ne peut pas calculer cela et c'est donc indécidable mais pourquoi? Pourquoi est-il impossible sur le plan informatique pour une machine de générer l'arbre d'analyse et de prendre une décision? Peut-être que je me trompe et que cela peut être...
Je venais tout juste d'avoir une discussion sur les machines de Turing quand on m'a demandé: "La machine de Turing dérive-t-elle d'automates, ou est-ce l'inverse"? Je ne connaissais pas la réponse bien sûr, mais je suis curieux de le savoir. La machine de Turing est fondamentalement une version...
Comme vous le savez, il existe de nombreuses anomalies pour les machines de Turing à bande unique lorsque le temps est : simulation multi-bande TM, simulation d'un alphabet de bande plus grand avec seulement , constructibilité temporelle, non-étanchéité du théorème de la hiérarchie temporelle, ...o...
Est-il possible de tester algorithmiquement si un nombre calculable est rationnel ou entier? En d'autres termes, serait-il possible pour une bibliothèque qui implémente des nombres calculables de fournir les fonctions isIntegerou isRational? Je suppose que ce n'est pas possible, et que cela est en...
Avertissement: je connais très peu la théorie de la complexité. Je suis désolé mais il n'y a vraiment aucun moyen de poser cette question sans être (terriblement) concis: Quels devraient être les morphismes dans "la" catégorie des machines de Turing? Ceci est évidemment subjectif et dépend de...
Je cherche à obtenir une réponse définitive à la question du titre. Existe-t-il un ensemble de règles qui traduisent un programme en une configuration de pièces finies sur un plateau infini, de sorte que si le noir et blanc ne joue que des mouvements légaux, le jeu se termine en temps fini si le...
Toute langue qui n'est pas complète de Turing ne peut pas écrire elle-même un interprète. Je n'ai aucune idée de l'endroit où je l'ai lu, mais je l'ai vu utilisé à plusieurs reprises. Il semble que cela donne lieu à une sorte de langage complet «ultime» non Turing; celui (s) qui ne peutêtre...
L'une des choses étonnantes de l'informatique est que l'implémentation physique est en quelque sorte «hors de propos». Les gens ont réussi à construire des ordinateurs à partir de plusieurs substrats différents - relais, tubes à vide, transistors discrets, etc. Les gens pourraient bientôt réussir à...
Étant donné un langage L défini par une machine de Turing qui le décide, est-il possible de déterminer algorithmiquement si L se situe dans
D'un point de vue purement abstrait de raisonnement mathématique / informatique, (comment) pourrait-on même découvrir ou raisonner sur des problèmes comme 3-SAT, Subset Sum, Travelling Salesman, etc.? Serions - nous encore en mesure de raisonner sur eux de quelque façon significative avec juste la...
À propos de cette question, je me suis demandé: quelle est la complexité temporelle pour une machine de Turing à une seule bande et à une seule tête pour calculer la longueur de son entrée? Pour être précis, disons que l'alphabet de la bande est {0,1,b}{0,1,b}\{0,1,b\} , l'entrée est une chaîne en...
En termes simples: quelle est la correspondance entre les machines de Turing avec oracles et les familles de circuits uniformes avec oracles? Comment ces derniers sont-ils définis afin d'obtenir le même modèle de calcul, pour une machine Oracle Turing donnée? Cela peut être une question...
Existe-t-il une preuve que l'émulation d'une machine de Turing sur une machine de Turing inconsciente ne peut pas être effectuée en moins deO(mlogm)O(mlogm)\mathcal{O}\left(m\log m\right) where mmm is the number of steps the Turing machine uses? Or is this just an upper bound? In the paper of Paul...
Le théorème de la hiérarchie temporelle stipule que les machines de turing peuvent résoudre plus de problèmes si elles ont (assez) plus de temps. Tient-il d'une manière ou d'une autre si l'espace est limité asymptotiquement? Comment liéDTISP(g(n),O(s(n)))DTISP(g(n),O(s(n)))\textrm{DTISP}(g(n),...
Il est bien connu que le problème d'arrêt n'est pas calculable. Cependant, il est possible de "compresser" exponentiellement des informations sur le problème d'arrêt, de sorte que sa décompression soit calculable. Plus précisément, il est possible de calculer à partir d'une description de machines...
Je suis certain que je ne suis pas le premier à entretenir l'idée que je vais présenter. Cependant, il serait utile que je puisse trouver de la documentation liée à l'idée. L'idée est de construire une machine de Turing M avec la propriété que si P = NP alors M résoudra 3-SAT en temps polynomial....
Définissez comme la classe de langues pouvant être acceptée par une machine de Turing (multitape) dans le temps . (Le " " est juste pour simplifier la notation et éviter toute confusion.) Notez qu'il n'y a pas de autour de .f ( n ) + 1 + 1 O ( ⋅ ) f ( n ) + 1D T I M E (f( n )...
Existe-t-il une machine de Turing qui peut décider si presque toutes les autres machines de Turing s'arrêtent? N→{Mi}N→{Mi}\mathbb{N} \rightarrow \{M_i\}∥⋅∥‖⋅‖\| \cdot \| f(i)=∥{n:Mi can't decide whether Mn halts}∥.f(i)=‖{n:Mi can't decide whether Mn halts}‖.f(i) = \|\{n: M_i \text{ can't decide...