Машина Тьюринга — что это: роскошь или средство вычисления?

Любой, кто интересуется информатикой, компьютерами и IT, рано или поздно встретит термин «машина Тьюринга». Понять, что это, с помощью соответствующей страницы в «Википедии» категорически невозможно, даже не пытайтесь. Поэтому мы решили справиться сами — и вам рассказать.

Всё, что нужно знать о машине Тьюринга

• Зачем она нужна
• Как устроена
• Принцип работы
• Роль в истории
• Полнота по Тьюрингу
• Примеры реализации
• При чём тут грибы?

Зачем она нужна

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

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

Чуть позже, в 1930-е годы, к этому же вопросу обратился третий, не менее знаменитый, математик Макс Ньюман. Он преподавал в Кембридже, был криптоаналитиком и одним из создателей Colossus — самого большого компьютера тех времён.

Среди студентов Ньюмана был пока ещё никому не известный математик Алан Тьюринг. Валяясь на лугах Гранчестера, где любили отдыхать тогдашние хипстеры, он размышлял над словами Ньюмана. Итогом этих раздумий стала статья On Computable Numbers, with an Application to the Entscheidungsproblem

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

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

Что такое машина Тьюринга и как она устроена

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

• бесконечной ленты с ячейками;
• автомата или головки для чтения и записи;
• программы.

Принцип работы машины Тьюринга

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

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

На рисунке выше изображена лента, входная информация (11В) расположена так, что в каждой клетке по одному символу. До и после неё — нулевые ячейки. Исходное состояние головки — q1. Это состояние запускает работу машины. Головка может сдвинуться влево и вместо 0 записать цифру или букву. Также она может сдвинуться вправо и перезаписать 1 другой цифрой или буквой. Или передвинуться ещё на ячейку влево/вправо без перезаписи.

Головка может также остаться на месте и ничего не делать. Выполнение операций прекращается после того, как головка считывает пассивное состояние — q0.

В чём же важность этой, на первый взгляд, нехитрой конструкции?

Роль в истории

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

Также новаторство Тьюринга было в том, что его машина использовала двоичную систему во времена, когда преобладала десятичная. Привычные для нас двоичные числа для большинства читателей в 1936 году были не столь знакомы. Так, компьютер ENIAC (1943–1945) использовал десятичную систему. А слово «бит» (сокращение от binary digit, «двоичная цифра») появилось в публикациях только в 1948 году.

Важность работы Тьюринга была ещё и в том, что он описал универсальный компьютер «общего назначения». Это революционная концепция. В то время компьютеры разрабатывались специально для определённых видов работ. Например, Вэнивар Буш со студентами в 1920-е годы придумал аналоговый компьютер, известный как дифференциальный анализатор. Он решал обыкновенные дифференциальные уравнения — и это было всё, что он делал.

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

Полнота по Тьюрингу

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

Другими словами, можно написать на Java или C++ программу, которая будет действовать как машина Тьюринга. «Полными» также являются и HTML5, и CSS3. А вот SQL не полный — на нём пишутся в основном запросы к базе данных, а не полноценные программы.

Примеры реализации

Несмотря на то что данная разработка — это мысленный эксперимент, нашлись энтузиасты, которые попытались сконструировать её физический прототип.

Пожалуй, наиболее впечатляющую модель воспроизвел Ричард Ридел. У него ушло на её создание шесть месяцев.

Другие умельцы реализовали машину Тьюринга в Excel:

При чём тут грибы?

Несмотря на то что машина Тьюринга была придумана почти 100 лет назад, эта концепция не только не устарела, но и используется сейчас. Робототехник Джошуа Бонгард и биолог Майкл Левин в своих работах предлагают уйти от узкого понимания компьютеров и рассматривать живые организмы тоже как вычислительные машины.

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

Кроме того, биологические системы эволюционируют и меняются со временем, что также усложняет применение к ним жёстких математических определений.

Но ничего лучше машины Тьюринга, похоже, не придумали, поэтому Бонгарду и Левину придётся найти, где у крабов лента, а где считывающая головка.