Questions marquées «computability»

Au travail, j'ai été chargé de déduire des informations de type sur un langage dynamique. Je réécris des séquences d'instructions en imbriquéeslet expressions , comme ceci: return x; Z => x var x; Z => let x = undefined in Z x = y; Z => let x = y in Z if x then T else F; Z => if x then...

J'ai rencontré le problème intéressant suivant: soit polynômes sur le champ des nombres réels, et supposons que leurs coefficients soient tous entiers (c'est-à-dire qu'il existe une représentation exacte finie de ces polynômes). Si nécessaire, nous pouvons supposer que le degré des deux polynômes...

On m'a dit que les ordinateurs quantiques ne sont pas plus puissants sur le plan informatique que les machines de Turing. Quelqu'un pourrait-il bien vouloir fournir des références bibliographiques expliquant ce

Existe-t-il un algorithme pour le problème suivant: Étant donné une machine de Turing qui décide d'un langage , existe-t-il une machine de Turing décidant telle que ?M1M1M_1M 2 L t 2 ( n ) = o ( t 1 ( n ) )LLLM2M2M_2LLLt2( n ) = o ( t1( n ) )t2(n)=o(t1(n))t_2(n) = o(t_1(n)) Les fonctions et sont...

Laissez L∅={⟨M⟩∣M is a Turing Machine and L(M)=∅}.L∅={⟨M⟩∣M is a Turing Machine and L(M)=∅}.L_\emptyset = \{\langle M\rangle \mid M \text{ is a Turing Machine and }L(M)=\emptyset\}. Existe-t-il une machine de Turing R qui décide (je ne veux pas dire reconnaît) la langue L∅L∅L_\emptyset ? Il semble...

Cette question est de savoir si chaque théorème mathématique peut être réduit à la question de savoir si une seule machine de Turing s'arrête. En particulier, je m'intéresse aux conjectures qui ne sont actuellement pas prouvées. Par exemple: Wikipedia dit qu'il est actuellement inconnu s'il existe...

Je suis désolé si cette question a une réponse triviale qui me manque. Chaque fois que j'étudie un problème qui s'est révélé indécidable, j'observe que la preuve repose sur une réduction à un autre problème qui s'est avéré indécidable. Je comprends que cela crée une sorte d'ordre sur le degré de...

Je comprends que la plupart des problèmes sont triviaux si un oracle d'arrêt est disponible (ou, je pense de manière équivalente, l'hyper-calcul). Cependant, appliquer l'argument qui montre que le problème d'arrêt est impossible pour une machine Turing montre également qu'il est impossible pour un...

Donc, étant donné deux DFA, le problème de trouver s'ils génèrent la même langue est-il un problème décidable? Je sais déjà que l'égalité de deux LFC n'est pas décidable mais qu'en est-il de l'égalité de deux DFA? étant donné que la plupart des problèmes avec les DFA sont décidables, est-ce...

L'existence de problèmes indécidables implique-t-elle immédiatement la non-prévisibilité des systèmes physiques? Considérons le problème de l'arrêt, d'abord nous construisons un UTM physique, disons en utilisant la construction basée sur un circuit habituel. Il ne peut alors y avoir aucune théorie...

OK, voici donc une question d'un test passé dans ma classe de théorie du calcul: Un état inutile dans une MT est celui qui n'est jamais entré dans une chaîne d'entrée. Laissez Prouver que U S E L E S S T M est indécidable.U S E L E S ST M= { ⟨ M, q⟩ ∣ q est un état inutile dans  M}...

Y at - il un besoin pour être infini indécidable?L⊆Σ∗L⊆Σ∗L\subseteq \Sigma^* Je veux dire que si nous choisissons une langue être une version finie bornée de , c'est-à-dire , ( ), avec . Est-il possible que soit un langage indécidable? L ⊆ Σ ∗ | L ′ | ≤ N N ∈ N L ′ ⊂ L L ′L′L′L' L⊆Σ∗L⊆Σ∗L\subseteq...

J'obtiens la preuve de passer d'un énumérateur à une machine de Turing (continuez à exécuter l'énumérateur et voyez si cela correspond à l'entrée) mais je ne vois pas comment fonctionne l'autre sens. Selon mes notes et le livre (Intro to the Theory of Computation - Sipser), pour obtenir...

J'ai essayé de déterminer si le problème d'arrêt est décidable pour les automates cellulaires unidimensionnels à 3 symboles. Définition Soit f(w,i)f(w,i)f(w,i) la configuration du système au pas de temps . Plus formellement , où est l'alphabet.iiif:A∗×N→A∗f:A∗×N→A∗f:A^*\times \mathbb{N} \to A^*AAA...

J'ai appris aujourd'hui que l'analyse d'algorithme diffère en fonction du modèle de calcul. C'est quelque chose auquel je n'ai jamais pensé ni entendu parler. Un exemple qui m'a été donné, qui l'a illustré davantage, par l'utilisateur @chi était: Par exemple, considérons la tâche: étant donné...

J'ai vu des sites Web qui prétendent «prouver» que HTML5 + CSS est Turing Complete. J'ai vu des sites Web qui prétendent «prouver» que SQL est Turing Complete. J'ai vu un tas de sites Web qui prétendent «expliquer» ce que signifie être Turing Complete. Assez! Où puis-je trouver un livre (écrit par...

Il peut être démontré que deux modèles informatiques sont co-complets si chacun peut coder un simulateur universel pour l'autre. On peut montrer que deux logiques sont co-complètes si un codage des règles d'inférences (et peut-être des axiomes si elles existent) de chacune se révèle être des...

Dans le problème de l'arrêt, nous sommes intéressés s'il existe une machine Turing qui peut dire si une machine Turing donnée s'arrête ou non sur une entrée donnée . Habituellement, la preuve commence à supposer qu'un tel existe. Ensuite, nous considérons un cas où nous restreignons à lui-même,...

J'essaie de trouver les réponses à deux questions sur la machine Universal Turing. Comment la machine Universal Turing peut-elle simuler une machine Turing si celle qui est simulée a un plus grand nombre d'états? Comment la machine Universal Turing peut-elle simuler une machine Turing si celle qui...

C'est probablement une idée stupide, mais supposons que nous ayons un ordinateur programmé pour effectuer une séquence infinie de calculs et supposons que le calcul prenne secondes pour terminer. Cet ordinateur peut alors effectuer un nombre infini de calculs en un temps limité.jeeithi^\text{th}1 /...