Une machine de Turing qui revient à un état rencontré précédemment avec sa tête de lecture / écriture sur la même cellule de la même bande exacte sera prise en boucle. Une telle machine ne s'arrête pas. Quelqu'un peut-il donner un exemple d'une machine sans arrêt qui ne boucle...
Lorsque l'on considère les modèles de calcul des machines, la hiérarchie de Chomsky est normalement caractérisée par (dans l'ordre), les automates finis, les automates déroulants, les automates liés linéaires et les machines de Turing. Pour le premier et le dernier niveau 1 (langages réguliers et...
J'ai récemment entendu une analogie intéressante qui déclare que la preuve de Turing de l'indécidabilité du problème d'arrêt est très similaire au paradoxe du barbier de Russell. Je me suis donc demandé: les mathématiciens ont finalement réussi à rendre la théorie des ensembles cohérente en passant...
Je sais ce qu'est le calcul dans un sens vague (c'est ce que font les ordinateurs), mais j'aimerais une définition plus rigoureuse. Dictionary.comLes définitions de calcul, calcul, calcul et calcul sont circulaires, donc cela n'aide pas. Wikipediadéfinit le calcul comme «tout type de calcul qui...
Considérez les problèmes de décision énoncés dans un langage formel «raisonnable». Disons des formules en arithmétique Peano d'ordre supérieur avec une variable libre comme cadre de référence, mais je suis également intéressé par d'autres modèles de calcul: équations diophantiennes, problèmes de...
Dans le livre d'Andrew W. Appel, Modern Compiler Implementation in ML , il dit au chapitre 17 que la théorie de la calculabilité montre qu'il sera toujours possible d'inventer de nouvelles transformations d'optimisation et procède pour prouver qu'un compilateur entièrement optimisé résoudra le...
Il existe de nombreuses façons de définir la complexité de Kolmogorov et, généralement, toutes ces définitions sont équivalentes jusqu'à une constante additive. C'est-à-dire que si et sont des fonctions de complexité de kolmogorov (définies via différents langages ou modèles), alors il existe une...
Je suis un étudiant diplômé suivant un cours de théorie du calcul et j'ai de la difficulté à produire du contenu une fois qu'on me le demande. Je suis en mesure de suivre le manuel (Introduction à la théorie du calcul de Michael Sipser) et les conférences; Cependant, lorsqu'on me demande de prouver...
Soit . Je dois décider si F est décidable ou récursivement énumérable. Je pense que c'est décidable, mais je ne sais pas comment le prouver.F= { ⟨ M⟩ : M est une MT qui s'arrête pour chaque entrée en 50 étapes au maximum }F={⟨M⟩:M est un TM qui s'arrête pour chaque entrée en 50 étapes au maximum}F...
J'ai lu la page wikipedia de la règle 110 dans les automates cellulaires, et je sais plus ou moins comment ils fonctionnent (un ensemble de règles décide où tracer le prochain 1 ou 0). Je viens de lire qu'ils sont complets de Turing, mais je ne peux même pas comprendre comment «programmez-vous» la...
Faut-il qu'un problème NP-hard soit calculable? Je ne pense pas, mais je ne suis pas
Existe-t-il une fonction calculable telle que:F: N → QF:N→Qf:\mathbb{N}\rightarrow \mathbb{Q} Pour toutt ∈ N : 0 ≤ f( t ) < Xt∈N:0≤F(t)<Xt\in\mathbb{N}: 0\le f(t) < X limt → ∞F( t ) = Xlimt→∞F(t)=X\lim\limits_{t\rightarrow\infty} f(t) = X Où XXX est un nombre réel non calculable. La seule...
L' ensemble Mandelbrot est une belle créature en mathématiques. Il y a beaucoup de belles images de cet ensemble créées avec une grande précision, donc évidemment cet ensemble est "calculable" dans un certain sens. Cependant, ce qui m'inquiète, c'est qu'il n'est même pas récursivement énumérable -...
Réglage: expressions régulières avec références arrières langue unaire (alphabet à 1 symbole) Le problème suivant est-il décidable dans ce paramètre: Étant donné une expression régulière avec des références arrières, définit-elle un langage régulier? Par exemple, (aa+)\1définit une langue...
Le problème de l'arrêt ne peut être résolu dans le cas général. Il est possible de trouver des règles définies qui restreignent les entrées autorisées et le problème d'arrêt peut-il être résolu pour ce cas particulier? Par exemple, il semble probable qu'un langage qui n'autorise pas les boucles,...
La mémoire est utilisée pour beaucoup de choses, si je comprends bien. Il sert de cache disque et contient les instructions des programmes, ainsi que leur pile et tas. Voici une expérience de pensée. Si l'on ne se soucie pas de la vitesse ou du temps nécessaire à un ordinateur pour effectuer le...
Une machine de Turing sans capacité d'écriture sur des cellules vierges est-elle moins puissante que la Turing standard? Je pense que la réponse est oui mais je ne suis pas en mesure de trouver un calcul qu'une machine standard de Turing peut faire mais cette machine ne le peut pas. Des...
Comment vérifiez-vous si deux algorithmes (disons, Tri par fusion et Tri naïf) renvoient le même résultat pour n'importe quelle entrée, lorsque l'ensemble de toutes les entrées est infini? Mise à jour: Merci Ben d' avoir décrit comment cela est impossible à faire algorithmiquement dans le cas...
Quelles opérations doivent être effectuées pour effectuer un calcul analogique arbitraire ? L'addition, la soustraction, la multiplication et la division seraient-elles suffisantes? De plus, quelqu'un sait-il exactement quels problèmes peuvent être traités avec le calcul analogique, mais pas avec...
Je veux savoir si le problème suivant est décidable et comment le découvrir. Chaque problème que je vois, je peux lui dire «oui» ou «non», donc la plupart des problèmes et des algorithmes sont-ils décidables sauf quelques-uns (qui sont fournis ici )? Entrée: Un graphe orienté et fini , avec et...