Самоприменимость машины Тьюринга

Можно, не изменяя принципам,

найти сотни достойных решений

Агни Йога (т.1 стр.196)

Какая странность – машина Тьюринга это всегда вычислимость, а нас к бухте «машина Тьюринга» прописали только потому, что у нас на борту есть некая невычислимость. Если ответить коротко, то невычислимость обнаруживается тогда, когда какая-то задача не имеет решения. Теперь подробнее об одном из способов достижения невычислимости.

Рассмотрим пример, но не тот, что раньше (там задача была элементарна, а таблица машины оказалась достаточно громоздкой), а проще. Нас будет интересовать в качестве примера машина Тьюринга, инвертирующая двоичный код. Скажем, на ленте дана входная запись 011001, после работы машина должна записать на ленте код 100110, т.е. нули должны замениться единичками, а единички – нулями. Таблица такой машины – весьма проста.

	q₀	q₁
0	1Rq₀	0Lq₁
1	0Rq₀	1Lq₁
l	lLq₁	lRS

Рис.4

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

Как из данной в примере машины Тьюринга «извлечь» невычислимость? Первое, что приходит в голову – подать на ленту в качестве входного слова, что-нибудь этакое, что она не сможет воспринять, например, вместо нулей и единичек в качестве входного слова на ленте записать последовательность букв, скажем – abbbaa… (не «ломать» же ради невычислимости машину!). Все! Комбинацию «aq₀» в самом начале работы она уже не «понимает», нет такой комбинации. А не понимая, не может выполнить никакой команды: ни записать-стереть символ, ни сдвинуть головку вправо-влево, ни изменить состояние. Машина «парализована», задача для такой машины оказалась невычислимой. Правда, смущает одно обстоятельство. Мы машину ни коим образом не изменяли, а подали на ее входную ленту нечто для нее «непотребное». Это все равно, что залить в бак вместо бензина молоко и желать, чтобы автомобиль поехал. Нет, нужно подать на ленту нечто машине «знакомое», так сказать – взятое из ее существа.

Попробуем провести над машиной странную операцию: развернем нашу двумерную таблицу (например, слева направо и сверху вниз) в одномерную запись. Правильно – у нас получится:

01Rq₀q₀00Lq₁q₁10Rq₀q₀11q₁Lq₁q₁llLq₁q₀llRSq₁

Напоминаю, что символ l обозначает пустую ячейку. А теперь предъявим машине для чтения на ленте эту одномерную запись. Все символы ее взяты не из воздуха, а из «существа» машины.

01Rq₀q₀00Lq₁q₁10Rq₀q₀11q₁Lq₁q₁llq₁ q₀LllRSq₁

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

10Rq₀q₀00Lq₁q₁10Rq₀q₀11q₁Lq₁q₁llLq₁q₀llRSq₁

В этой ситуации машину ожидает большая неприятность: головка читает с ленты символ R. А в левом столбце таблицы рис.4 (столбце входных символов) такого символа нет. Машина этот символ «не понимает». И поэтому, она не «знает», что делать дальше. Куда двигать головку, какой символ стирать-записывать на ленте, в какое состояние переходить: команды «на этот случай жизни» у машины нет. Мы столкнулись с ранее рассмотренной ситуацией, когда машине Тьюринга предложили для чтения незнакомые символы. Но тут, казалось бы, случай другой: машина «столкнулась» с символом, взятым из ее же «тела», из ее собственной записи. Если воспользоваться предыдущей аналогией «бензин-молоко», то она до некоторой степени похожа на ситуацию «бензин - тосол» (тосол – это уже нечто автомобильное). Да, символ R принадлежит «телу» машины, но чтобы она могла его «понять», необходимо его вхождение не только в команду-тройку, но и в строку входных символов ее таблицы. Чуть ниже мы попытаемся это сделать, а сейчас назовем ситуацию, когда машине предъявляется для чтения собственная запись режимом самоприменимости.

Что, тупик? В данном примере, да. Основное условие правильной работы машины Тьюринга нарушилось: алгоритм не реализуется, и машина Тьюринга… перестала быть машиной Тьюринга! Виновата в этом введенная нами самоприменимость. Мы пока еще не знаем хороша ли самоприменимость или плоха: об этом в свое время, дальше мы будем говорить достаточно подробно. Пока лишь зафиксируем наше «достижение»: и невычислимость возникла в виде особого режима работы машины Тьюринга, но и сохранилась сама машина с ее способностью моделировать лишь вычислимые процессы (в примере – инвертировать двоичный код), когда режим самоприменимости отключен.

Читатель, наверное, обратил внимание, если текст читал, а не бегло просматривал, что когда мы развертывали двумерную таблицу машины в одномерную запись, то предложили развертку выполнить слева направо и сверху вниз. Почему, чем эти направления предпочтительней других, например, снизу вверх и справа налево, ведь тоже получится одномерная запись? Или развертывать в шахматном порядке? Вспомним, что одномерная запись таблицы – это тоже «таблица» её самоё. Однако, если двумерная таблица имеет один и тот же вид, то одномерные записи при разных направлениях развертки будут разными. И когда машина, будучи поставленной в режим самоприменимости, будет читать эти разные записи, не будет ли она «думать», что она «знакомится» с разными машинами. Какая из них – она сама?

