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...
Existe-t-il une machine de Turing qui s'arrête sur toutes les entrées mais cette propriété n'est pas prouvable pour une raison quelconque? Je me demande si cette question a été étudiée. Remarque: «non démontrable» pourrait signifier un système de preuve «limité» (qui au sens faible pense que la...
Je commence à lire un livre sur la complexité informatique et les machines de Turing. Voici une citation: Un algorithme (c'est-à-dire une machine) peut être représenté comme une chaîne de bits une fois que nous avons décidé d'un codage canonique. Cette affirmation est fournie comme un simple fait,...
Dans cette question, nous considérons uniquement les machines Turing qui s'arrêtent sur toutes les entrées. Si k∈Nk∈Nk \in \mathbb{N} alors par TkTkT_k on désigne la machine de Turing dont le code est kkk . Considérez la fonction suivante
Étant donné les langues AAA et BBB , disons que leur concaténation ABABAB est sans ambiguïté si pour tous les mots w∈ABw∈ABw \in AB , il y a exactement une décomposition w=abw=abw = ab avec a∈Aa∈Aa \in A et b∈Bb∈Bb \in B , et ambiguë sinon. (Je ne sais pas s'il existe un terme établi pour cette...
Notez qu'il s'agit d'une question liée à l'étude dans un cours de CS dans une université, ce n'est PAS des devoirs et peut être trouvé ici sous l'examen d'automne 20112. Voici les deux questions que je regarde d'un examen passé. Ils semblent être liés, le premier: Laisser FINITECFG={<G>∣G is...
Le problème de savoir si deux automates déroulants reconnaissent la même langue est indécidable. Le problème de savoir si un automate pushdown reconnaît la langue vide est décidable, d'où il est également décidable s'il reconnaît une langue finie donnée. Il est indécidable que la langue acceptée...
Il n'y a pas de solution analytique générale au problème des n-corps qui puisse produire une fonction analytique qui peut être utilisée pour donner l'état d'un système à n-corps à un temps arbitraire t avec une précision exacte. Cependant, il existe certains cas particuliers de systèmes à n corps...
J'utilise un ordinateur numérique pour écrire ce message. Une telle machine a une propriété qui, si vous y réfléchissez, est en fait assez remarquable: c'est une machine qui, si elle est programmée de manière appropriée, peut effectuer tout calcul possible . Bien sûr, les machines à calculer d'un...
Les machines de comptage avec deux compteurs ou plus sont généralement équivalentes aux machines de Turing dans les cours sur la théorie du calcul. Cependant, je n'ai pas vu d'analyse formelle des langues pouvant être reconnues par une machine à guichet unique. Ces langues sont-elles équivalentes...
Existe-t-il des propriétés indécidables des automates linéaires bornés (en évitant l'astuce de la langue vide)? Et pour un automate fini déterministe? (mettre de côté l'intraçabilité). J'aimerais obtenir un exemple (si possible) d'un problème indécidable défini sans utiliser de machines Turing...
Dans une conférence, un professeur a mentionné que les ordinateurs modernes n'ont pas autant de puissance de calcul qu'une machine Turing parce qu'ils n'ont pas de mémoire infinie, et comme aucun ordinateur ne peut avoir une mémoire infinie, la machine Turing est donc inaccessible et représente...
Un ensemble est dénombrable s'il a une bijection avec les nombres naturels et est numériquement calculable (ce) s'il existe un algorithme qui énumère ses membres. Tout ensemble non finissable pouvant être énuméré doit être dénombrable puisque nous pouvons construire une bijection à partir de...
Étant donné un langage , définissez l'ensemble de longueur de comme l'ensemble de longueurs de mots dans : L L L S ( L ) = { | u |LLLLLLLLLL S (L)={ | u | ∣u∈L}LS(L)={|u|∣u∈L}\mathrm{LS}(L) = \{|u| \mid u \in L \} Quels ensembles d'entiers peuvent être l'ensemble de longueurs d'une langue...
Je me demande comment ça se fait que la langue suivante est dans .RR\mathrm R LM1= { ⟨ M2⟩∣∣M2 est un TM, et L ( M1) = L ( M2) , Et | ⟨ M1⟩ | > | ⟨ M2⟩ | }LM1={⟨M2⟩|M2 est une MT, et L(M1)=L(M2), et |⟨M1⟩|>|⟨M2⟩|}L_{M_1}=\Bigl\{\langle M_2\rangle \;\Big|\;\; M_2 \text{ is a TM, and }...
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...
Je veux savoir si le problème suivant est décidable: Instance: un NFA A avec n états Question: Existe-t-il un nombre premier p tel que A accepte une chaîne de longueur p. Ma conviction est que ce problème est indécidable, mais je ne peux pas le prouver. Le décideur peut facilement avoir un...
Des langues telles que sont RE-complètes sous plusieurs réductions. Il est trivial de voir que co-RE a aussi des problèmes complets. S. Schmitz [1] considère certaines classes entre ELEM et REC . Ils présentent des problèmes complets pour ces classes dans le cadre de réductions spécialement...
Je cherchais des problèmes ouverts intéressants et faciles à énoncer en calculabilité (compréhensibles par les étudiants de premier cycle prenant leur premier cours en calculabilité) pour donner des exemples de problèmes ouverts (et, évidemment, je veux que les étudiants puissent comprendre le...
Si est en fait égal à , comment cela améliorerait-il nos algorithmes pour factoriser les entiers plus rapidement. En d'autres termes, quel genre d'information cela nous donnerait-il pour mieux comprendre la factorisation des nombres entiers?PP{\sf P}NPNP{\sf