stringtranslate.com

Неограниченный недетерминизм

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

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

Обсуждение неограниченного недетерминизма имеет тенденцию переплетаться с дискуссиями о справедливости . Основная концепция заключается в том, что все пути вычислений должны быть «справедливыми» в том смысле, что если машина бесконечно часто входит в какое-либо состояние, она должна совершать все возможные переходы из этого состояния. Это равнозначно требованию, чтобы машина гарантированно обслуживала запрос, если может, поскольку бесконечная последовательность состояний будет разрешена только в том случае, если не существует перехода, который приводит к обслуживанию запроса. Эквивалентно, каждый возможный переход должен произойти в конечном итоге в ходе бесконечных вычислений, хотя для того, чтобы переход произошел, может потребоваться неограниченное количество времени. Эту концепцию следует отличать от локальной справедливости подбрасывания «честной» монеты, под которой понимается, что результат всегда может быть орлом для любого конечного числа шагов, хотя по мере увеличения числа шагов это почти наверняка не произойдет .

Пример роли справедливого или неограниченного недетерминизма в слиянии строк был приведен Уильямом Д. Клингером в его диссертации 1981 года. Он определил «справедливое слияние» двух строк как третью строку, в которой в конечном итоге должен появиться каждый символ каждой строки. Затем он рассмотрел множество всех справедливых слияний двух строк merge (S, T) , предполагая, что это монотонная функция. Затем он доказал, что merge (⊥,1 ω )⊆ merge (0,1 ω ) , где ⊥ — пустой поток. Теперь слияние (⊥,1 ω ) = {1 ω }, поэтому должно быть так, что 1 ω является элементом слияния (0,1 ω ) , противоречие. Он пришел к выводу, что:

Похоже, что справедливое слияние нельзя записать как недетерминированную программу управления потоками данных, работающую с потоками. [2]

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

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

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

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

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

Неопределенность против недетерминированных автоматов

Уильям Клингер представил следующий анализ приведенного выше доказательства Плоткина:

Это доказательство основано на предпосылке, что если каждый узел x некоторой бесконечной ветви может быть достигнут некоторым вычислением c , то существует вычисление c , которое посещает каждый узел x на этой ветви. ... Очевидно, что эта посылка вытекает не из логики, а скорее из интерпретации точек выбора. Эта предпосылка не работает из-за недетерминизма прибытия [при поступлении сообщений в модели Актера] из-за конечной задержки [при поступлении сообщений]. Хотя каждый узел бесконечной ветви должен лежать на ветви с пределом, сама бесконечная ветвь не обязательно должна иметь предел. Таким образом, существование бесконечной ветви не обязательно означает непрерывные вычисления. [2]

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

Спаан и др. утверждали, что неограниченно недетерминированная программа может решить проблему остановки ; их алгоритм состоит из двух частей, определяемых следующим образом: [6]

Первая часть программы запрашивает натуральное число из второй части; получив его, он выполнит итерацию желаемой машины Тьюринга на указанное количество шагов и примет или отклонит ее в зависимости от того, остановилась ли машина.

Вторая часть программы недетерминированно выбирает натуральное число по запросу. Число сохраняется в переменной, которая инициализируется значением 0; затем программа неоднократно выбирает, увеличивать ли переменную или обслуживать запрос. Ограничение справедливости требует, чтобы запрос в конечном итоге был обслужен, иначе возникает бесконечный цикл, в котором всегда выполняется только ветвь «увеличить переменную».

Очевидно, что если машина остановится, у этого алгоритма есть путь, который принимает. Если машина не остановится, этот алгоритм всегда отклонит, независимо от того, какое число вернет вторая часть программы.

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

Клингер и Карл Хьюитт [ нужна ссылка ] разработали модель (известную как модель актера ) параллельных вычислений со свойством неограниченного недетерминизма, встроенную в [Clinger 1981; [7] ; [8] ; [9] ]; это позволяет выполнять вычисления , которые не могут быть реализованы с помощью машин Тьюринга, как показано выше. Однако эти исследователи подчеркивают, что их модель параллельных вычислений не может реализовать какие-либо функции, выходящие за пределы класса рекурсивных функций [ нужна цитация ], определенных Чёрчем, Клини, Тьюрингом и т. д. (См. « Неопределённость в параллельных вычислениях »).