Нам остается предположить, что дело не в направлении развертки, а в чем-то другом, ибо речь идет все-таки об одной и той же машине. Окинем более внимательным взором таблицу на рис.4. Не трудно представить, что символы левого столбца таблицы (у нас это символы – 0, 1, l), можно трактовать как входные символы ленты, когда машина работает как инвертирующая машина без всякой-там самоприменимости. А символы q₀, q₁, S, L, R – это символы, принадлежащие самой машине, иными словами – ее внутренние символы. Я чувствую, что наиболее дотошный читатель уже начал догадываться – куда (или откуда) дует ветер. В самом деле, когда машина начинает работать в режиме самоприменимости (кто включает этот режим, сейчас неважно), ей приходится обрабатывать две группы символов: внешние (из внешнего мира!) и внутренние (из своего внутреннего мира!). Здесь совершенно неважно – в каком направлении была осуществлена развертка; важно, что количественное соотношение между внешними и внутренними символами при любом способе развертки остается неизменным. Машина в режиме самоприменимости с легкостью «разбирается» с внешними символами (еще бы – для этого машина и создавалась, чтобы инвертировать единички и нолики!), а встретившись с внутренним символом – «затыкается».

Всякая ли машина Тьюринга несамоприменима? Далеко не всякая. Вот, например, та же инвертирующая машина, которую мы «превратили» в самоприменимую.

	q₀	q₁	q₂
0	1Rq₀	0Lq₁	0Hq₂
1	0Rq₀	1Lq₁	1Hq₂
l	0Lq₁	lRq₂	lHq₂
H	HRq₀	0Rq₀	HHq₂
q₂	q₂Rq₀	1Rq₀	q₂Hq₂
q₀	q₀Rq₀	q₀Lq₁	q₀Hq₂
q₁	q₁Rq0	q₁Lq₁	q₁Hq₂
L	LRq₀	LLq₁	LHq₂
R	RRq₀	RLq₁	RHq₂

Рис. 5

Очевидно, из нашего примера с машиной на рис.4, машину нужно было научить понимать внутренние символы L,R,H, q₀, q₁, q₂ (здесь для однообразия символики прежнее состояние останова S мы обозначили символом q₂). Естественно, при появлении новых входных символов, должны были появиться новые клетки таблицы. Их нужно было заполнить какими-то командами (тройками), чтобы машина «знала», что нужно делать, когда головка читает новый входной символ. (Мы сочли нужным добавить в таблицу еще один, третий, столбец, соответствующий состоянию останова q₂, хотя этого можно было и не делать). Так вот, по поводу слова «превратили». Как заполнять новые клетки, чтобы наша инвертирующая машина стала самоприменимой?

Здесь приходится сообщить «любителям самоприменимости» «принеприятнейшую новость»: доказано, что проблема самоприменимости машины Тьюринга алгоритмически неразрешима. Это означает, что нет алгоритма (способа), с помощью которого можно было однозначно сказать – находящаяся перед вами машина Тьюринга самоприменима или нет. Или иначе – как создать самоприменимую машину Тьюринга? Здесь даже не помогает то обстоятельство, что вы «научите» машину «понимать» ее внутренние символы. Остается единственный способ: «запустить» машину и посмотреть – самоприменима или нет. Самоприменима – значит, остановится. А если что-то долго не останавливается; вам уже надоело ждать? Вы смотрите на часы, вас ждут другие дела. Можно остановить машину принудительно, так и не дождавшись ответа о ее свойствах. Обидно, если вы не дождались всего каких-то пару минут, и пара часов ожидания потеряна напрасно. Нельзя ли сразу узнать, еще до запуска машины – остановится она или нет. Тут новая незадача – проблема останова машины Тьюринга тоже алгоритмически неразрешима: в общем случае по внешнему виду ее таблицы нельзя сразу сказать – остановится или нет.

Вот почему мы выше и написали – «превратили». Заполнили таблицу, руководствуясь какими-то интуитивными соображениями, «запустили», посмотрели. Сразу понятно, что сделать это «в ручную» даже для такой сравнительно небольшой таблицы, как на рис.5, было невозможно: легко видеть, что после развертки такой таблицы ее одномерная запись содержит 135 символов. Естественно, наша машина Тьюринга была промоделирована на обычном компьютере. И то, пока какой-то вариант машины остановился (по всем правилам) – значит, самоприменима – головка сделала свыше 5000 шагов туда-сюда вдоль записи, состоящей из этих 135-ти входных символов.

Ну, вот – какой-то вариант оказался самоприменимым (машина остановилась), значит невычислимости все-таки нет? Не будем спешить: сам вариант «появился» посредством невычислимости! Мне, скажем повезло, что «придумалось» за относительно короткое время. А если бы «не придумалось»? Нельзя исключать из рассмотрения и такой момент: для какой-то специализированной машины Тьюринга ее самоприменимый вариант «создать» нельзя по одной простой причине: такого варианта не существует в принципе. Узнать же, что его не существует, невозможно из-за алгоритмической неразрешимости самоприменимости машины Тьюринга.

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

Размышляя над «уловкой» капитана нашего корабля, я все время задаю себе вопрос. Почему он ввел какой-то непонятный режим работы машины, заставляя ее «читать саму себя»? Не проще ли было взять любую известную алгоритмически неразрешимую проблему, и сказать: «пожалуйста, вот вам невычислимость»? Может быть, это был просто нетрадиционный ответ на нетрадиционную же и озорную идею подрезать мухе крылья? Все может быть. Но сдается мне, что тут была заложена более глубокая мысль. Машина Тьюринга была выбрана в качестве основополагающей модели, если угодно – путеводной звезды – на пути к постижению сознания. Значит, нужно «выжать» из этой модели все, что возможно и даже – невозможно. Мы, естественно, знали сетования М.Минского по поводу самоприменимости УМТ – мол, там непреодолимая и раздражающая трудность. Поэтому искать нужно там, где трудно: плохо спрятанное легко найдет любой. Сущность сознания спрятана очень хорошо. Капитан не стал затруднять себя вопросом – кто-то спрятал, или само спряталось? Нужно искать, а там жизнь подскажет – где холодно, где тепло, а где совсем горячо.

К содержанию

Вперед