Агниджо Банерджи - Эта странная математика. На краю бесконечности и за ним

По оригинальному описанию Тьюринга был даже сконструирован целый ряд реальных машин – в основном в качестве экспериментов по проектированию или для демонстрации работы простейших вычислительных устройств. Несколько машин было построено из деталей LEGO, в том числе одна – из конструктора LEGO Mindstorms NXT для создания программируемого робота. А вот рабочая модель, созданная изобретателем из штата Висконсин Майком Дэйви, напротив, “воплощает в себе классические эстетичность и функциональность описанной Тьюрингом машины” и сейчас находится в постоянной экспозиции Музея истории компьютеров в городе Маунтин-Вью (штат Калифорния).

Модель машины Тьюринга, построенная Майком Дэйви в соответствии с оригинальной идеей Алана Тьюринга.

Как уже упоминалось, свое изящное устройство Тьюринг придумал специально для того, чтобы дать ответ на проблему разрешимости, сформулированную Гильбертом, что он и сделал в своей статье 1936 года, озаглавленной “О вычислимых числах применительно к Entscheidungsproblem ”. Если ввести в универсальную машину Тьюринга произвольные входные данные, она может либо остановиться, либо продолжать работать бесконечно. Тьюринг задался вопросом: возможно ли определить, остановится она или нет? Можно, конечно, запустить ее на неопределенное время и посмотреть, что произойдет. Но если после долгого ожидания вы решите досрочно прекратить эксперимент, не дождавшись результата, то так и не узнаете, остановилась бы машина сразу после этого этапа, гораздо позже либо продолжала бы работать бесконечно. Разумеется, для конкретных случаев просчитать результат можно, как мы в силах выяснить, остановится ли когда-нибудь простая машина Тьюринга. Однако Тьюринг хотел знать, существует ли общий алгоритм, способный для любых входных данных определить, остановится машина или нет. Эта задача получила название “проблема остановки”, и Тьюринг доказал, что такого алгоритма не существует. Далее, в заключительной части своей статьи, он показал, что отсюда следует вывод о неразрешимости Entscheidungsproblem . А это значит, что мы можем быть абсолютно уверены: никакая самая совершенная компьютерная программа не сумеет – во всех случаях – определить, завершит ли когда-нибудь свою работу какая-либо иная программа.

За месяц до выхода исторической статьи Тьюринга американский ученый-логик Алонзо Чёрч, его научный руководитель, независимо опубликовал собственную статью, в которой делал тот же вывод, но для доказательства использовал совершенно другой метод – лямбда-исчисление. Так же как и машина Тьюринга, лямбда-исчисление представляет собой универсальную вычислительную модель, но скорее программную, а не аппаратную; она оперирует “комбинаторами” – функциями, которые применяются к другим функциям. И Чёрч, и Тьюринг, пользуясь каждый своим методом, пришли, в сущности, к одному и тому же результату, получившему название “тезис Чёрча – Тьюринга”. Суть его в том, что человек способен высчитать или оценить количественно (такую мелочь, как ограниченность ресурсов, мы при этом в расчет не берем) только то, что вычислимо с помощью машины Тьюринга или равнозначного ей устройства. “Вычислимость” означает, что машина Тьюринга, если подать ей на вход программу (в двоичном представлении), способна работать до тех пор, пока не остановится, дав на выходе ответ (в таком же двоичном представлении). Основной вывод, следующий из тезиса Чёрча – Тьюринга, заключается в том, что общего решения Entscheidungsproblem не существует.

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

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