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

• Эту теорему доказали (с условиями и ограничениями) итальянские ученые Бём и Якопини, а Дейкстра лишь ссылался на неё.

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

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

А вот теперь настало время написать про некоторые проблемы машины Тьюринга - фундаментальной основы всех информационных технологий.

Зачем?

Поводом для текущей статьи стал мой диалог с одним пользователем на Reddit при обсуждении статьи Гарантии языка программирования как основа безопасной разработки программного обеспечения (там я тоже получаю обратную связь от читателей, как на Хабре, только от англоязычной аудитории).

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

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

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

Каково бы ни было разумное понимание алгоритма, любой алгоритм, соответствующий такому пониманию, может быть реализован на машине Тьюринга.

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

Из-за этого машина Тьюринга (а следовательно, и любой компьютер, который мы можем себе представить) не позволяет сделать некоторые вещи:

• Решить невычислимые задачи - те, для которых в принципе не существует алгоритма. Неважно, сколько времени или памяти мы дадим машине, она никогда не сможет гарантированно дать правильный ответ для всех возможных входных данных.

• Невозможно создать программу, которая проанализирует любую другую программу и её входные данные и скажет, завершится ли эта программа когда-нибудь (остановится) или будет работать вечно (зациклится). Кстати, скорее всего, это и подтверждают слова Э. Дейкстры: «Тестирование выявляет только наличие, но никак не отсутствие ошибок».

• Решить NP-трудные задачи за разумное время.

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

• Мысленный эксперимент "Китайская комната", показывает, что машина Тьюринга не позволяет "создать понимание" или "сознание" в человеческом смысле, она лишь симулирует его внешние проявления.

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

Если вам интересна эта тема, рекомендую почитать Surprisingly Turing-Complete · Gwern.net или её перевод Неожиданная полнота по Тьюрингу повсюду - Хабр.

Причём тут машина Тьюринга?

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

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

• Интересен и обратный вывод: полнота языка программирования по Тьюрингу является достаточным основанием, чтобы такой язык программирования нельзя было отнести к безопасным :-)