Machines théoriques plus puissantes que les machines de Turing

Existe-t-il des machines théoriques dépassant les capacités des machines de Turing dans au moins certaines zones?

La thèse de Church-Turing (dans une formulation) affirme que tout ce qui peut être physiquement calculable peut également être calculé sur une machine de Turing. En supposant que vous croyiez en cette thèse et que vous vous intéressez aux fonctions que de telles machines pourraient calculer (et non pas, par exemple, au calcul interactif), aucun hyper-calcul n'est possible.

La thèse de Church-Turing ne porte que sur ce qui est calculable, mais pas sur l'efficacité du calcul. On sait que les machines de Turing ne sont pas aussi efficaces, bien qu’elles simulent polynomialement des ordinateurs classiques. Les ordinateurs quantiques sont supposés être exponentiellement plus efficaces que les machines de Turing. En ce sens, vous pouvez battre les machines de Turing (si vous pouviez seulement construire un ordinateur quantique évolutif).

Scott Aaronson a probablement plus à dire à ce sujet - je vous laisse le vérifier vous-même.

Oui, il existe des machines théoriques dépassant les machines de Turing en termes de puissance de calcul, telles que les machines Oracle et les machines de Turing à temps infini . Le mot à la mode que vous devriez transmettre à Google est l' hypercalcul .

La thèse de Church-Turing n'a pas besoin d'être considérée comme un article de foi; il est probablement plus logique de le considérer comme énonçant une description, une définition de ce que nous entendons par le terme "calcul", et il s’agit également d’une notion assez étroite de calcul: le calcul par un seul processeur exécutant des étapes strictement séquentielles sans connexion externe. ingérence. Certains aspects du calcul sur lesquels nous devons raisonner ne sont pas couverts par cette notion, et de nombreux éléments supplémentaires de la théorie mathématique ont été développés en informatique pour répondre à de telles préoccupations.

La thèse de Church-Turing n'est donc pas une caractéristique déterminante de notre univers, mais bien une caractéristique particulière d'une manière particulière de faire certaines choses dans notre univers.

À cet égard, elle peut être assimilée à la géométrie euclidienne. Notre univers est-il intrinsèquement euclidien? Pourquoi nos méthodes de mesure des terres sont-elles limitées par ses principes? Ne pouvons-nous pas avoir une hypergéométrie permettant une mesure plus puissante des terres? La réponse est: nous pouvons et nous le faisons, mais nous n’appelons pas toujours les résultats «mesure du sol» ou «géométrie».

De même, notre théorie et notre pratique en matière de calcul vont au-delà de ce que les machines de Turing peuvent décrire (par exemple, il existe des calculs de processus pour décrire des systèmes concurrents), mais nous n’appelons pas nécessairement ces extensions «calcul».

Une des faiblesses théoriques d’une machine de Turing est sa prévisibilité. Un adversaire tout-puissant et omniscient pourrait exploiter cette faiblesse en jouant à un jeu contre la machine de Turing. Donc, si une machine théorique avait accès à une source aléatoire que son adversaire ne pouvait pas prédire (et pouvait cacher son état interne à son adversaire), cette machine théorique serait alors plus puissante qu'une machine de Turing.

Le problème de ce type de machine théorique dans la vie réelle n’est pas de savoir si la source aléatoire est parfaitement aléatoire ou non (en supposant qu’elle soit parfaitement aléatoire est une idéalisation inoffensive), Etat de notre adversaire. Donc, dans le cas concret, on ne peut jamais être sûr qu'il soit valide d'idéaliser l'instance actuelle d'une situation par une telle machine. Ce n'est que légèrement mieux que la situation pour la plupart des types d'hypercalcul, où il m'est difficile de savoir quelles situations idéalisées devraient être modélisées par celles-ci (j'ai déjà répondu: j'ai donc besoin d'un type de machine miracle omniscient pour résoudre "RE", Je ne savais pas que de telles machines existent. )

$\Pi_2^0$ Cette excuse elle-même est née d’une conversation avec un autre Thomas, à savoir Thomas Chust.)