Невычислимое

Мы можем рассматривать компьютерную программу, как устройство, которое берет на вход набор целых чисел и выдает на выходе другой набор целых чисел. Компилятор языка C#, например, принимает на вход строки исходного кода, а это всего лишь набор огромных двоичных чисел. На выходе компилятора мы получаем либо диагностический текст, или строки IL-кода и метаданных, которые, опять-таки, всего лишь огромные двоичные числа. Поскольку компилятор не идеален, иногда его работа завершается аварийно с внутренними сообщениями об ошибках. Но эти сообщения об ошибках, также являются лишь огромными двоичными числами. Поэтому давайте возьмем за основу компьютерной программы следующую простую модель: компьютерная программа – это устройство которое, либо (1) бесконечно исполняется, не выдавая ничего на выходе, либо (2) вычисляет функцию соответствия одного целого числа другому.

Вот интересный вопрос: существуют ли такие функции, которые невозможно вычислить даже в принципе на компьютере с произвольным размером хранилища, с помощью любой программы на языке C# (*)?

Мы уже знаем ответ на этот вопрос. В прошлом году я указывал на то, что Проблема Останова не решаема ни одной компьютерной программой, поскольку даже предположение о том, что она решаема, ведет к логическому противоречию. Но Проблема Останова – это всего лишь функция на целых числах. Давайте скажем, что на вход нашей функции H поступает число, которое после записи в виде юникодной строки может содержать программу на языке C#. На выходе мы получаем 1, если программа является некорректной программой на языке C#, 2 – если программа корректна и когда-либо завершается, и 3 – если программа корректна и выполняется бесконечно. Если бы было можно написать программу, которая надежным образом вычисляла бы функцию H и всегда завершалась, тогда ее можно было бы использовать для решения Проблемы Останова, что, как известно, невозможно. Таким образом, H является невычислимой функцией.

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

Без потери общности, давайте предположим, что внешнее хранилище машины Тьюринга может хранить произвольно большое количество битов, либо нулей, либо единиц, и что внутреннее хранилище позволяет хранить фиксированное количество битов, например, n. Это достаточно серьезные ограничения, но они не являются фундаментальными. Настоящие компьютеры, конечно же, манипулируют данными, представляющие собой 32-разрядные целые или 64-разрядные числа с плавающей точкой, и тому подобное, но на некотором уровне внутри процессора, все равно происходит манипуляция на уровне битов. Нет принципиальной разницы между машиной, манипулирующей одним битом в один момент времени и машиной, манипулирующей 64 битами; второй вариант просто более удобен.

Так какое количество правил нам нужно для описания нашей машины Тьюринга? Машина Тьюринга с n битами, описывающими внутреннее состояние может иметь 2^n возможных состояний, а также существует два возможных значения «текущей позиции» во внешнем состоянии. (**) Таким образом, у нас есть 2^(n+1) правил перехода между состояниями. Каждое правило перехода должно кодировать три вещи: (1) чему равны n бит нового внутреннего состояния? (2) на какое значение должно измениться внешнее состояние? и (3) как мы должны обновить текущее положение?

Опять-таки, без потери общности, давайте предположим, что обновление текущей позиции осуществляется таким образом: увеличение значения на единицу, уменьшение значения на единицу или использование старого значения. На практике это было бы неудобно, но в принципе этого достаточно. Итак, у нас есть три варианта. Тогда каждое правило изменения состояния имеет 2 x 2^n x 3 вариантов при наличии 2 ^ (n + 1) правил перехода. Таким образом, общее число возможных машин Тьюринга, с n битами внутреннего хранилища, равняется 3 x 2 (n + 1) в степени 2 ^ (n + 1), что, да, приводит к очень быстрому росту при увеличении n, однако все равно, является конечным числом.

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

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

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

Вычислима ли функция S ? Можем ли мы написать компьютерную программу, вычисляющую эту функцию?

Интуиция должна подсказывать, что «нет», но можете ли вы сказать почему?

.

.

.

.

.

.

.

.

.

.

Потому что, если функция S вычислима, то функция H тоже должна быть вычислимой! Все, что нам нужно для вычисления функции H, это создать компьютерную программу, которая будет компилировать указанную программу на языке C# в симулятор машины Тьюринга, исполняемой на пустом внешнем хранилище. Мы берем количество битов состояния n машины Тьюринга и вычисляем S(n). Затем мы запустим симулятор машины Тьюринга, и если это потребует более S ( n ) шагов, тогда мы знаем, что это одна из n -битовых машин Тьюринга, которые исполняются вечно. Таким образом, мы сможем надежно вычислить H за конечное время. А поскольку мы знаем, что функция H не может быть надежно вычислена за конечное время, тогда мы знаем, что функция S также не может быть исполнимой.

Приведенные мной здесь аргументы известны как «задача усердных бобров» (Busy Beaver), поскольку n-битовая машина Тьюринга исполняется столько, сколько работает «самый усердный бобер». Я несколько изменил привычный способ представления этой проблемы; обычно «самый усердный бобер» представлен как машина Тьюринга с k состояниями и максимальным выходным результатом, а не как n -битовая машина, которая исполняется дольше всего до останова. Хотя две главные характеристики остаются теми же самыми; обе версии такой функции невычислимы.

Интересным фактом о функции «усердных бобров» (как бы вы ее не представили) является то, что она растет чрезвычайно быстро. Представить себе подобную функцию легко; даже простые функции, такие как n! или 2^n растут невероятно быстро даже для относительно небольших значений n, таких как 100. Но наша функция «усердных бобров» S(n) растет быстрее любой вычислимой функции. Т.е. подумайте о быстрорастущей функции, для которой вы можете написать программу для ее вычисления за конечное время; функция «усердных бобров» растет быстрее этой функции, не важно, насколько хитроумную быстрорастущую функцию вы бы ни придумали. Вы знаете, почему это так? У вас есть вся необходимая информация, чтобы ответить на этот вопрос. (****)

(*) Конечно, здесь нет ничего особенного в языке C#; это всего лишь язык общего назначения. Мы отталкиваемся от предположения, что если существует функция, которую невозможно вычислить на языке C#, то ее нельзя вычислить ни одной программой, ни на одном другом языке программирования.

(**) Конечно, нам не нужен переход из конечного состояния, ну да ладно. Давайте проигнорируем эту малозначительную деталь.

(***) Конечно, может существовать несколько одинаково длинных результатов, но это не имеет значения.