Введение

В информатике, неограниченный недетерминизм или неограниченная непредсказуемость – это свойство конкурентности, при котором время ожидания обработки запроса может неограниченно возрастать из-за разрешения конфликтов при доступе к общим ресурсам, при этом гарантируется, что запрос в конечном итоге будет обработан. Неограниченный недетерминизм стал важной проблемой при разработке денотационной семантики конкурентности и впоследствии вошел в область исследований теоретической концепции гипервычислений.

Справедливость

Обсуждение неограниченного недетерминизма часто затрагивает вопросы справедливости. Основная идея заключается в том, что все пути вычислений должны быть "справедливыми" в том смысле, что если машина бесконечно часто входит в какое-либо состояние, она должна осуществлять все возможные переходы из этого состояния. Это эквивалентно требованию, чтобы машина гарантированно выполняла запрос, если это возможно, поскольку бесконечная последовательность состояний допустима только в том случае, если нет перехода, который приводит к выполнению запроса. Эквивалентно, каждый возможный переход должен в конечном итоге произойти в бесконечном вычислении, хотя для этого может потребоваться неограниченное время. Это понятие отличается от локальной справедливости подбрасывания "справедливой" монеты, где понимается, что результат может быть орлом любое конечное число раз, хотя с увеличением числа подбрасываний это становится маловероятным. Пример роли справедливого или неограниченного недетерминизма при объединении строк был приведен Уильямом Д. Клингером в его диссертации 1981 года. Он определил "справедливое объединение" двух строк как третью строку, в которой каждый символ каждой из исходных строк должен в конечном итоге появиться. Затем он рассмотрел множество всех справедливых объединений двух строк, предполагая, что оно является монотонной функцией. Далее он утверждал, что , где – пустой поток. Теперь }, следовательно, должен быть элементом , что является противоречием. Он заключил, что:
Похоже, что справедливое объединение нельзя представить в виде недетерминированной программы потока данных, работающей с потоками.

О возможности реализации неограниченного недетерминизма

Эдсгер Дейкстра утверждал, что невозможно реализовать системы с не ограниченным недетерминизмом. По этой причине Тони Хоар предположил, что "эффективная реализация должна стремиться к разумной справедливости".

Недетерминированные автоматы

Недетерминированные машины Тьюринга обладают лишь ограниченным недетерминизмом. Точно так же, последовательные программы, содержащие охраняемые команды как единственный источник недетерминизма, также обладают ограниченным недетерминизмом. Кратко говоря, недетерминизм, основанный на выборе, ограничен. Гордон Плоткин привел доказательство в своей оригинальной работе о силовых областях:

Теперь множество начальных сегментов последовательностей выполнения заданной недетерминированной программы, начиная с заданного состояния, образует дерево. Точки ветвления соответствуют точкам выбора в программе. Поскольку в каждой точке выбора всегда существует лишь конечное число альтернатив, фактор ветвления дерева всегда конечен. То есть, дерево является конечным. Теперь лемма Кёнига утверждает, что если каждая ветвь конечного дерева конечна, то и само дерево тоже конечно. В данном случае это означает, что если каждая последовательность выполнения завершается, то существует лишь конечное число последовательностей выполнения. Следовательно, если выходное множество бесконечно, оно должно содержать [непрерывающееся вычисление].

Неограниченный недетерминизм и невычислимость

Spaan et al. утверждали, что для неограниченно недетерминированной программы возможно решить проблему останова; их алгоритм состоит из двух частей, определенных следующим образом:

Первая часть программы запрашивает натуральное число у второй части; получив его, она выполняет заданную машину Тьюринга в течение указанного числа шагов и принимает или отклоняет в зависимости от того, остановилась ли машина. Вторая часть программы недетерминированно выбирает натуральное число по запросу. Это число сохраняется в переменной, инициализированной нулем; затем программа попеременно выбирает либо увеличить значение переменной, либо обработать запрос. Условие справедливости требует, чтобы запрос был обработан в конечном итоге, иначе возникнет бесконечный цикл, в котором всегда выбирается только ветвь увеличения переменной. Очевидно, что если машина останавливается, у этого алгоритма существует путь, приводящий к принятию. Если же машина не останавливается, этот алгоритм всегда будет отклонять результат, независимо от того, какое число возвращает вторая часть программы.

Аргументы в пользу неограниченного недетерминизма

Клингер и Карл Хьюитт разработали модель (известную как модель акторов) параллельных вычислений, в которой изначально заложено свойство неограниченного недетерминизма [Клингер 1981; ; ;]. Это позволяет выполнять вычисления, которые невозможно реализовать на машинах Тьюринга, как было показано выше. Однако эти исследователи подчеркивают, что их модель параллельных вычислений, определенная Церковью, Клини, Тьюрингом и другими (см. Неопределенность в параллельных вычислениях), отличается от традиционных моделей. Хьюитт обосновал использование неограниченного недетерминизма тем, что невозможно установить предел времени, необходимого для установления состояния вычислительной схемы, называемой арбитром (см. метастабильность в электронике). Арбитры используются в компьютерах для обработки ситуаций, когда тактовые частоты компьютера работают асинхронно с внешними входными сигналами, например, с вводом с клавиатуры, доступом к диску, сетевым вводом и т. п. Таким образом, получение сообщения, отправленного компьютеру, может занять неограниченное время, в течение которого компьютер может пройти через неограниченное количество состояний. Он также утверждал, что электронная почта допускает неограниченный недетерминизм, поскольку почта может храниться на серверах неопределенно долго до доставки, а соединения с серверами в Интернете также могут быть недоступны неопределенно долго. Это послужило причиной споров об неограниченном недетерминизме.

Анализ справедливости Хьюитта

Хьюитт утверждал, что проблемы справедливости частично обусловлены глобальной точкой зрения на состояние. Старейшие модели вычислений (например, машины Тьюринга, постпродукции, лямбда-исчисление и т. д.) основаны на математике, использующей глобальное состояние для представления вычислительного шага. Каждый вычислительный шаг представляет собой переход из одного глобального состояния вычисления в следующее. Подход, основанный на глобальном состоянии, был продолжен в теории автоматов для конечных автоматов и автоматов с памятью (стековых машин), включая их недетерминированные версии. Все эти модели обладают свойством ограниченного недетерминизма: если машина всегда останавливается при запуске из начального состояния, то существует предел количества состояний, в которых она может остановиться. Хьюитт утверждал, что существует принципиальная разница между выбором при недетерминизме глобального состояния и неопределенностью порядка поступления сообщений (недетерминизмом) в его модели акторов. В недетерминизме глобального состояния "выбор" делается в пользу "следующего" глобального состояния. При неопределенности порядка поступления сообщений арбитраж локально определяет порядок обработки каждого сообщения в неограниченный промежуток времени. Пока локальный арбитраж продолжается, неограниченная активность может происходить в других местах. Глобального состояния нет, и, следовательно, нет "выбора" относительно "следующего" глобального состояния.