On sait que la langue des mots contenant un nombre égal de 0 et 1 n'est pas régulière, tandis que la langue des mots contenant un nombre égal de 001 et 100 est régulière ( voir ici ). Étant donné deux mots w1,w2w1,w2w_1,w_2 , est-il décidable si la langue des mots contenant un nombre égal de...
Je me demande si décider de la décidabilité du problème est un problème décidable. Je suppose que non, mais après des recherches initiales, je ne trouve aucune documentation sur ce
J'ai lu dans Wikipedia et dans quelques autres textes Le problème d'arrêt est décidable [...] pour les automates linéaires bornés (LBA) et les machines déterministes à mémoire finie. Mais plus tôt, il est écrit que le problème d'arrêt est un problème indécidable et donc TM ne peut pas le résoudre!...
Beaucoup de problèmes indécidables «célèbres» sont néanmoins au moins semi-décidables, leur complément étant indécidable. Un exemple par-dessus tout peut être le problème de l'arrêt et son complément. Cependant, quelqu'un peut-il me donner un exemple dans lequel un problème et son complément sont...
Je parcourais la définition de Wikipedia du langage contextuel et j'ai trouvé ceci: Chaque catégorie de langues est un sous-ensemble approprié de la catégorie directement au-dessus. Tout automate et toute grammaire dans chaque catégorie a un automate ou une grammaire équivalent dans la catégorie...
Je lisais une réponse à une question récente, et une sorte de pensée étrange et éphémère m'est venue à l'esprit. Ma demande pourrait trahir soit que mes côtelettes théoriques manquent sérieusement (surtout vrai) ou qu'il est tout simplement trop tôt pour moi de lire ce site. Maintenant, avec l'avis...
Existe-t-il des langages indécidables tels que leur union / intersection / langage concaténé est décidable? Quelle est l'interprétation physique d'un tel exemple car en général, les langages indécidables ne sont pas fermés sous ces opérations? Que dire de la fermeture de Kleene? En avons-nous aussi...
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...
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...
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...
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...
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...
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...
L'une des définitions d'un ensemble énumérable calculable (ce, équivalent à énumérable récursivement, équivalent à semi-décidable) est la suivante: A⊆Σ∗A⊆Σ∗A \subseteq \Sigma^* est ce ssi il y a un langage décidable (appelé vérificateur) st pour tous les ,V⊆Σ∗V⊆Σ∗V\subseteq \Sigma^*x∈Σ∗x∈Σ∗x\in...
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...
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}...
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,...
Accepter signifie-t-il que le TM lira et reconnaîtra un caractère de la cellule dans laquelle il lit actuellement? Et est-ce le cas qu'un TM s'arrête si l'entrée est
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...
Supposons que j'ai deux fonctions et et je souhaite déterminer siGFFFggG F( x ) = ∫G ( x ) dx .F(X)=∫g(X)réX.F(x) = \int G(x)dx. Supposons que mes fonctions soient composées de fonctions élémentaires (polynômes, exponentielles, logs et fonctions trigonométriques), mais pas, disons, série Taylor. Ce...