Изобретение машины Тьюринга в 1936 году Аланом Тьюрингом положило начало современным вычислениям.
Вычисление – знакомая концепция, которую большинство из нас понимает интуитивно. Возьмем функцию f(x) = x + 3. Когда x равно трем, f(3) = 3 + 3. Шесть. Легко. Кажется очевидным, что эта функция вычислима. Но некоторые функции не так просты, и не так просто определить, можно ли их вычислить, а значит, они могут никогда не дать нам окончательного ответа.
В 1928 году немецкие математики Давид Гильберт и Вильгельм Аккерманн предложили вопрос, названный Entscheidungsproblem («проблема принятия решения»). Со временем их вопрос привёл к формальному определению вычислимости, которое позволило математикам ответить на множество новых проблем и заложило основу теоретической информатики.
Определение пришло от 23-летнего аспиранта по имени Алан Тьюринг, в 1936 году написавшего основополагающую статью, которая не только формализовала концепцию вычислений, но и доказала фундаментальный вопрос математики и заложила интеллектуальную основу для изобретения вычислительной техники. Великое озарение Тьюринга состояло в том, чтобы дать конкретный ответ на вопрос о вычислениях в форме абстрактной машины, которую его научный руководитель Алонзо Чёрч позже назвал машиной Тьюринга. Она абстрактна, потому что не существует (и не может) физически существовать как осязаемое устройство. Это концептуальная модель вычислений: если машина может вычислить функцию, то эта функция вычислима.
Вот как это работает. Машина Тьюринга может считывать и изменять символы на бесконечно длинной ленте в соответствии с таблицей правил. Лента состоит из «ячеек», каждая из которых может хранить ровно один символ, и машина считывает и перезаписывает содержимое ячеек с помощью записывающей головки. Каждое правило в таблице определяет, что должна делать машина, основываясь как на её текущем состоянии, так и на считываемом символе. Машина может войти в конечное состояние («состояние принятия» или «состояние отклонения»), в котором она останавливается, принимая или отклоняя ввод. Или она попадает в бесконечный цикл и продолжает читать ленту вечно.
Лучший способ понять машину Тьюринга – рассмотреть простой пример. Давайте представим тот, который разработан, чтобы сказать нам, является ли данный вход числом нуль. Мы будем использовать входной номер 0001, сопровождаемый пустыми символами (#), поэтому «#0001#» является частью нашей ленты.
Машина запускается в начальном состоянии, которое мы назовем q0. Она читает крайнюю левую ячейку на нашей ленте и находит пустой символ. Правила гласят: «В состоянии q0, если символ #, оставить всё как есть без изменений, переместиться на одну ячейку вправо и изменить состояние машины на q1». После этого шага машина находится в состоянии q1, и её головка считывает второй символ, 0.
Теперь ищем правило, применимое к этим условиям. Мы находим то, что говорит: «Оставайтесь в состоянии q1 и переместите головку на одну ячейку вправо». Это оставляет нас в той же позиции (в состоянии q1, чтение «0»), поэтому мы продолжаем двигаться вправо, пока головка, наконец, не прочитает иное число, 1.
Когда мы снова обращаемся к таблице, мы находим новое правило: «Если мы встречаем 1, переходим к q2, что является состоянием «отклонения». Машина останавливается, отвечая «Нет» на первоначальный вопрос: «0001 – это нуль?»
Если вместо этого ввести «#0000#», машина встретит # после всех этих нулей. Когда мы сверяемся с таблицей, мы находим правило, говорящее, что машина переходит в состояние q3, состояние «принятия». Теперь машина отвечает «Да» на вопрос «Является ли «0000» нулём?»
С помощью своей абстрактной машины Тьюринг создал модель вычислений, чтобы ответить на Entscheidungsproblem. Она формально спрашивает: при заданном наборе математических аксиом существует ли механический процесс – набор инструкций, который сегодня мы назвали бы алгоритмом, – при помощи которого можно было бы определить, верно ли некое утверждение?
Скажем, мы хотим найти алгоритм, который может сказать нам, возможна ли определенная шахматная позиция. Здесь аксиомы – это шахматные правила, регулирующие допустимые ходы. Можем ли мы выполнить конечную пошаговую последовательность процедур, чтобы достичь этого положения? Хотя анализ некоторых позиций может занять больше времени, чем наша жизнь – алгоритм может генерировать все возможные позиции и сравнивать каждую из них с входными данными – такие алгоритмы существуют в игре в шахматы. В результате мы говорим, что шахматы «разрешимы».
Однако в 1936 году Чёрч и Тьюринг, используя разные методы, независимо друг от друга доказали, что не существует общего способа решения всех случаев Entscheidungsproblem. Например, некоторые игры, такие как «Игра жизни» Джона Конвея, неразрешимы: ни один алгоритм не может определить, появится ли определенный паттерн из исходного паттерна.
Тьюринг показал, что функция вычислима, если существует алгоритм, который может выполнить желаемую задачу. В то же время он показал, что алгоритм – это процесс, который может быть определен машиной Тьюринга. Следовательно, вычислимая функция – это функция, для вычисления которой используется машина Тьюринга. Это может показаться обходным способом определения вычислимости, но это лучшее, что у нас есть.
«Не похоже, что у вас есть выбор определить это каким-то иным образом, – сказал Майкл Сипсер, ученый-теоретик из Массачусетского технологического института. – Я думаю, общепризнанно, что тезис Чёрча-Тьюринга гласит: неформальное понятие алгоритма соответствует тому, что может сделать любая «разумная» вычислительная модель».
Другие математики придумали другие модели вычислений, которые на первый взгляд выглядят совсем иначе, но на самом деле эквивалентны: они могут выполнять любые вычисления, которые могут выполнять машины Тьюринга, и наоборот.
Всего через несколько лет после того, как Курт Гёдель доказал, что математика неполна, Чёрч и Тьюринг этой работой показали, что некоторые проблемы математики неразрешимы – никакой алгоритм, каким бы сложным он ни был, не может сказать нам ответ да или нет. И то, и другое было сокрушительным ударом для Гильберта, который надеялся, что у математики будут аккуратные, идеализированные ответы. Но, возможно, это и к лучшему: если бы существовало общее решение проблемы Entscheidungsproblem, это означало бы, что все проблемы в математике можно было бы свести к простым механическим вычислениям.
Помимо ответов на эти фундаментальные вопросы, машина Тьюринга также привела непосредственно к разработке современных компьютеров через вариант, известный как универсальная машина Тьюринга. Это такая машина Тьюринга, которая может имитировать любую иную машину Тьюринга на любом входе. Она может считывать описание других машин Тьюринга (их правил и входных лент) и моделировать их поведение на своей собственной входной ленте, производя тот же результат, что и симулированная машина, точно так же, как современные компьютеры могут считывать любую программу и выполнять её. В 1945 году Джон фон Нейман предложил компьютерную архитектуру, названную архитектурой фон Неймана, которая сделала возможной концепцию универсальной машины Тьюринга в реальной машине.
Когда Санджив Арора, учёный из Принстонского университета, преподает эту концепцию, он делает акцент на более широкой философской картине.
«Есть два понятия «универсального», – сказал он. – Одно из представлений об универсальности состоит в том, что она может управлять любой другой машиной Тьюринга. Но другое, более важное понятие «универсального» заключается в том, что она может выполнять любые вычисления, которые вы придумаете во вселенной».
В мире классической физики любой физический процесс может быть симулирован или смоделирован с помощью алгоритмов, которые, в свою очередь, могут быть симулированы машиной Тьюринга.
Ещё один известный и очень полезный вариант – вероятностная машина Тьюринга. В отличие от обычной машины Тьюринга, у которой есть чётко определенная реакция на каждый вход, вероятностная машина Тьюринга может иметь несколько реакций, основанных на вероятностях. Это означает, что она может давать разные результаты для одних и тех же входных данных в разное время. Удивительно, но такого рода вероятностная стратегия может быть более эффективной, чем чисто детерминистический подход к некоторым проблемам. Было показано, что идеи вероятностных машин Тьюринга практически полезны в таких областях, как криптография, оптимизация и машинное обучение.
Эти абстрактные машины, возможно, являются лучшим доказательством того, что постановка фундаментальных вопросов может быть одной из самых полезных вещей, которые может сделать учёный.
Автор перевода @arielf
НЛО прилетело и оставило здесь промокод для читателей нашего блога:
— 15% на заказ любого VDS (кроме тарифа Прогрев) — HABRFIRSTVDS.
