Безграничный недетерминизм - Unbounded nondeterminism

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

В Информатика, неограниченный недетерминизм или же безграничная неопределенность является собственностью параллелизм при котором величина задержки в обслуживании запроса может стать неограниченной в результате арбитража разногласий за совместно используемые ресурсы при этом гарантируя, что запрос в конечном итоге будет обработан. Безграничный недетерминизм стал важной проблемой в развитии денотационная семантика параллелизма, а позже стал частью исследования теоретической концепции гипервычисления.

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

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

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

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

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

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

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

Недетерминированные машины Тьюринга имеют только ограниченный недетерминизм. Точно так же последовательные программы, содержащие охраняемые команды в качестве единственного источника недетерминизма, имеют только ограниченный недетерминизм (Эдсгер Дейкстра [1976]). Вкратце, недетерминизм выбора ограничен. Гордон Плоткин дал доказательство в своей оригинальной статье 1976 года о степенных доменах:

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

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

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

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

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

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

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

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

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

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

Клингер и Карл Хьюитт^{[нужна цитата ]} разработали модель (известную как Актерская модель ) параллельных вычислений со свойством неограниченного недетерминизма, встроенным в [Clinger 1981; Hewitt 1985; Хьюитт и Ага 1991; Hewitt 2006b]; это позволяет вычисления это не может быть реализовано машинами Тьюринга, как показано выше. Однако эти исследователи подчеркивают, что их модель параллельных вычислений не может реализовать какие-либо функции, которые не входят в класс рекурсивные функции^{[нужна цитата ]} определено Черчем, Клини, Тьюрингом, и Т. Д. (Видеть Неопределенность в параллельных вычислениях.)

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

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

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

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

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

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

• Карл Хьюитт, Питер Бишоп и Ричард Штайгер. Универсальный модульный актерский формализм для искусственного интеллекта IJCAI 1973.
• Робин Милнер. Процессы: математическая модель вычислительных агентов в Коллоквиуме по логике 1973.
• Карл Хьюитт, и другие. Актерская индукция и мета-оценка Запись конференции ACM Symposium on Principles of Programming Languages, январь 1974 г.
• Карл Хьюитт, и другие. Поведенческая семантика нерекурсивных структур управления Proceedings of Colloque sur la Programmation, апрель 1974 г.
• Ирен Грейф. Семантика общения параллельных профессий Докторская диссертация MIT EECS. Август 1975 г.
• Гордон Д. Плоткин. Конструкция энергетической области SIAM Journal on Computing, 5: 452-487, сентябрь 1976 г.
• Эдсгер Дейкстра. Дисциплина программирования Prentice Hall. 1976.
• Карл Хьюитт и Генри Бейкер Актеры и непрерывные функционалы Материалы рабочей конференции ИФИП по формальному описанию концепций программирования. 1–5 августа 1977 г.
• Жиль Кан и Дэвид Маккуин. Сопрограммы и сети параллельных процессов ИФИП. 1977 г.
• Генри Бейкер. Актерские системы для вычислений в реальном времени Докторская диссертация MIT EECS. Январь 1978 г.
• Майкл Смит. Силовые домены Журнал компьютерных и системных наук. 1978 г.
• Джордж Милн и Робин Милнер. Параллельные процессы и их синтаксис JACM. Апрель 1979 г.
• К. А. Р. Хоар. Связь последовательных процессов CACM. Август 1978 г.
• Ниссим Франсез, К. А. Р. Хор, Даниэль Леманн и Виллем де Ровер. Семантика недетерминизма, параллелизма и коммуникации Журнал компьютерных и системных наук. Декабрь 1979 г.
• Нэнси Линч и Майкл Фишер. Об описании поведения распределенных систем в семантике параллельных вычислений. Springer-Verlag. 1979 г.
• Джеральд Шварц Денотационная семантика параллелизма в семантике параллельных вычислений. Springer-Verlag. 1979 г.
• Уильям Уэдж. Расширенная обработка тупика потока данных Семантика параллельных вычислений. Springer-Verlag. 1979 г.
• Ральф-Йохан Бэк. Семантика неограниченного недетерминизма ИКАЛП 1980.
• Дэвид Парк. О семантике справедливого параллелизма Материалы Зимней школы по формальной спецификации программного обеспечения. Springer-Verlarg. 1980 г.
• Дана Скотт. Что такое денотационная семантика? Серия выдающихся лекций лаборатории информатики Массачусетского технологического института. 17 апреля 1980 г.
• Уильям Д. Клингер, Основы актерской семантики. Докторская диссертация по математике Массачусетского технологического института, июнь 1981 г.
• Уильям Д. Клингер, Недетерминированный вызов по необходимости не ленивый и не по имени Страницы 226-234 в Симпозиум по LISP и функциональному программированию. Питтсбург, Пенсильвания, 1982.
• Стивен Брукс, Тони Хоар и Билл Роско Теория передачи последовательных процессов JACM. Июль 1984 г.
• Карл Хьюитт, Вызов открытых систем Байт Журнал. Апрель 1985 г. Перепечатано в Основы искусственного интеллекта --- справочник Издательство Кембриджского университета. 1990 г.
• Билл Роско. Неограниченный недетерминизм в CSP в «Две статьи о CSP», техническая монография PRG-67, Вычислительная лаборатория Оксфордского университета. Июль 1988 г.
• Карл Хьюитт и Гуль Ага Языки с оговорками Сторожевого Рога: являются ли они дедуктивными и логическими? Международная конференция по компьютерным системам пятого поколения, Омша, 1988 г., Токио. Также в Искусственный интеллект в MIT, Vol. 2. MIT Press 1991.
• А. В. Роско: Теория и практика параллелизма, Прентис Холл, ISBN  0-13-674409-5.
• Эдит Спаан, Лин Торенвлит и Питер ван Эмде Боас. Недетерминизм, справедливость и фундаментальная аналогия. Бюллетень EATCS, 37: 186-193, 1989.
• Дэвид А. Шмидт, Структура типизированных языков программирования. MIT Press, Кембридж, Массачусетс, 1994.
• Батлер, М. Дж. И Морган, К. С. Системы действий, неограниченный недетерминизм и бесконечные следы Формальный аспект вычислений. 1995 г.
• Томас А. Судкамп, Языки и машины. 2-е издание. Аддисон-Уэсли, Рединг, Массачусетс, 1997.
• Лука Ачето и Эндрю Д. Гордон (редакторы). Вычисления алгебраических процессов: первые двадцать пять лет и далее » Алгебра процессов. Бертиноро, Форли, Италия, 1–5 августа 2005 г.
• Стивен Брук. Повторная проверка CSP в Вычисления алгебраических процессов: первые двадцать пять лет и далее. Август 2005 г.
• А. В. Роско: Теория и практика параллелизма, Прентис Холл, ISBN  0-13-674409-5. Пересмотрено в 2005 г.
• Карл Хьюитт. Неоднократная кончина логического программирования и причины его возрождения Что пошло не так и почему: уроки исследований и приложений искусственного интеллекта. Технический отчет SS-06-08. AAAI Press. Март 2006 г.
• Карл Хьюитт, Что такое обязательство? Физические, организационные и социальные МОНЕТА @ AAMAS. 27 апреля 2006 г.
• Тоби Орд. Гипервычисления: вычисления больше, чем может вычислить машина Тьюринга на arxiv.org.