Discuter:Machine de Turing non déterministe

Un article de Wikipédia, l'encyclopédie libre.

N'étant pas vraiment spécialiste ni de physique ni d'algorithmique, je m'interroge sur la(les) corrélation(s) qu'il peut exister entre le concept de "Machine de Turning non-déterministe" et d'"Ordinateur Quantique".

- Il me semble que l'article sur la machine de Turning ND précise qu'il est impossible d'en construire une : "Cette description permet facilement de voir qu'une vraie machine de Turing non-déterministe, qui peut effectuer un nombre illimité de calculs en parallèle en autant de temps qu'il en faudrait pour résoudre un seul calcul n'est pas constructible dans le monde réel (nous ne pouvons construire que des machines de Turing déterministes).[...]"

- Alors que celui sur l'ordinateur quantique précise que "La logique des ordinateurs quantiques permet de nouvelles opérations que n'autorise pas la logique classique. De nouveaux algorithmes tirant parti de ces possibilités ont ainsi été imaginés pour les ordinateurs quantiques. Le gain en complexité algorithmique est le stimulant principal des recherches dans ce domaine."

Peut-être que l'ordianteur quantique n'est-il qu'un sous-ensemble des machines de turning non-deterministes ???

Est-ce que je fais fausse route ?

Th. Labbé