Pourquoi ne pas distribuer l'informatique et / ou le GPU considérés comme des machines de turing non déterministes si elles peuvent exécuter plusieurs emplois à la fois?

Question

Nous savons donc une machine à trouble non déterministe (NTM) n'est qu'un modèle théorique de calcul.Ils sont utilisés dans des expériences de pensée pour examiner les capacités et les limites des ordinateurs.Communément utilisé pour Dicuss p vs NP et la manière dont les problèmes NP ne peuvent pas être résolus en temps polynomial, à moins que le calcul ait été effectué sur le NTM hypothétique. Nous savons également qu'un NTM utiliserait un ensemble de règles pour prescrire plus d'une action à effectuer pour une situation donnée.En d'autres termes, tenter de nombreuses options différentes simultanément.

N'est-ce pas ce que l'informatique distribuée passe à travers le matériel de produits de base?Exécutez de nombreux calculs différents possibles en parallèle?Et le GPU, cela fait-il dans une seule machine.Pourquoi cela n'est-il pas considéré comme une NTM?

Answer 1

En calcul parallèle, les threads peuvent se parler et échanger des informations pendant le calcul.Dans le nondéterminisme, la seule "communication" entre threads est que nous calculons la ou toutes les voies de calcul possibles.Ceci est beaucoup plus limité.

Si vous simulez le nondéterminisme en accumulant des calculs parallèles pour chaque choix non déterministe, vous avez besoin d'un nombre exponentiel de threads pour un calcul de temps polynomial.Nous savons comment construire des machines parallèles dans le monde réel, nous ne savons pas comment construire des éléments non déterministes.