Il existe des temps spatiaux relativistes (par exemple des temps spatiaux MH; voir Hogarth 1994) où une ligne du monde de durée infinie peut être contenue dans le passé d'un observateur fini. Cela signifie qu'un observateur normal peut avoir accès à un nombre infini d'étapes de calcul. En supposant...
Je sais que les portes NAND peuvent être utilisées pour créer des circuits qui implémentent chaque table de vérité, et les ordinateurs modernes sont constitués de portes NAND. Quel est le lien théorique entre les portes NAND et l'exhaustivité de Turing? Il me semble que les circuits de porte NAND...
J'ai ces questions d'un ancien examen que j'essaie de résoudre. Pour chaque problème, l'entrée est un codage d' une certaine machine de Turing MMM . Pour un entier c>1c>1c>1 , et les trois problèmes suivants: Est-il vrai que pour chaque entrée , M ne passe pas le | x | + c position lors de...
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...
J'essaie de comprendre l'existence de langues non reconnaissables. Pour cela, j'ai besoin de savoir pourquoi une machine Turing ne reconnaît qu'une seule langue, pas plusieurs. Pourquoi
Je suis en quelque sorte nouveau, mais très intéressé par le domaine de l'informatique et de la théorie de la complexité, et je veux clarifier ma compréhension de la façon de classer les problèmes et de la façon dont les problèmes sont liés à la machine utilisée pour les résoudre. Ma compréhension...
Contexte: Je suis un profane complet en informatique. Je lisais sur les chiffres de Castor occupé ici , et j'ai trouvé le passage suivant: L'humanité peut ne jamais connaître la valeur de BB (6) avec certitude, sans parler de celle de BB (7) ou d'un nombre supérieur dans la séquence. En effet, déjà...
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...
Voici le problème: Prouvez que les machines de Turing à bande unique qui ne peuvent pas écrire sur la partie de la bande contenant la chaîne d'entrée ne reconnaissent que les langues normales. Mon idée est de prouver que cette MT particulière est équivalente à un DFA. L'utilisation de cette MT pour...
Les définitions des machines de Turing indiquent toujours explicitement que le symbole vide ne fait pas partie de l'alphabet saisi. Je me demande ce qui ne va pas quand vous le ferez partie de l'alphabet d'entrée, car effectivement le symbole vide semble déjà faire partie de l'entrée. Pour...
Quelles sont les différences entre les machines de Turing déterministes et non déterministes? Modèles différents mais équivalents de NDTM. En particulier, quelle est cette expression fréquemment utilisée "devinez de façon non déterministe"? Comment l'utiliser correctement et exemples d'utilisation...
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...
J'ai vu des machines de turing être représentées avec des bandes infinies dans une et dans deux directions. Y a-t-il une différence dans la puissance de ces machines de turing, ou sont-elles fondamentalement équivalentes? Dans ma tête, je pense qu'ils sont équivalents, car je suppose qu'il doit y...
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 lu plusieurs fois qu'il n'est pas possible de retourner la réponse d'un NDTM efficacement. Cependant, je ne comprends pas pourquoi. Par exemple, étant donné un MTND qui fonctionne en O ( n ) , ce texte (section 3.3) indique qu'il ne sait pas comment une autre MTND T peut déterminer dans O ( n...
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
Je me suis demandé pourquoi la bande / les bandes ne font pas partie de la définition formelle d'une machine de Turing. Considérons, par exemple, la définition formelle d'une machine de Turing sur la page Wikipedia . La définition, après Hopcroft et Ullman, comprend: l'ensemble fini d'états , l'...
Je lis Sipser et j'ai du mal à comprendre quel est le processus de sorte que si vous me donnez des machines k Turing avec k bandes, je peux cracher une machine Turing équivalente avec une seule bande. Un exemple serait bien. En fait, un exemple élaboré qui montre comment passer d'une MT qui a...
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...