¿Por qué no se distribuyen computación y / o GPU consideradas máquinas de Turing no deterministas si pueden ejecutar varios trabajos a la vez?

Question

Entonces, sabemos que una máquina de Turing no determinista (NTM) es solo un modelo teórico de computación.Se utilizan en experimentos de pensamiento para examinar las habilidades y limitaciones de las computadoras.Comúnmente utilizado para DICUSS P VS NP, y cómo los problemas NP no pueden resolverse en el tiempo polinomial a menos que el cálculo se realice en el hipotético NTM. También sabemos que un NTM usaría un conjunto de reglas para prescribir más de una acción que se realizará para cualquier situación dada.En otras palabras, intente muchas opciones diferentes simultáneamente.

¿No es esto qué computación distribuida hace entre hardware de productos básicos?Ejecutar muchos cálculos diferentes posibles en paralelo?Y la GPU, hace esto dentro de una sola máquina.¿Por qué esto no se considera un NTM?

Answer 1

En computación paralela, los hilos pueden hablar entre sí e intercambiar información durante el cálculo.En el notibinismo, la única "comunicación" entre hilos es que calculamos la o de todas las posibles caminos de computación.Esto es mucho más limitado.

Si simula el notibinismo al desmarcar cálculos paralelos para cada elección no determinista, necesita un número exponencial de hilos para un cálculo de tiempo polinomial.Sabemos cómo construir máquinas paralelas en el mundo real, no sabemos cómo construir los no determinísticos.