Machines de calcul quantique et de Turing: les machines de Turing sont-elles toujours une mesure précise?

En classe la semaine dernière, mon professeur a commenté et dit que les machines de Turing sont utilisées comme mesure / modèle standard de ce qui est calculable et constituent une base de discussion utile pour ce sujet. Elle a également déclaré que toutes les variantes des machines Turing se sont avérées équivalentes sur le plan des calculs - lues, tout aussi puissantes - les unes que les autres. W

J'ai commenté et dit hier qu'en ce qui concerne la puissance de calcul, j'ai remarqué que certaines machines de turing peuvent prendre un temps incroyablement long pour calculer quelque chose de très simple, tandis qu'une machine de turing avec plus de bandes peut calculer quelque chose dans une complexité asymptotique inférieure par rapport au nombre des étapes nécessaires.

Elle a dit qu'en ce qui concerne le discours de classe, le temps d'exécution d'un algorithme particulier sur une machine de turing ne change pas la définition de la calculabilité, ni la puissance avec laquelle nous mesurons la calculabilité. "Nous sommes préoccupés par ce qui est calculable, pas par ce qui est efficacement calculable à ce stade." Donc, peu importe si les machines de turing ont de plus en plus de bandes, et de plus en plus de bandes impliquent qu'elles peuvent calculer en moins d'étapes. D'accord, je comprends que nous nous concentrons vraiment sur ce qui EST calculable, pas sur la vitesse à laquelle nous pouvons le calculer.

Quelque chose à ce sujet me dérange, car jusqu'à présent, les algorithmes avec une complexité asymptotique temporelle et spatiale anormalement grande définissent vraiment les limites de ce qui est, je devrais dire, pratiquement calculable.

Donc, j'ai quelques questions:

1. Supposons que nous ayons un modèle pour une machine de turing quantique , cela doit être équivalent à une machine de turing "régulière", non?

Donc, la réponse à cette question, je pense, va vraiment dans le sens de la raison pour laquelle j'ai écrit ce post. La technologie de l'informatique quantique est-elle dépassée par les définitions classiques de ce qui est calculable via une machine de turing?

2. Est-ce quelque chose au-dessus de ma tête et dois-je supprimer ce message? Je ne veux pas être précoce, je n'ai tout simplement pas vu une question similaire à la mienne.

Vous mélangez la théorie de la calculabilité (également connue sous le nom de théorie de la récursivité ) et la théorie de la complexité (ou complexité informatique ). La théorie de la calculabilité est un vaste sujet mathématique qui étudie les ramifications du concept de calcul . Il ne traite pas de la complexité du calcul. Comme votre professeur le mentionne, tous les modèles de calcul (Turing-complets) sont les mêmes du point de vue de la théorie de la calculabilité. La théorie de la calculabilité, bien qu'elle soit un sujet mathématique intéressant, n'est pas un bon modèle de calcul dans le monde réel pour cette raison, comme vous le mentionnez.

La théorie de la complexité a commencé sa vie comme une tentative de résoudre ce problème. La théorie de la complexité étudie la difficulté, en termes de temps et d'espace, de calculer certains prédicats et fonctions. Du point de vue de la théorie de la complexité, tous les modèles de calcul ne sont pas identiques et les machines de Turing sont prises comme modèle de référence. Cependant, même la théorie de la complexité n'est pas très réaliste, car elle traite tous les modèles de calcul de manière polynomiale équivalente aux machines de Turing de la même manière (deux modèles sont polynomialement équivalents si un problème est résolu dans le temps et l'espace dans un modèle peut être résolu dans le temps et l'espace dans l'autre, où est la taille d'entrée etS ( n ) T ( n ) c S ( n ) c n c O ( 1 ) O ( n log n ) Ω ( n 2$T(n)$$S(n)$$T(n)^c$$S(n)^c$$n$$c$ est une constante positive). Par exemple, les machines de Turing ne sont pas de bons modèles pour de vrais ordinateurs car elles ne prennent pas en charge l'accès aléatoire (accès à un point arbitraire en mémoire dans le temps ). Bien sûr, l'accès aléatoire peut être simulé par une machine de Turing, mais la simulation peut être lente. On dit souvent que le tri peut se faire dans le temps , mais ce n'est pas le cas pour les machines de Turing, qui nécessitent probablement ou se déplacent même pour trier des entiers. Par conséquent, dans le domaine des algorithmes , d'autres modèles tels que la machine RAM remplacent les machines Turing.$O(1)$$O(n\log n)$$\Omega(n^2)$

Enfin, les ordinateurs quantiques peuvent être modélisés de plusieurs manières différentes, comme la machine de Turing quantique. Tout ce qui est calculable à l'aide d'ordinateurs quantiques l'est également à l'aide d'ordinateurs classiques, et donc du point de vue de la théorie de la calculabilité, les machines de Turing quantiques ne sont qu'un autre modèle équivalent. Cependant, les machines de Turing quantiques sont largement conjecturées pour ne pas être polynomialement équivalentes aux machines de Turing classiques: par exemple, l'affacturage et le logarithme discret sont "faciles" pour les machines de Turing quantiques (résolubles en temps polynomial), alors qu'il est conjecturé qu'ils sont "durs" pour les machines de Turing classiques (ne peut pas être résolu en temps polynomial; bien que certaines personnes pensent que l'affacturage entier pourrait être résoluble en temps polynomial). Donc, du point de vue de la théorie de la complexité, différent des machines de Turing classiques.