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

38

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

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

Зенна
источник
PS: вы также можете взглянуть на этот вопрос о гипер-вычислениях.
Каве
6
Вот еще один похожий вопрос .
Дэйв Кларк
7
Я думаю, что Андрей и Нил объяснили здесь, что ответ отрицателен для задач вычисления функции более высокого типа. Таким образом , по существу , Черча-Тьюринга Тезис о числовых задачах функции вычисления. Обычные эквивалентности между моделями вычислений не имеют места для более высоких типов. (Однако, насколько я понимаю, речь идет скорее о механизмах взаимодействия и о том, как представлены объекты более высокого типа, чем о вычислительной мощности моделей.) (Перепост, чтобы исправить несколько опечаток)
Kaveh
7
Я согласен с Каве.
Андрей Бауэр
На самом деле, первая статья в этом направлении, похоже, относится к 1996-1997 гг. «Почему взаимодействие важнее алгоритмов» или «Смена парадигмы от алгоритмов к взаимодействию». позже в статье упоминаются пещера Платоса, «брезент Тьюринга» (?), «Критика чистого разума» Канта, диалектическая логика Маркса, Декарт, Пенроуз, Сирл. так что, возможно, это следует рассматривать как граничащий с философским, а не так в духе технического / математического TCS. нет математики, нет лемм или доказательств или thms. в то время как, возможно, он немного грандиозен, он искренне стремится понять «общую картину» тезиса КТ по ​​истории и т. д.
vzn

Ответы:

75

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

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

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

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

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

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

Скотт Ааронсон
источник
8
Существует существенная разница между тостерами и взаимодействием: каждая модель вычислений имеет некоторый механизм ввода-вывода. Тостеры появляются очень редко. Некоторые модели вычислительной модели IO наивны: например, машины Тьюринга имеют дело с IO только неформально. Это не проблематично, когда вычисления считаются функциональными, т.е. начинаются с ввода и заканчиваются выводом, как это происходит на машинах Тьюринга. Однако это наивно становится обременительным, когда вы хотите иметь дело с подлинными параллельными явлениями, например, когда два интерактивных вычисления равны? (Продолжение ниже.)
Мартин Бергер
12
В случае, если мои взгляды еще недостаточно ясны, я должен добавить, что я нахожу, что вся литература "миф о тезисе Церковью-Тьюринга" не просто колеблется, но (что более важно) удручающе бесплодна идей. Чтение этого приносит всю радость чтения того, кто утверждает, что опровергает физику Ньютона, не из-за чего-то классного, такого как квантовая механика или теория относительности, а потому, что «законы Ньютона игнорируют трение» . Или слушая, как ребенок объясняет, почему она технически выиграла настольную игру, потому что она сдвинула фигуры, пока вы уходили в ванную.
Скотт Ааронсон
7
Я думаю, что цитата Лэнса Фортнау, приведенная ниже в ответе vzn (оригинальная статья здесь: ubiquity.acm.org/article.cfm?id=1921573 ), демонстрирует, что по крайней мере несколько здравомыслящих людей придерживаются тезиса «Сильный». Fortnow утверждает, что тезис КТ можно «просто изложить» как «все вычислимо вычислимо на машине Тьюринга», написав «все», где он должен был написать «каждый ». f:NN
Ноам Цайлбергер
10
как мы можем спорить о так называемом тезисе, названном в честь Тьюринга и Черча, и ни один из них на самом деле не сформулировал в собственном написании тезис, как он позже был интерпретирован и развит? - См. Также: формула Эйлера, исключение Гаусса, алгоритм Евклида, теорема Пифагора.
Джеффс
14
двадцать комментариев! Скотт успешно превратил общий ответ в оптимизированный пост в Shtetl ...
Сашо Николов
35

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

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

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

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

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

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

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

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

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

P|(νx)Q  (νx)(P|Q)provided xfv(P)

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

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

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

Мартин Бергер
источник
1
+1 за объяснение мощности модели ТМ по сравнению с интерактивными вычислительными системами (она может имитировать их).
Каве
3
Если бы я только мог проголосовать за это несколько раз.
Виджай Д
26

С точки зрения вычислимости чисел (т. Е. Вычислительных функций из ) все известные модели вычислений эквивалентны.NN

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

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

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

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

Нил Кришнасвами
источник
1

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

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

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

ВЗН
источник
-4

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

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

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

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

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

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

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

Ричард Маллинс
источник
-7

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

Доктор
источник
2
Интерактивные модели вычислений, такие как исчисления процессов, являются играми в смысле игровой семантики .
Мартин Бергер
1
Поведение человека не имеет значения. Важно то, что вычислимые интерактивные устройства действуют алгоритмически и механически по отношению к своим входам.
Мартин Бергер
1
@ Марк Джей, я не понимаю, что ты говоришь. Интерактивный подход просто говорит, что устройство вычислимо, если оно реагирует на свои входные данные механическим способом, используя ограниченные ресурсы. Да, если другая часть взаимодействия делает что-то сумасшедшее, например, ввод Омеги Чейтина, то механическое устройство может делать что-то сумасшедшее, например, вычисление проблемы остановки. Ну и что?
Мартин Бергер
1
По моему мнению, CTT не о том, что физически осуществимо. Вместо этого это грубый тест, который исключает некоторые явно не реализуемые вещи: если CTT говорит, что что-то не вычислимо, то это физически не реализуемо, но я не думаю, что обратное значение имеет место.
Мартин Бергер
1
@ Марк J, требование «устройство вычислимо, если оно реагирует на свои входные данные механическим способом, используя ограниченные ресурсы», не требует, чтобы входные данные генерировались механически. Конечно, ввод Омега Чейтина не может быть произведен механически.
Мартин Бергер
-8

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

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

поэтому я бы сказал, что ТМ и робототехника образуют, так сказать, очень естественную синергию или симбиотические отношения. но это не радикальное утверждение и что Вегнер объявляет с большой помпой является, сформулировано в различных условиях, не очень противоречивой или романа. Другими словами, Вегнер, похоже, намеренно позиционирует себя как интеллектуальный или академический иконоборец в своем стиле ... и кто же такое сообщество 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] Об изменении нашей области - предложение

ВЗН
источник
9
то, что началось десятилетия назад как простая теория с ТМ, теперь явление очень реальное - конечно, мы это знаем. Мы называем это "информатика".
Джеффс
аналогия, которая была на грани моих мыслей при написании этого, но, наконец, выяснилась позже: думаю, что различие между биологией in vivo и биологией in vitro является актуальным. ТМ аналогична последнему. другие (появляющиеся) модели аналогичны первым. =)
vzn
в любом случае, в томе 2006 года многие престижные компьютерные ученые согласны с новой парадигмой. обратите внимание также на заключительное эссе в сборнике: Линн Стейн, «Взаимодействие, вычисления и образование». В этом томе в целом описан фундаментальный сдвиг в культуре вычислений от акцента на решении алгоритмических задач к перспективе, в которой взаимодействие играет центральную роль. , В этой главе Стейн указывает, что такой сдвиг должен сопровождаться соответствующим сдвигом в образовании по информатике, в фундаментальной «истории», которую мы рассказываем нашим студентам на их вводных курсах.
vzn
4
@vzn Аргумент от власти
Мартин Бергер