Вставлю свои 3 копейки
Задача это описания условий изменения состояния системы, описание начального состояния и целевого состояния.
Операция (метод) это способ воздействия на систему с целью изменения ее сотояния.
Алгоритм это инструкция/описание применения операций к системе в ее начальном состоянии, которая гарантированно приводит систему в целевое состояние. Специально не использую термин "последовательного применения", так как хочу что бы ничего не мешало нам говорить о паралельности исполнения нескольких последовательных инструкций.
Недетерменированным алгоритмом, можно назвать алгоритм, в котором есть хотя бы одна недетерминированная операция.
Недетерминированной операцией можно назвать операцию, результат которой не следует однозначно из определения/описания самой системы. Т.е. оператор, каким-то необяснимым, в рамках системы способом, догадывается как нужно поменять состояние системы, что бы это привело исполнение всех операторов к верному решению задачи.
Соответственно, говорить о недетерминированности алгоритма определенной сисемы, необходимо только с точки зрения ее определения. Получается, что
1. если "генератор случайных чисел" (или вообще какой то случайности) описан в рамках самой системы, то его использование в операторах не делает алгоритм недетерменированным. В противном случае, делает.
2. если "модифицируемая база знаний" включена в описание системы (т.е. детерминированный алгоритм ее модификации, а другими словами, обучение) то ее использование (т.е. решения принимаемые на основе этих знаний) в операторах не делает алгоритм недетерменированным. В противном случае, делает.
3. если система изменила свое повидение на основе каких-то внешних факторов и эти фаторы учтены в самом описании системы, то такое поведение не делает алгоритм недетерменированным. В противном случае, делает.
Кстати, частенько недетерминированным поведением метода называют поведение, которое при одних и тех же исходных данных, приводит к ошибки исполнения. Но здесь нет противоречия с моим определением. Просто такой алгоритм метода, не приводит к решению желаемой задачи, а приводит к решению какой-то другой задачи, целевое состояние которой частично совпадает с целевым состоянием желаемой задачи.
Это определение так же удовлетворяет классическому определению недетерминированного алгоритма из теории сложности.
Вот как-то так.