Oui et non. Le papier cité par Darkpoulp discute bien de ça.
Oui, du point de vue de la calculabilité : l'ensemble des problèmes pour lesquels il existe un algorithme qui le résout en temps fini est le même. (Et encore mieux, cet ensemble reste le même même si tu fais appel à la physique quantique : tu peux simuler un ordinateur quantique avec une machine de Turing
.)
Non, du point de vue de la complexité. Savoir qu'il existe un algorithme pour résoudre un problème en temps fini, c'est bien beau, mais ça ne nous aide pas beaucoup. Ce qu'on voudrait, c'est : 1. connaître cet algorithme et 2. que le temps d'exécution et la mémoire nécessaire ne soient pas simplement finis mais aussi raisonnables, genre inférieur à la durée de vie et à la taille de l'univers.
La théorie de la complexité tente de répondre à la question 2 en classant les problèmes en catégories et notamment :
- la catégorie P des problèmes de taille n qu'on sait résoudre en temps polynomial en n (ex. l'addition, la multiplication ou le tri),
- la catégorie NP des problèmes dont on peut vérifier la solution en temps polynomial (ex. le Sudoku),
- la catégorie PSPACE pour ceux dont on connaît un algo en espace polynomial
- EXP ceux pour lequel on connaît des algorithmes en temps exponentiel par rapport à n.
La catégorie des problèmes solubles en pratique est P. Beaucoup de problèmes intéressants sont dans NP.
On voit facilement que P ⊆ NP ⊆ PSPACE ⊆ EXP : qui peut le plus peut le moins. Il est aussi prouvé que P ≠ EXP, donc au moins une des inclusions est stricte. On pense que P ≠ NP, mais c'est une question ouverte.
Et l'analogue de "il n'existe pas plus puissant que la machine de Turing en mécanique Newtonienne" du point de vue de la complexité n'existe pas (n'est pas prouvé) à ma connaissance. On peut juste observer empiriquement que les humains ne font pas mieux que les ordinateurs sur les problèmes "difficiles" du point de vue de la théorie de la complexité, genre les Échecs ou le Go.
Et même si on arrive à répondre à la question 2, il reste la question 1 : sommes-nous assez intelligents pour savoir construire une machine aussi intelligente que nous (et qui pourrait donc réinventer une autre machine, et ainsi de suite à l'infini) ? Ou bien y a t-il de la perte en ligne ?
Ce n'est pas évident du tout : intuitivement il est plus facile de résoudre un problème (être intelligent) que d'écrire un algorithme qui sache résoudre toute la classe de problèmes similaires (construire une machine intelligente).