Perché non sono distribuiti in calcolo e / o GPU considerati macchine di Turing non deterministiche se possono eseguire più lavori contemporaneamente?

Question

Quindi conosciamo che una macchina di tentazione nonerministica (NTM) è solo un modello teorico di calcolo.Sono usati negli esperimenti di pensiero per esaminare le abilità e le limitazioni dei computer.Comunemente usato per Dicuss P VS NP e come i problemi NP non possono essere risolti in tempo polinomiale a meno che il calcolo non fosse stato fatto sull'ipotetico NTM. Sappiamo anche che un NTM avrebbe usato una serie di regole per prescrivere più di un'azione da eseguire per qualsiasi situazione.In altre parole, tentare contemporaneamente molte opzioni diverse.

Non è questo ciò che il calcolo distribuito offre l'hardware della merce?Esegui molti diversi calcoli possibili in parallelo?E la GPU, lo fa all'interno di una singola macchina.Perché non è considerato un NTM?

Answer 1

In parallelo computing, i fili possono parlare tra loro e scambiare informazioni durante il calcolo.In nonterminismo, l'unica "comunicazione" tra i thread è che calcolo o di tutti i possibili percorsi di calcolo.Questo è molto più limitato.

Se simulta il nonderminismo con i calcoli paralleli di vaga per ogni scelta nonerministica, è necessario un numero esponenziale di thread per un calcolo del tempo polinomiale.Sappiamo come costruire macchine parallele nel mondo reale, non sappiamo come costruire protesiche.