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

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

Затем Тьюринг создал в своем воображении особый вид вычислительной машины, известный сегодня под названием “универсальная машина Тьюринга”. Теоретически она была способна выполнять любую программу. Лента ее разделена на две части: на одной закодирована программа, на другой содержатся входные данные. Головка чтения-записи универсальной машины Тьюринга может перемещаться между этими частями и выполнять над входными данными операции в соответствии с командами, записанными в программе. Устройство предельно просто: бесконечно длинная лента, на которой содержится как программа, которую следует выполнить, так и входные и выходные данные, плюс головка чтения-записи. Машина может выполнять всего шесть простых операций: считывание, запись, перемещение влево, вправо, изменение состояния и остановка. Но, несмотря на эту простоту, возможности универсальной машины Тьюринга поражают воображение.

У вас наверняка есть хотя бы один компьютер. Неважно, какая на нем операционная система – какая-нибудь из версий Windows, Mac или Android либо иная, скажем, Linux . Производители любят подчеркивать преимущества и особенности своих операционных систем, выгодно отличающие их от конкурентов. Но с точки зрения математики при наличии достаточной памяти и времени все эти различные системы абсолютно идентичны. Более того, все они – полные эквиваленты той самой универсальной машины Тьюринга. Пусть на первый взгляд она и кажется чересчур примитивной, да и по эффективности не ровня мощным машинам нашего времени, но вот по своим возможностям она ничем не хуже любого современного компьютера.

Изобретение универсальной машины Тьюринга привело к возникновению такого понятия, как эмуляция. Говорят, что один компьютер способен эмулировать некий другой, если он может выполнять программу (называемую эмулятором), которая фактически превращает его в этот другой компьютер. Например, компьютер, работающий под управлением операционной системы Mac OS , может выполнить программу, которая заставит его вести себя так, как если бы на нем была установлена система Windows , – правда, на это требуется много оперативной памяти, а обработка данных происходит медленно. Если подобная эмуляция возможна, два компьютера считаются математически эквивалентными.

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

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

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

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

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