Применимость тезиса Черча-Тьюринга к интерактивным моделям вычислений

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

Единственная критика, которую я видел в этой работе, - это форум Lambda the Ultimate , на котором кто-то сетовал на авторов, которые постоянно публикуют то, что очевидно известно. Мой вопрос тогда заключается в том, есть ли еще какая-то критика в этой линии мышления, и в частности в их «Настойчивых машинах Тьюринга». А если нет, то почему это, казалось бы, изучено очень мало (я могу ошибаться). Наконец, как понятие универсальности переводится в интерактивную область.

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

Вы можете сказать: конечно, у меня есть «точка», но она совершенно неинтересна. Никто никогда не утверждал, что машина Тьюринга может справиться с любым возможным взаимодействием с внешним миром, не подключив его сначала к подходящей периферии. Если вы хотите, чтобы ТМ жарил хлеб, вам нужно подключить его к тостеру; тогда ТМ может легко справиться с внутренней логикой тостера (если только этот конкретный тостер не требует решения проблемы остановки или чего-то в этом роде, чтобы определить, насколько коричневым должен быть хлеб!). Точно так же, если вы хотите, чтобы ТМ обрабатывал интерактивное общение, вам необходимо подключить его к подходящим коммуникационным устройствам, как Нил обсуждал в своем ответе. Ни в том, ни в другом случае мы не говорим ничего, что не было бы очевидным для самого Тьюринга.

Таким образом, я бы сказал, что причина, по которой не было никакого «продолжения» к диатрибам Вегнера и Голдина, заключается в том, что TCS знает, как моделировать интерактивность всякий раз, когда это необходимо, и с радостью делает это с самого начала поля.

Обновление (8/30): Связанный пункт заключается в следующем. Неужели это когда-нибудь заставит критиков задуматься о том, что здесь, внутри Башни Слоновой Кости Тьюринга (ECTIT), основные темы исследований за последние два десятилетия включали интерактивные доказательства, многопартийные криптографические протоколы, коды для интерактивного общения, асинхронные протоколы для маршрутизации , консенсус, распространение слухов, выборы лидеров и т. д., и цена анархии в экономических сетях? Если из-за того, что представление Тьюринга о вычислениях находится в центре поля, так трудно обсуждать взаимодействие, как так мало кто из нас заметил?

Еще одно обновление: людям, которые продолжают стучать по барабану о том, что формализмы более высокого уровня намного более интуитивны, чем ТМ, и никто не думает с точки зрения ТМ как практического вопроса, позвольте мне задать чрезвычайно простой вопрос. Что в первую очередь позволяет существовать всем этим высокоуровневым языкам , гарантирует, что их всегда можно скомпилировать в машинный код? Может ли это быть ... э-э ... ЦЕРКОВЬ-ТЕЗИС , тот самый, на котором вы тряпили? Чтобы уточнить, тезис Церкви-Тьюринга не является утверждением, что "ТУРИНГ МАЧИНЕЗ ПРАВИЛА !!" Скорее, это утверждение, что любой разумный язык программирования будет эквивалентен по выразительной мощности машинам Тьюринга - и, как следствие,то, что вы могли бы также думать в терминах языков более высокого уровня, если это более удобно сделать. Это, конечно, было радикально новое понимание 60-75 лет назад.

Последнее обновление: я создал пост в блоге для дальнейшего обсуждения этого ответа.

Я думаю, что проблема довольно проста.

1. Все интерактивные формализмы могут моделироваться машинами Тьюринга.

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

3. Все, кто работает над математизацией взаимодействия, знают это.

Позвольте мне объяснить это более подробно.

Очевидно, что машины Тьюринга могут моделировать все существующие интерактивные модели вычислений в следующем смысле: выберите некоторую кодировку соответствующего синтаксиса в виде двоичных строк, напишите ТМ, который принимает в качестве входных данных две кодированные интерактивные программы P, Q (в выбранной модели интерактивных вычислений) и возвращает истину именно тогда, когда в соответствующей системе переписывания терминов происходит одностадийное сокращение от P до Q (если ваше исчисление имеет отношение тройного перехода, продолжайте mutatis mutandis). Таким образом, вы получили TM, который выполняет пошаговое моделирование вычислений в интерактивном исчислении. Ясно, что пи-исчисление, окружающее исчисление, CCS, CSP, сети Петри, временное пи-исчисление и любая другая интерактивная модель вычислений, которая была изучена, могут быть выражены в этом смысле. Это то, что люди имеют в виду, когда говорят, что взаимодействие не выходит за рамки ТМ.

