Alors oui, les gens ont par exemple étudié les fonctions calculables avec une machine de Turing assistée d'un oracle qui sait résoudre le problème de l'arrêt (sur les machines sans oracle).
Eh bien on s'aperçoit qu'il n'y a pas de machine avec oracle qui décide de l'arrêt des machines avec oracle. Du coup on peut continuer, et ça fait toute une hiérarchie de classes de fonctions. Bien sûr, on a plus de dispositif physique pour les calculer dès qu'on sort des machines de Turing de base.
Et les machines quantiques ne sont pas candidates pour ça, vu qu'elles sont simulables avec des machines classiques.
[^] # Re: Halting problem
Posté par arenthis . En réponse au journal Déterminer le domaine d'un programme. Évalué à 4.
Eh bien on s'aperçoit qu'il n'y a pas de machine avec oracle qui décide de l'arrêt des machines avec oracle. Du coup on peut continuer, et ça fait toute une hiérarchie de classes de fonctions. Bien sûr, on a plus de dispositif physique pour les calculer dès qu'on sort des machines de Turing de base.
Et les machines quantiques ne sont pas candidates pour ça, vu qu'elles sont simulables avec des machines classiques.