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