Lors du développement d'algorithmes en informatique quantique, j'ai remarqué qu'il existe deux modèles principaux dans lesquels cela se fait. Certains algorithmes - comme pour le problème de l'arbre NAND hamiltonien (Farhi, Goldstone, Guttman) - fonctionnent en concevant un hamiltonien et un état...
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
La littérature est assez claire sur le fait que les RAM à coût unitaire avec multiplication primitive sont déraisonnables, dans la mesure où elles ne peut pas être simulé par les machines de Turing en temps polynomial peut résoudre des problèmes PSPACE complets en temps polynomial Cependant, toutes...
Si nous avons un programme informatique arbitraire qui peut modifier ses instructions, est-il possible de simuler ce programme avec un programme qui ne peut pas modifier ses instructions? Éditer: Je suis nouveau sur stackexchange, donc je ne sais pas si je suis autorisé à poser une NOUVELLE...
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'...
Un algorithme de machine de Turing à temps polynomial est considéré comme efficace si son temps d'exécution, dans le pire des cas, est limité par une fonction polynomiale dans la taille d'entrée. Je connais la forte thèse de Church-Turing: Tout modèle raisonnable de calcul peut être simulé...
J'avais l'impression que nos ordinateurs, étant finis, ne sont finalement pas plus puissants que les machines à états finis (extraordinairement grandes). Cependant, les machines de Turing linéairement délimitées sont également finies, mais il semble que les langues régulières soient strictement un...
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 /...
Dans l'analyse d'algorithmes, nous supposons une machine d'accès aléatoire (RAM) à un processeur générique. Pour autant que je sache, la machine RAM n'est pas plus efficace que la machine Turing. Tous les algorithmes peuvent être implémentés dans la machine de Turing. Mes questions sont donc: Si la...
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'aimerais citer Nielsen & Chuang, Quantum Computation and Quantum Information, édition du 10e anniversaire, page 5 (c'est moi qui souligne): Une classe de défis à la forte thèse de Church-Turing vient du domaine du calcul analogique. Au cours des années qui se sont écoulées depuis Turing, de...
Soit une chaîne d'entrée donnée comme . Ensuite, si un NFA est actuellement dans l'état (et a lu l'entrée jusqu'à l'alphabet ), puis avant de lire le symbole d'entrée suivant, le NFA se divise en deux NFA, l'un étant dans l'état r et l'autre dans s , s'il y a une transition de le type r \...
Il s'agit d'une suite d'une autre question ici , et j'espère que ce n'est pas trop philosophique. Comme Raphael l'a souligné dans un commentaire sur ma question précédente, je n'ai pas vraiment la définition de "calculable", mais selon certains articles que j'ai lus, la définition n'est pas...
À ma connaissance, il n'existe pas d' algorithme pire des cas qui résout le problème suivant:O( n )O(n)O(n) Étant donné une séquence de longueur composée d'entiers finis, trouvez la permutation où chaque élément est inférieur ou égal à son successeur.nnn Mais existe-t-il une preuve de son...
Dans une question précédente Qu'est-ce qu'un algorithme exactement? , J'ai demandé si avoir un "algorithme" qui renvoie la valeur d'une fonction basée sur un tableau de valeurs précalculées était un algorithme. L'une des réponses qui a retenu mon attention est celle-ci: L'exemple factoriel entre...
J'essaie de relier les circuits logiques multinationaux (ordinateurs basés uniquement sur des portes logiques) avec tout ce que j'ai appris récemment dans la théorie du calcul. Je me demandais si les circuits logiques combinatoires peuvent implémenter des calculs de la même manière que les machines...
Au cours des deux dernières années, j'ai construit un ordinateur mécanique alimenté par des billes et en ai fait un jeu. Il est similaire à l'ancien Digi-Comp II, à l'exception de deux différences clés: Les pièces sont repositionnables sur la carte. Vous pouvez connecter plusieurs «bits» ensemble à...
Fermé. Cette question est hors sujet . Il n'accepte pas actuellement de réponses. Voulez-vous améliorer cette question? Mettez à jour la question afin qu'elle soit sur le sujet pour Computer Science Stack Exchange. Fermé il y a 3 ans . Les ordinateurs et les langages de programmation ont tendance...
Les machines de Turing ont un alphabet de symboles formel, une description basée sur les règles d'état et de transition de la façon dont un calcul est effectué. Le modèle d'acteur est parfois mentionné comme un modèle de calcul plus puissant que les machines de Turing (pas dans ce qu'il peut...
J'essaie d'attaquer TAOCP une fois de plus, étant donné la lourdeur littérale des volumes que j'ai du mal à m'y engager sérieusement. Dans TAOCP 1, Knuth écrit, page 8, les concepts de base: Soit un ensemble fini de lettres. Soit l'ensemble de toutes les chaînes de (l'ensemble de toutes les...