Н. Кришнасвами ссылается на второй подход к моделированию интерактивности с использованием оракулов. Этот подход отличается от интерпретации приведенного выше соотношения редукция / переход, поскольку понятие ТМ изменено: мы переходим от простых ТМ к ТМ с оракульными лентами. Этот подход популярен в теории сложности и криптографии, главным образом потому, что он позволяет исследователям в этих областях переносить свои инструменты и результаты из последовательного в параллельный мир.

Проблема обоих подходов заключается в том, что теоретические проблемы параллельного подхода скрыты. Теория параллелизма стремится понять взаимодействие как феномен sui generis. Оба подхода через ТМ просто заменяют удобный формализм для выражения языка интерактивного программирования на менее удобный формализм.

Ни в том, ни в другом подходе подлинно теоретические вопросы параллелизма, т. Е. Коммуникации и поддерживающей их инфраструктуры, не имеют прямого представления. Они там, видимые обученному глазу, но закодированные, скрытые в непроницаемом тумане сложности кодирования. Таким образом, оба подхода плохи в математизации ключевых задач интерактивных вычислений. Возьмем, к примеру, то, что могло бы быть лучшей идеей в теории языков программирования за последние полвека, аксиоматизация Milner et al. В области экструзии областей видимости (что является ключевым шагом в общей теории композиционности):

Насколько просто эта идея, когда она выражается на специально подобранном языке, таком как пи-исчисление. Выполнение этого с использованием кодировки пи-исчисления в ТМ, вероятно, заняло бы 20 страниц.

Другими словами, изобретение явных формализмов для взаимодействия внесло следующий вклад в информатику: прямая аксиоматизация ключевых примитивов для связи (например, операторов ввода и вывода) и вспомогательных механизмов (например, генерация нового имени, параллельная композиция и т. Д.) , Эта аксиоматизация превратилась в настоящую исследовательскую традицию со своими конференциями, школами, терминологией.

Аналогичная ситуация складывается в математике: большинство понятий можно записать с использованием языка теории множеств (или теории топосов), но мы в основном предпочитаем понятия более высокого уровня, такие как группы, кольца, топологические пространства и так далее.

С точки зрения вычислимости чисел (т. Е. Вычислительных функций из ) все известные модели вычислений эквивалентны.$\mathbb{N} \to \mathbb{N}$

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

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

Я подозреваю, что получить это право выполнимо и, по сути, сводится к (1) рассмотрению строк оракула не как набора, а как топологического пространства, открытые множества которого кодируют модальную логику времени и знаний, которые вы хотите смоделировать, и (2) обеспечения что теоремы, которые вы доказываете, все непрерывны относительно этой топологии, рассматривая предикаты как непрерывные функции от цепочек оракула до значений истинности, рассматриваемых как пространство Серпинского. Я должен подчеркнуть, что это предположение , основанное на аналогии с теорией предметной области. Вам нужно будет проработать детали (и, вероятно, представить их в LICS или что-то в этом роде), чтобы быть уверенным.

В результате люди предпочитают моделировать взаимодействие, используя такие вещи, как модель Dolev-Yao , где вы явно моделируете взаимодействие между компьютерами и средой, чтобы вы могли явно охарактеризовать то, что знает злоумышленник. Это значительно упрощает формулирование подходящей модальной логики для рассуждений о безопасности, поскольку состояние системы плюс состояние среды представлены явно.

читая блог Лэнса Фортноуса, только что наткнулся на эту недавнюю / приятную / длинную обзорную статью по subj со многими ракурсами и ссылками [1] (которая пока не цитировалась), включает точку зрения Вегнера / Голдина (среди многих других). Я просто процитирую Fortnows отлично / решительное резюме / заявление / утверждение о почти официальной / единой / единодушной партийной линии TCS:

