Бэктрекинг-недетерминированность в языках программирования
Из прочтения настоящего информационного модуля становится очевидным, что весьма затруднительно описывать алгоритмы через машины Тьюринга. Чтобы недетерминированные алгоритмы можно было формулировать на уровне аппликативных или процедурных (императивных) языков программирования (ЯП), введем недетерминированность также и в ЯП.. При этом обратим внимание на то, что эта недетерминированность будет иная , чем в Т-машинах: недетерминированный выбор, а затем - поиск с возвратом.
Если e1 и е2 есть (детерминированные или недетерминированные) выражения одинакового типа, то запись E1 ? E2 образует (недетерминированное) выражение. Для его вычисления мы делаем недетерминированный (случайный) выбор одного из входящих в него выражений и его значение принимаем в качестве значения исходного выражения. Обратим внимание, что тем самым недетерминированное выражение в качестве результата его вычисления может иметь значение из множества возможных значений.
