Безграничный недетерминизм - Unbounded nondeterminism
В информатике , неограниченная недетерминизм или неограниченная неопределенность является свойством параллельности , с помощью которого величина задержки в обслуживании запроса может быть неограниченной в результате арбитража раздора для общих ресурсов , в то же время гарантируя , что запрос будет в конечном счете , будет обслуживаться . Неограниченный недетерминизм стал важной проблемой в развитии денотационной семантики параллелизма , а позже стал частью исследования теоретической концепции гиперкомпьютера .
Справедливость
Обсуждение неограниченного недетерминизма имеет тенденцию вовлекаться в обсуждение справедливости . Основная концепция состоит в том, что все пути вычислений должны быть «справедливыми» в том смысле, что если машина входит в состояние бесконечно часто, она должна принимать все возможные переходы из этого состояния. Это равносильно требованию, чтобы машина гарантированно обслуживала запрос, если это возможно, поскольку бесконечная последовательность состояний будет разрешена только в том случае, если нет перехода, который приводит к обслуживанию запроса. Точно так же каждый возможный переход должен в конечном итоге произойти в бесконечном вычислении, хотя переход может занять неограниченное количество времени. Эту концепцию следует отличать от местной справедливости подбрасывания "справедливой" монеты, которая подразумевает, что для любого конечного числа шагов результат всегда может быть орлом, хотя по мере увеличения числа шагов это будет почти наверняка не произойдет.
Пример роли справедливого или неограниченного недетерминизма в слиянии струн был приведен Уильямом Д. Клингером в его диссертации 1981 года. Он определил «честное слияние» двух строк как третью строку, в которой каждый символ каждой строки должен в конечном итоге появиться. Затем он рассмотрел множество всех честных слияний двух строк слияния (S, T) , при условии , что это монотонная функция. Затем он утверждал, что merge (⊥, 1 ω ) ⊆ merge (0,1 ω ) , где ⊥ - пустой поток. Теперь merge (⊥, 1 ω ) = {1 ω }, поэтому должно быть, что 1 ω является элементом merge (0,1 ω ) ; противоречие. Он пришел к выводу, что:
- Похоже, что честное слияние не может быть записано как недетерминированная программа потока данных, работающая с потоками.
О возможности реализации неограниченного недетерминизма
Эдсгер Дейкстра [1976] утверждал, что невозможно реализовать системы с неограниченным недетерминизмом. По этой причине Тони Хоар [1978] предположил, что «эффективная реализация должна быть разумно справедливой».
Недетерминированные автоматы
Недетерминированные машины Тьюринга обладают только ограниченным недетерминизмом. Точно так же последовательные программы, содержащие защищенные команды как единственный источник недетерминизма, имеют только ограниченный недетерминизм ( Эдсгер Дейкстра [1976]). Вкратце, недетерминизм выбора ограничен. Гордон Плоткин привел доказательство в своей оригинальной статье 1976 года о степенных доменах:
- Теперь набор начальных сегментов последовательностей выполнения заданной недетерминированной программы P , начиная с заданного состояния, будет формировать дерево. Точки ветвления будут соответствовать точкам выбора в программе. Поскольку в каждой точке выбора всегда есть только конечное число альтернатив, фактор ветвления дерева всегда конечен. То есть дерево окончательное. Теперь лемма Кениг говорит , что если каждая ветвь финитарного дерева конечна, то и само дерево. В данном случае это означает, что если каждая последовательность выполнения P завершается, то существует только конечное число последовательностей выполнения. Итак, если выходной набор P бесконечен, он должен содержать [неопределенное вычисление].
Неопределенность против недетерминированных автоматов
Уильям Клинджер [1981] представил следующий анализ приведенного выше доказательства Плоткина:
- Это доказательство зависит от предпосылки, что если каждый узел x некоторой бесконечной ветви может быть достигнут некоторым вычислением c , то существует вычисление c, которое посещает каждый узел x ветви. ... Очевидно, что эта посылка следует не из логики, а, скорее, из интерпретации, данной точкам выбора. Эта предпосылка не подходит для недетерминизма прибытия [в прибытии сообщений в модели Актера] из-за конечной задержки [в прибытии сообщений]. Хотя каждый узел бесконечной ветви должен лежать на ветви с пределом, бесконечная ветвь не обязательно должна иметь предел. Таким образом, существование бесконечной ветви не обязательно подразумевает неконечное вычисление.
Безграничный недетерминизм и невычислимость
Spaan et al. [1989] утверждали, что неограниченно недетерминированная программа может решить проблему остановки ; их алгоритм состоит из двух частей, определяемых следующим образом:
Первая часть программы запрашивает натуральное число из второй части; после его получения он будет перебирать желаемую машину Тьюринга для этого количества шагов и принимать или отклонять в зависимости от того, остановилась ли машина.
Вторая часть программы недетерминированно выбирает натуральное число по запросу. Число хранится в переменной, которая инициализируется 0; затем программа неоднократно выбирает, увеличивать ли переменную или обслуживать запрос. Ограничение справедливости требует, чтобы запрос в конечном итоге был обслужен, поскольку в противном случае существует бесконечный цикл, в котором когда-либо берется только ветвь «увеличить переменную».
Ясно, что если машина действительно останавливается, у этого алгоритма есть приемлемый путь. Если машина не останавливается, этот алгоритм всегда будет отклонять, независимо от того, какое число вернет вторая часть программы.
Аргументы в пользу неограниченного недетерминизма
Клинджер и Карл Хьюитт разработали модель (известную как модель акторов ) параллельных вычислений со свойством неограниченного недетерминизма, встроенным в [Clinger 1981; Hewitt 1985; Хьюитт и Ага 1991; Hewitt 2006b]; это позволяет выполнять вычисления, которые не могут быть реализованы машинами Тьюринга, как показано выше. Однако эти исследователи подчеркивают, что их модель параллельных вычислений не может реализовать какие-либо функции, которые не входят в класс рекурсивных функций, определенных Черчем, Клини, Тьюрингом и т. Д. (См. Неопределенность в параллельных вычислениях ).
Хьюитт [2006] оправдал свое использование неограниченного недетерминизма, утверждая, что нет никаких ограничений, которые могут быть наложены на то, сколько времени требуется вычислительной схеме, называемой арбитром, для урегулирования (см. Метастабильность в электронике ). Арбитры используются в компьютерах, чтобы иметь дело с обстоятельствами, когда компьютерные часы работают асинхронно с вводом извне, например. , ввод с клавиатуры, доступ к диску, сетевой ввод и т. д. Таким образом, получение сообщения, отправленного на компьютер, может занять неограниченное время, а в это время компьютер может пройти неограниченное количество состояний.
Он также утверждал, что электронная почта допускает неограниченный недетерминизм, поскольку почта может храниться на серверах неопределенное время перед доставкой, и что каналы передачи данных с серверами в Интернете также могут быть отключены на неопределенное время. Это породило безграничную полемику о недетерминизме .
Анализ справедливости Хьюитта
Хьюитт утверждал, что проблемы справедливости частично проистекают из точки зрения глобального государства. Самые старые модели вычислений (например, машины Тьюринга , постановки Поста, лямбда-исчисление и т. Д.) Основаны на математике, которая использует глобальное состояние для представления вычислительного шага . Каждый вычислительный шаг - это переход от одного глобального состояния вычисления к следующему глобальному состоянию. Подход глобального состояния был продолжен в теории автоматов для конечных автоматов и машин с выталкивающим стеком, включая их недетерминированные версии. Все эти модели обладают свойством ограниченного недетерминизма: если машина всегда останавливается при запуске в своем начальном состоянии, то существует ограничение на количество состояний, в которых она может остановиться.
Хьюитт утверждал, что существует фундаментальная разница между выбором в недетерминизме глобального состояния и неопределенностью порядка прибытия (недетерминизм) его модели Актера . В недетерминизме глобального состояния делается «выбор» для «следующего» глобального состояния. В случае неопределенности порядка прибытия арбитраж принимает решение о каждом порядке прибытия локально в неограниченный промежуток времени. Пока идет местный арбитраж, неограниченная деятельность может иметь место в другом месте. Нет глобального состояния и, следовательно, нет «выбора» в отношении «следующего» глобального состояния.
использованная литература
- Карл Хьюитт , Питер Бишоп и Ричард Штайгер. Универсальный модульный актерский формализм для искусственного интеллекта IJCAI 1973.
- Робин Милнер. Процессы: математическая модель вычислительных агентов в логическом коллоквиуме 1973.
- Карл Хьюитт и др. Актерский вводный курс и запись конференции по метаоценке симпозиума ACM по принципам языков программирования, январь 1974 г.
- Карл Хьюитт и др. Поведенческая семантика нерекурсивных структур управления Proceedings of Colloque sur la Programmation, апрель 1974 г.
- Ирен Грейф. Семантика общающихся параллельных профессоров MIT EECS Докторская диссертация. Август 1975 г.
- Гордон Д. Плоткин . Построение области мощности. SIAM Journal on Computing, 5: 452-487, сентябрь 1976 г.
- Эдсгер Дейкстра . Дисциплина программирования Prentice Hall . 1976 г.
- Карл Хьюитт и Генри Бейкер Актеры и непрерывные функционалы Труды Рабочей конференции IFIP по формальному описанию концепций программирования. 1–5 августа 1977 г.
- Жиль Кан и Дэвид Маккуин. Сопрограммы и сети параллельных процессов ИФИП. 1977 г.
- Генри Бейкер. Акторские системы для вычислений в реальном времени. Докторская диссертация MIT EECS. Январь 1978 г.
- Майкл Смит. Power domains Журнал компьютерных и системных наук. 1978 г.
- Джордж Милн и Робин Милнер. Параллельные процессы и их синтаксис JACM. Апрель 1979 г.
- АВТОМОБИЛЬ Хоар . Связь последовательных процессов CACM. Август 1978 г.
- Ниссим Франсез , К.А. Хор, Даниэль Леманн и Виллем де Ровер. Семантика недетерминизма, параллелизма и коммуникации. Журнал компьютерных и системных наук. Декабрь 1979 г.
- Нэнси Линч и Майкл Фишер . Об описании поведения распределенных систем в семантике параллельных вычислений. Springer-Verlag. 1979 г.
- Джеральд Шварц Денотационная семантика параллелизма в семантике параллельных вычислений. Springer-Verlag. 1979 г.
- Уильям Уэдж. Расширенное рассмотрение тупика потока данных Семантика параллельных вычислений. Springer-Verlag. 1979 г.
- Ральф-Йохан Бэк. Семантика неограниченного недетерминизма ICALP 1980.
- Дэвид Парк. О семантике справедливого параллелизма Труды Зимней школы по формальной спецификации программного обеспечения. Springer-Verlarg. 1980 г.
- Дана Скотт . Что такое денотационная семантика? Серия выдающихся лекций лаборатории информатики Массачусетского технологического института. 17 апреля 1980 г.
- Уильям Д. Клинджер, Основы актерской семантики . Докторская диссертация по математике Массачусетского технологического института, июнь 1981 г.
- Уильям Д. Клинджер, Недетерминированный призыв по необходимости не является ни ленивым, ни именем. Стр. 226–234 симпозиума по LISP и функциональному программированию . Питтсбург, Пенсильвания, 1982.
- Стивен Брукс, Тони Хоар и Билл Роско Теория передачи последовательных процессов JACM. Июль 1984 г.
- Карл Хьюитт, Журнал «Проблемы открытых систем ». Апрель 1985 г. Перепечатано в "Основы искусственного интеллекта" - сборнике материалов Cambridge University Press. 1990 г.
- Билл Роско . Неограниченный недетерминизм в CSP в "Две статьи о CSP", техническая монография PRG-67, Вычислительная лаборатория Оксфордского университета. Июль 1988 г.
- Языки с предложениями Карла Хьюитта и Гул Ага Guarded Horn: являются ли они дедуктивными и логичными? Международная конференция по компьютерным системам пятого поколения, Омша, 1988 г., Токио. Также в искусственном интеллекте в Массачусетском технологическом институте , Vol. 2. MIT Press 1991.
- А. В. Роско: теория и практика параллелизма , Prentice Hall, ISBN 0-13-674409-5 .
- Эдит Спаан, Лин Торенвлит и Питер ван Эмде Боас. Недетерминизм, справедливость и фундаментальная аналогия . Бюллетень EATCS, 37: 186-193, 1989.
- Дэвид А. Шмидт, Структура типизированных языков программирования . MIT Press, Кембридж, Массачусетс, 1994.
- Батлер, MJ и Морган, CC Action Systems, неограниченный недетерминизм и бесконечные следы. Формальный аспект вычислений. 1995 г.
- Томас А. Судкамп, Языки и машины . 2-е издание. Аддисон-Уэсли, Рединг, Массачусетс, 1997.
- Лука Ачето и Эндрю Д. Гордон (редакторы). Алгебраические вычисления процесса: первые двадцать пять лет и позже Алгебра процессов. Бертиноро, Форли, Италия, 1–5 августа 2005 г.
- Стивен Брук. Retracing CSP в алгебраических вычислениях процесса: первые двадцать пять лет и далее . Август 2005 г.
- А. В. Роско: теория и практика параллелизма , Prentice Hall, ISBN 0-13-674409-5 . Пересмотрено в 2005 г.
- Карл Хьюитт. Неоднократная кончина логического программирования и причины его возрождения. Что пошло не так и почему: уроки исследований и приложений искусственного интеллекта. Технический отчет SS-06-08. AAAI Press. Март 2006 г.
- Карл Хьюитт, что такое приверженность? Физическая, организационная и социальная сфера COIN @ AAMAS. 27 апреля 2006 г.
- Тоби Орд. Гипервычисления: Вычисления больше, чем машина Тьюринга может вычислить на arxiv.org .