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

[AlexDem]

На всякий случай: в рассуждении я предполагал, что все ветви ведут к какому-то решению, в противном случае мы их вообще не могли бы считать конечными, пусть и неограниченными. Так что каждая ветвь дерева имеет лист, но мы не можем ограничить её длину... Хорошо, когда неограниченная, но конечная ветвь одна - очевидно, что алгоритм достигнет решения за конечное число шагов (что и делает НМТ). У нас же ветвей много, как и номеров - $\aleph_0$ (причём мы не знаем априори, что все они конечны, часть ведь могут циклиться). Можно ли среди них найти хотя бы один путь к решению за конечное число шагов? Я не понимаю, откуда это следует.

Если есть оракул, то это аналог поиска в глубину, от которого отказались. Если добавить хотя бы одну ветку, которая циклится, то у нас нет такого оракула-предсказателя, который смог бы предотвратить попадание в эту ветку.

[whitefox]

Вот такая аналогия.
Дерево -- незнакомый нам город, где мы знаем только центральную площадь (корень).
Узлы дерева -- перекрёстки.
Лист -- место куда мы хотим попасть.
На площади стоит оракул у которого мы спрашиваем дорогу.
Он даёт нам схему движения (номер) типа -- на первом перекрёстке направо, на втором налево и т.д.
И мы движемся по этой схеме. Если пришли в нужное место (лист), то на этом всё. А если оракул подсунул нам липу, то мы возвращаемся на площадь. Даём ему по мозгам, берём новую схему и начинаем всё сначала.

[AlexDem]

В принципе, раз каждый лист у нас имеет номер, то рано или поздно мы его перебором найдём. Пожалуй, понятно, спасибо

[whitefox]

На здоровье.