Por que não são distribuídos computação e / ou GPU considerado máquinas de Turing não determinantes se puderem executar vários trabalhos de uma só vez?

Question

Então, sabemos que uma máquina de Turing não-interminista (NTM) é apenas um modelo teórico de computação.Eles são usados em experimentos de pensamento para examinar as habilidades e limitações de computadores.Comumente usado para dickuss p vs np, e como os problemas de NP não podem ser resolvidos em tempo polinomial, a menos que o cálculo tenha sido feito no NTM hipotético. Também sabemos que um NTM usaria um conjunto de regras para prescrever mais de uma ação a ser realizada para qualquer situação.Em outras palavras, tente muitas opções diferentes simultaneamente.

Não é isso que a computação distribuída faz o hardware de commodities?Execute muitos cálculos possíveis diferentes em paralelo?E a GPU, faz isso dentro de uma única máquina.Por que isso não é considerado um NTM?

Answer 1

Na computação paralela, os encadeamentos podem falar uns com os outros e trocar informações durante o cálculo.No nonderminismo, a única "comunicação" entre os fios é que compuamos os ou de todos os possíveis caminhos de computação.Isso é muito mais limitado.

Se você simular o não-interminismo desovando cálculos paralelos para cada escolha não-interminística, você precisa de um número exponencial de tópicos para uma computação em tempo polinômio.Sabemos como construir máquinas paralelas no mundo real, não sabemos como construir não-nonderministas.