Хьюитт оправдал свое использование неограниченного недетерминизма, утверждая, что не существует ограничений, которые можно установить на то, сколько времени потребуется вычислительной схеме, называемой арбитром, для стабилизации (см. Метастабильность в электронике ). Арбитры используются в компьютерах для решения ситуации, когда компьютерные часы работают асинхронно с входными данными извне, например. , ввод с клавиатуры, доступ к диску, сетевой ввод и т. д. Таким образом, получение сообщения, отправленного на компьютер, может занять неограниченное время, и в то же время компьютер может проходить неограниченное количество состояний.

Он далее утверждал, что электронная почта обеспечивает неограниченный недетерминизм, поскольку почта может храниться на серверах неопределенное время, прежде чем будет доставлена, и что каналы передачи данных на серверы в Интернете также могут быть недоступными на неопределенный срок. Это привело к спорам о неограниченном недетерминизме . [10]

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

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

Хьюитт утверждал, что существует фундаментальная разница между выбором в недетерминизме глобального состояния и неопределенностью порядка прибытия (недетерминизмом) его модели Актера . В недетерминизме глобального состояния делается «выбор» в пользу «следующего» глобального состояния. При неопределенности порядка прибытия арбитраж решает каждый порядок прибытия локально в течение неограниченного периода времени. Пока идет местный арбитраж, неограниченная деятельность может иметь место в другом месте. Не существует глобального состояния и, следовательно, не существует «выбора» относительно «следующего» глобального состояния.

Рекомендации

  1. ^ Орд, Тоби (2002). «Гиперкомпьютеры: вычисления больше, чем машина Тьюринга». arXiv : math/0209332 .
  2. ^ аб Клингер, Уильям Д. (1 мая 1981 г.). Основы семантики актеров (Технический отчет AI). Массачусетский Институт Технологий. hdl : 1721.1/6935.
  3. ^ аб Дейкстра, Эдсгер (1976). Дисциплина программирования . Серия Прентис-Холла по автоматическим вычислениям. Прентис-Холл. ISBN 9780613924115.
  4. ^ Хоар, ЦАР (август 1978 г.). «Обмен последовательными процессами». Коммуникации АКМ . 21 (8): 666–677. дои : 10.1145/359576.359585 . S2CID  849342.
  5. ^ Плоткин, Гордон (сентябрь 1976 г.). «Конструкция области власти». SIAM Journal по вычислительной технике . 5 (3): 452–487. дои : 10.1137/0205035.
  6. ^ Спаан, Эдит; Торенвлит, Лин; ван Эмде Боас, Питер (февраль 1989 г.). «Недетерминизм, справедливость и фундаментальная аналогия». Бюллетень ЕАТКС . 37 : 186–193.
  7. ^ Хьюитт, Карл (апрель 1985 г.). «Проблема открытых систем». БАЙТ . МакГроу Хилл. стр. 223–242. ISSN  0360-5280.Перепечатано как Хьюитт, Карл (апрель 1990 г.). «Проблема открытых систем». В Партридже, Дерек; Уилкс, Йорик (ред.). Основы искусственного интеллекта: справочник . Издательство Кембриджского университета. стр. 383–395. ISBN 9780521359443.
  8. ^ Хьюитт, Карл ; Ага, Гюль (1988). «Языки с защищенными предложениями Хорна: являются ли они дедуктивными и логичными?». Материалы международной конференции по компьютерным системам пятого поколения . FGCS 1988. Токио, Япония: OHMSHA Ltd. Токио и Springer-Verlag. стр. 650–657. ISBN 3540195580.Также как Хьюитт, Карл ; Ага, Гюль (июнь 1991 г.). «Языки с защищенными предложениями Хорна: они дедуктивны и логичны?». В Уинстоне, Патрик Генри ; Шеллард, Сара Александра (ред.). Искусственный интеллект в Массачусетском технологическом институте: расширяя границы . МТИ Пресс. стр. 582–593. ISBN 9780262231503.
  9. ^ Хьюитт, Карл (май 2006 г.). «Что такое приверженность? Физическая, организационная и социальная». Координация, организации, институты и нормы в агентных системах II . Международный семинар AAMAS 2006, COIN. Хакодате, Япония: Springer Berlin Heidelberg. стр. 293–307. дои : 10.1007/978-3-540-74459-7_19.
  10. ^ Хьюитт, Карл (март 2006 г.). «Повторяющийся упадок логического программирования и почему оно будет перевоплощено». Что пошло не так и почему: уроки исследований и применения искусственного интеллекта . Весенний симпозиум AAAI 2006 г. (технический отчет). Стэнфорд, Калифорния: AAAI. стр. 2–9. СС-06-08 . Проверено 10 марта 2022 г.