Войти
В информатике, неограниченный недетерминизм или неограниченная неопределенность - это свойство concurrency, с помощью которого величина задержки в обслуживании запроса может стать неограниченной в результате арбитража конкуренции за совместно используемые ресурсы, при этом гарантируя, что запрос в конечном итоге будет обслужен. Неограниченный недетерминизм стал важной проблемой в развитии денотационной семантики параллелизма, а позже стал частью исследования теоретической концепции гиперкомпьютера.
Обсуждение неограниченного недетерминизма имеет тенденцию вовлекаться в обсуждение справедливости. Основная концепция состоит в том, что все пути вычислений должны быть «справедливыми» в том смысле, что если машина входит в состояние бесконечно часто, она должна принимать все возможные переходы из этого состояния. Это равносильно требованию того, чтобы машина гарантированно обслуживала запрос, если это возможно, поскольку бесконечная последовательность состояний будет разрешена только в том случае, если нет перехода, который приводит к обслуживанию запроса. Точно так же каждый возможный переход должен в конечном итоге произойти в бесконечном вычислении, хотя переход может занять неограниченное количество времени. Эту концепцию следует отличать от местной справедливости подбрасывания "справедливой" монеты, которая подразумевает, что для любого конечного числа шагов результат всегда может быть орлом, хотя по мере увеличения числа шагов это почти наверняка не произойдет.
Пример роли справедливого или неограниченного недетерминизма в слиянии строк был приведен Уильямом Д. Клингером в его диссертации 1981 года. Он определил «справедливое слияние» двух строк как третью строку, в которой в конечном итоге должен появиться каждый символ каждой строки. Затем он рассмотрел набор всех справедливых слияний двух слияний строк (S, T), предполагая, что это монотонная функция. Затем он утверждал, что merge (⊥, 1) ⊆ merge (0,1), где ⊥ - пустой поток. Теперь merge (⊥, 1) = {1}, поэтому должно быть, что 1 является элементом merge (0,1), противоречие. Он пришел к выводу, что:
Эдсгер Дейкстра [1976] утверждал, что невозможно реализовать системы с неограниченным недетерминизмом. По этой причине Тони Хоар [1978] предположил, что «эффективная реализация должна быть разумно справедливой».
Недетерминированные машины Тьюринга обладают только ограниченным недетерминизмом. Точно так же последовательные программы, содержащие охраняемые команды в качестве единственного источника недетерминизма, имеют только ограниченный недетерминизм (Эдсгер Дейкстра [1976]). Вкратце, недетерминизм выбора ограничен. Гордон Плоткин представил доказательство в своей оригинальной статье 1976 года о степенных областях:
Уильям Клингер [1981] представил следующий анализ приведенного выше доказательства Плоткина :
Spaan et al. [1989] утверждали, что неограниченно недетерминированная программа может решить проблему остановки ; их алгоритм состоит из двух частей, определяемых следующим образом:
Первая часть программы запрашивает натуральное число из второй части; после его получения он будет перебирать желаемую машину Тьюринга для этого количества шагов и принимать или отклонять в зависимости от того, остановилась ли машина.
Вторая часть программы недетерминированно выбирает натуральное число по запросу. Число хранится в переменной, которая инициализируется 0; затем программа неоднократно выбирает, увеличивать ли переменную на единицу или обслуживать запрос. Ограничение равноправия требует, чтобы запрос в конечном итоге был обслужен, поскольку в противном случае существует бесконечный цикл, в котором когда-либо берется только ветвь «увеличить переменную».
Очевидно, что если машина действительно останавливается, у этого алгоритма есть путь, который принимает. Если машина не останавливается, этот алгоритм всегда будет отклонять, независимо от того, какое число вернет вторая часть программы.
Клинджер и Карл Хьюитт разработали модель (известную как модель актера ) параллельных вычислений с свойство неограниченного недетерминизма, заложенное в [Clinger 1981; Hewitt 1985; Хьюитт и Ага 1991; Hewitt 2006b]; это позволяет выполнять вычисления, которые не могут быть реализованы машинами Тьюринга, как показано выше. Однако эти исследователи подчеркивают, что их модель параллельных вычислений не может реализовать какие-либо функции, которые не входят в класс рекурсивных функций, определенных Черчем, Клини, Тьюрингом и т. Д. (См. Неопределенность в параллельных вычислениях.)
Хьюитт [2006] оправдал свое использование неограниченного недетерминизма, утверждая, что нет никаких ограничений, которые могут быть наложены на то, сколько времени требуется вычислительной схеме, называемой арбитром, для урегулирования ( см. метастабильность в электронике ). Арбитры используются в компьютерах, чтобы иметь дело с обстоятельствами, когда компьютерные часы работают асинхронно с вводом извне, например, ввод с клавиатуры, доступ к диску, ввод сети и т. Д. Таким образом, сообщение, отправленное на компьютер, может занять неограниченное время. полученный, а компьютер тем временем мог пройти неограниченное количество состояний.
Он также утверждал, что электронная почта допускает неограниченный недетерминизм, поскольку почта может храниться на серверах неограниченное время до доставки, и что данные связываются с серверами в Интернете также может не работать на неопределенный срок. Это привело к спору о неограниченном недетерминизме..
Хьюитт утверждал, что вопросы справедливости частично проистекают из точки зрения глобального состояния. Самые старые модели вычислений (например, машины Тьюринга, постановки Поста, лямбда-исчисление и т. Д.) Основаны на математике, которая использует глобальное состояние для представления вычислительного шага. Каждый шаг вычислений - это переход от одного глобального состояния вычисления к следующему глобальному состоянию. Подход глобального состояния был продолжен в теории автоматов для машин с конечным числом состояний и машин с выталкиванием вниз, включая их недетерминированные версии. Все эти модели обладают свойством ограниченного недетерминизма: если машина всегда останавливается при запуске в своем начальном состоянии, то существует ограничение на количество состояний, в которых она может остановиться.
Хьюитт утверждал, что существует фундаментальная разница между выбором в недетерминизме глобального состояния и неопределенностью (недетерминизмом) порядка прибытия его модели актера. В недетерминизме глобального состояния делается «выбор» для «следующего» глобального состояния. В случае неопределенности порядка прибытия арбитраж принимает решение о каждом порядке прибытия локально в неограниченный промежуток времени. Пока продолжается местный арбитраж, неограниченная деятельность может иметь место в другом месте. Нет глобального состояния и, следовательно, нет «выбора» в отношении «следующего» глобального состояния.