«Тем не менее, несколько компьютерных ученых пытаются утверждать, что тезис [Черч-Тьюринга] не в состоянии охватить некоторые аспекты вычислений. Некоторые из них были опубликованы в престижных местах, таких как Наука, Коммуникации ACM, и теперь как целая серия документы в ACM Ubiquity. Некоторые люди, не относящиеся к информатике, могут подумать, что существуют серьезные дебаты о природе вычислений. Нет ».

[1] Turings Titanic Machine от Барри С Купера CACM Vol 55

Я очень согласен с комментариями Ааронсона.

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

Меня отбрасывает комментарий Милнера, что лямбда-исчисление подходит для «последовательных процессов», но что-то еще необходимо для взаимодействия процессов.

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

Кажется, что я определил проект: интуитивно должно быть возможно механически преобразовать один полный по Тьюрингу язык в другой. Есть ли алгоритм для этого? Я должен буду смотреть на Google. Может быть, это невероятно трудно сделать, и так же сложно, как и проблема остановки.

Вчера я посмотрел в сети и нашел статьи о моделях лямбда-исчисления. Я удивился, обнаружив, что это очень глубокая кроличья нора.

Ричард Маллинс

Вот в чем дело, когда вы добавляете (чистую) интерактивность, формальность выходит за пределы окна. Это больше не «закрытая» система. Тогда возникает вопрос: каково понятие вычислений, когда вступает в силу интерактивность? Этот ответ: хорошо, либо другой пользователь / машина заменяет некоторые ваши вычисления (которые могут быть прописаны просто другим, более крупным, конечным автоматом), либо вы больше не находитесь в формально определяемой системе, и вы сейчас играете игры , в этом случае нет применение тезиса Черча-Тьюринга.

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

исторически оно также носило название кибернетика, изобретенное / сформулированное Вейнером. смысл робототехники заключается в том, что входы и выходы не просто цифровые и не имеют смысла, что можно было бы заключить, рассматривая ТМ; они есть, но они имеют реальные последствия / следствия / причины и т. д., и машина формирует обратную связь с окружающей средой.

поэтому я бы сказал, что ТМ и робототехника образуют, так сказать, очень естественную синергию или симбиотические отношения. но это не радикальное утверждение и что Вегнер объявляет с большой помпой является, сформулировано в различных условиях, не очень противоречивой или романа. Другими словами, Вегнер, похоже, намеренно позиционирует себя как интеллектуальный или академический иконоборец в своем стиле ... и кто же такое сообщество TCS, чтобы отказать ему в этом мелодраматическом обрамлении? тем не менее см. [2] для серьезного опровержения.

Пример Вегнера по вождению автомобиля очень актуален, и можно привести и другие ключевые недавние достижения в TCS :

• соревнование DARPA по автомобильным гонкам, а также закрытие Google технологии вождения автомобиля. [3]
• дело о победе шахмат Big Blue AI над Каспаровым
• недавняя победа Deep Blue Jeopardy Challenge
• все более автономный марсоход
• недавно объявленный прорыв в неконтролируемом распознавании объектов Google. [4]
• коммерческое распознавание речи

но это правда, что началось несколько десятилетий назад , как простой теории с ДЧ теперь очень реальный феномен и сегменты башни из слоновой кости ТКС сообщества может быть в какой - то сопротивление или даже отрицание этого факта и связанный с ним, фундаментальная [около Куна ] преобразование и сдвиг "в данный момент в игре". это несколько иронично, потому что Тьюринг был очень применен во многих его перспективах и исследованиях, таких как его интерес к операционному тесту ИИ (тест Тьюринга), химической динамике, вычислениям в шахматных решениях и т. д. [5].

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

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

[1] Тезис Черча-Тьюринга - разрушение мифа Голдина и Вегнера

[2] Есть ли новые модели вычислений? ответ Гольдину и Вегнеру от Cockshott & Michaelson

[3] Автомобили Googles - Зарегистрированные 300 миль, ни одна авария под управлением компьютера, Атлантика

[4] Google неконтролируемое распознавание объектов изображений Youtube

[5] Вклад Алан Турингс в CS

[6] Пейзаж интерактивных систем доказательства

[7] Об изменении нашей области - предложение