Эти тонкие различия затрудняют обращение с недетерминированными выражениями.
Для организации завершения вычислений при недетерминированном выборе введем специальное выражение failure («неуспешная попытка»), которое в некотором (недетерминированном) вычислении обозначает выражение, не доставляющее никакого «желаемого» значения (неуспех). Благодаря этому может быть промоделирована концепция вычислений, встречающаяся в недетерминированных Т-машинах.
Введением failure
определяется так называемый «бэктрекинг-недетерминизм» (недетерминированный поиск с возвратом). Недетерминированные ветви вычисления, которые ведут к failure, отсекаются, т. e. не принимаются в качестве результата. Неуспех фиксируется только в том случае, когда все ветви приводят к failure.
Использование failure (выбор по-прежнему является недетерминированным) позволяет организовать поиск в недетерминированно-выбранном дереве вычислений.
Пример (алгоритмы с недетерминированным поиском).
Сортировка недетерминированным выбором. Рассмотрим систему вычислительных предписаний
fct ndsort == ( seq nat s, seq nat r ) scq nat:
if s = e then r
else nat x == any(s);
if x > first® then failure
else ndsort(drop(s, x), <x> * r)
fi
fi
fct any = (seq nat
s) nat:
if s=e then failure
else first(s) any(rest(s))
fi
fct drop = (seq nat s, nat x) seq nat:
if s == є then failure
elif first(s) = x then rest(s)
else append(first(s), drop(rest(s), x))
fi
fct sort = ( seq nat s)
seq nat:
if s = є then s
else nat x = any(s);
ndsort(drop(s,x),<x>?є
При вызове sort(s) порождается отсортированная по неубыванию версия s.
Обратим внимание: если затраты времени простого (т.e. недетерминированного) выбора составляют z, то затраты бэктрекинг-недетерминизма в самом неблагоприятном случае имеют порядок 2^z.