Почему не распространяются вычисления и / или графические процессоры не считаются не детерминированными машинами Turing, если они могут запускать несколько рабочих мест одновременно?

Question

Итак, мы знаем, что недетерминированная машина Turing (NTM) - это просто теоретическая модель вычислений.Они используются в мыслительных экспериментах для изучения способностей и ограничений компьютеров.Обычно используются для Dicuss p vs np, а как проблемы NP не могут быть решены в многочленом времени, если вычисление не было сделано на гипотетическом NTM. Мы также знаем, что NTM будет использовать набор правил, чтобы прописать более одного действия для выполнения для любой данной ситуации.Другими словами, попробуйте много разных вариантов одновременно.

Разве это не то, что распределенные вычисления делают через товарное оборудование?Беги много разных возможных расчетов параллельно?И GPU, делает это в пределах одной машины.Почему это не считается NTM?

Answer 1

В параллельных вычислениях нити могут общаться друг с другом и обмениваться информацией во время вычисления.В недетерминизме единственное «связь» между потоками заключается в том, что мы вычисляем или из всех возможных вычислений путей.Это гораздо более ограничено.

Если вы смоделируете нересторизма, нерестающие параллельные вычисления для каждого недетерминированного выбора вам нужно экспоненциальное количество потоков для полиномиального времени.Мы знаем, как построить параллельные машины в реальном мире, мы не знаем, как строить недетерминистые.