О понятии параллельного алгоритма

[AlexDem]

Можно ли любую параллельную программу считать алгоритмом в смысле теории алгоритмов? Ведь в общем случае не существует такой машины Тьюринга, которая вычисляла бы в точности тот же результат, что и параллельная программа просто потому, что результат параллельной программы может зависеть от порядка выполнения инструкций каждым из процессоров. Параллельная программа тогда реализует некоторое множество частично рекурсивных функций, частично рекурсивное отношение. Хотя при каждом запуске реализуется только одна функция из множества возможных. Так получается? Но это вроде бы ничего существенно не меняет в смысле применимости теории?

[whitefox]

А ещё существуют недетерминированные машины Тьюринга. Они тоже могут давать разные результаты при разных запусках.

[AlexDem]

А как доказывается эквивалентность НМТ и ДМТ?

В Википедии пишут:

Цитата:

Интуитивно кажется, что НМТ более мощные, чем ДМТ, так как они выполняют несколько возможных вычислений сразу, требуя только, чтобы хоть одно из них заканчивалось в допускающем состоянии. Однако любой язык, допускающийся НМТ, также допускается ДМТ: ДМТ может моделировать любой переход НМТ, делая многократные копии состояния, если встречается неоднозначность.

- но там дальше идёт пример, где число вариантов растёт экспоненциально. Какая же мощность множества ячеек ленты должна быть - $2^N$?

-- Сб мар 26, 2011 18:46:50 --

Хотя я вроде понял - число шагов до решения всегда конечно, поэтому здесь $2^N$ тоже конечно.

[whitefox]

AlexDem в сообщении #427710 писал(а):

- но там дальше идёт пример, где число вариантов растёт экспоненциально. Какая же мощность множества ячеек ленты должна быть - $2^N$?

Память увеличивается не более чем квадратично.

[AlexDem]

Это если возможности последовательно перебирать? Тогда можно и зациклиться где-нибудь, а НМТ решение бы нашла.

[whitefox]

При поиске в глубину -- можно и зациклиться. Но ведь можно вести поиск вширь.

[Joker_vD]

whitefox в сообщении #427744 писал(а):

Но ведь можно вести поиск вширь.

А тогда нужно экспоненциально много памяти.

[AlexDem]

Joker_vD в сообщении #427779 писал(а):

А тогда нужно экспоненциально много памяти.

Да, спасибо, уходил от компа... Ага, именно это я и имел в виду, когда писал про $2^N$. Хотя я теперь уже в конечности не уверен. $N$ хотя и конечно, но не ограниченно, а $2^N$ уже может перестать быть конечным? По аналогии с натуральным рядом, где длина записи чисел тоже не ограниченна но конечна... Впрочем, я тут как раз и сомневаюсь. А то за $N$ здесь можно принять число шагов до решения, для алгоритма оно должно быть конечным (если решение существует). Может кто подскажет как правильно.

[whitefox]

Joker_vD в сообщении #427779 писал(а):

whitefox в сообщении #427744 писал(а):

Но ведь можно вести поиск вширь.

А тогда нужно экспоненциально много памяти.

Вы имеете ввиду, что нам потребуется память для хранения дерева поиска? Но в данном случае не обязательно хранить всё дерево -- достаточно только текущую ветку. А её длина не более $N$.

[AlexDem]

whitefox, не понимаю - если поиск идёт в ширину, то что значит "текущая ветка"? При таком поиске мы должны в цикле перебирать все созданные ветки и в каждой делать по шагу. При этом все их надо где-то хранить. А если Вы имеете в виду поиск в глубину, то я не согласен считать такую ДМТ эквивалентом НМТ (выше объяснил - почему).

[whitefox]

Насчёт поиска в глубину полностью с Вами согласен. Выше я это уже отмечал.

whitefox в сообщении #427744 писал(а):

При поиске в глубину -- можно и зациклиться. Но ведь можно вести поиск вширь.

А поиск в ширину нужно организовать примерно так:

Без потери общности будем считать, что каждый внутренний узел нашего дерева вычислений имеет ровно $k$ сыновей. Перенумеруем их следующим образом:

сыновья корня получат номера от $1$ до $k$,
первый сын первого сына получит номер $1.1$, второй $1.2$, и т.д.
соответственно третий сын второго сына четвёртого сына -- $4.2.3$,
сыновья имеют номер из одного элемента, внуки из двух, правнуки из трёх и т.д.
Все номера упорядочиваем по длине, а одинаковой длины -- лексикографически.
В это порядке и осуществляем поиск, начиная каждый раз с корня.
Хранить нужно только номер очередного узла.

[AlexDem]

Вот, здесь у меня и получается следующее недоразумение. Пусть $k = 10$, тогда для нумерации сыновей можно использовать обычные натуральные числа. Длина каждого номера будет конечной, как и запись любого натурального числа. Но, как и в случае записи натурального числа, длина номеров у нас неограничена (хотя и конечна) - поскольку количество шагов до решения в определении алгоритма не ограничивается. Но это же не мешает натуральному ряду иметь мощность $\aleph_0$, почему же у нас множество номеров должно быть конечным? А если оно - бесконечно, то почему мы должны найти ответ за конечное число шагов? Ведь каждый номер - это отдельный прогон алгоритма.

[whitefox]

Вы совершенно правы -- множество номеров равномощно множеству натуральных чисел. И каждый номер даёт один прогон алгоритма. Вот только количество этих прогонов конечно, так как наша ДМТ остановится обнаружив лист.

[AlexDem]

whitefox в сообщении #428014 писал(а):

так как наша ДМТ остановится обнаружив лист.

Именно это хотелось бы видеть не посылкой, а следствием...

-- Вс мар 27, 2011 15:21:33 --

Или имеется в виду, что на каком-то номере ведь должна остановиться?

-- Вс мар 27, 2011 15:24:10 --

Хм, если остановится - то будет номер, а пока пашет - номера нет... Так что тоже не очевидно...

[whitefox]

Мы же предположили, что НМТ находит решение. Следовательно дерево вычислений имеет хотя бы один лист. Наша ДМТ просматривает сначала узлы на первом уровне дерева затем на втором и т.д. пока не наткнётся на лист. Здесь останов.
А номера это некая абстракция существующая ещё до начала прогона.
Фактически мы имеем машину с оракулом и для каждого прогона выбираем свой собственный оракул -- номер. Этот оракул будет говорить ДМТ на каждом шаге куда двигаться дальше.