Является ли взаимодействие более мощным, чем алгоритмы?

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

Как это может быть так? Как может быть что-то более мощное, чем машина Тьюринга? В чем суть этой истории? Почему это не так хорошо известно?

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

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

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

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

• Алгоритмы на основе Oracle не часто рассматриваются в повседневных вычислениях, потому что обычные компьютеры не имеют волшебного «оракула» для предоставления данных. Но мы могли бы на самом деле просто использовать человека в качестве оракула. Если человек понимает запрашиваемые данные, он может даже помочь алгоритму продвинуться, тем самым улучшив его производительность. Другими словами, человек может предоставить полезную ленту оракула, а не просто случайную, и в принципе это может привести к более быстрым или более мощным вычислительным методам по сравнению с не-оракуловыми. В конце концов, то же самое происходит с рандомизированными вычислениями, когда машине дается последовательность случайных битов в качестве дополнительного входа.

Turning Machines моделируют вычисления и не имеют понятия взаимодействия. В этом смысле машина, которая поддерживает взаимодействие с внешней системой, может делать то, что не может сделать Turning Machine. Но вычисления, выполняемые между входным битом из внешнего источника, очевидно, всегда могут быть смоделированы машиной Тьюринга, поэтому даже «машина ввода-вывода» не может ничего сделать с внешним вводом, чего не может сделать машина Тьюринга.

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

Представьте себе программу для IO Machine, например: «для любого начального ввода ленты распечатайте содержимое ленты, затем прочитайте символ из внешнего ввода; примите, если символ равен 1, и отклоните в противном случае». Эта программа может решить любую проблему. Но только если внешняя система, с которой она может взаимодействовать, способна решить проблему; для меня это не очень интересный способ сказать, что IO Machine может решать проблемы, которые невозможно решить с помощью машин Тьюринга.

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

Однако существует не теоретический смысл, в котором интерактивность может повысить способность компьютера решать проблемы. Есть много вещей, которые люди делают очень точно, и мы не знаем, как заставить компьютеры работать очень хорошо. Но есть также много вещей, которые люди несут в себе, что мы можем заставить компьютеры делать. Сочетание этих двух факторов может привести к таким проектам, как reCaptcha , который эффективно автоматически оцифровывает книги, решая проблемы распознавания слов в трудных случаях. Получившаяся система компьютерного + человеческого труда достигает результата, который в настоящее время нецелесообразно достигать, используя только вычисления или только человеческий труд.

Недавно ACM провел симпозиум Ubiquity « Что такое вычисления? «В которой Питер Вегнер опубликовал статью, отражающую его взгляды на интерактивные вычисления.

Вот две выдержки из статьи Питера Вегнера:

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

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

Однако Fortnow, у которого есть статья на том же симпозиуме, по-видимому, не согласен с мнением Вегнера и считает, что интерактивные вычисления не дают никакой дополнительной власти над машинами Тьюринга.

Чтобы добавить к миксу, кажется, что мы все еще обсуждаем и определяем вычисления. У Моше Варди есть статья «Что такое алгоритм?», Сообщения ACM, Vol. 55, № 3, март 2012 г.

Варди сообщает о двух новых определениях алгоритмов. Первый предложен Гуревичем, а второй - Moschovakis.

Гуревич утверждал, что каждый алгоритм может быть определен в терминах абстрактного автомата.

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

Я не думаю, что модели с IO "более мощные", чем машины Тьюринга, они просто моделируют разные вещи.

Теоретически, вы можете рассматривать IO как (шумного?) Оракула. С идеальным оракулом вы можете выполнять компьютерные по Тьюрингу невычислимые функции; но откуда взять оракула? Люди - это единственный «супер-тьюринговский» выбор (если есть), и мы, как известно, очень ненадежны.

Класс программ, которые соответствуют этой модели, являются интерактивными помощниками (например, Изабель / HOL , Coq ). Они имеют дело с неразрешимыми пространствами доказательств, но (возможно) каждое доказательство может быть найдено (и проверено) с помощью подходящего пользовательского ввода.

Проверьте это :) " Идеи Тьюринга и модели вычислений " https://www.cs.montana.edu/~elser/turing%20papers/Turing%27s%20Ideas%20and%20Models%20of%20Computation.pdf