Машина Тьюринга
Немудреный скажет: «Какая кухня!»
Но кухня легко превращается в лабораторию.
Агни Йога т.1 стр.198
Что такое вообще – вычисление? Можно вычислять
«на палочках», как нас учили в первом классе или даже в детском саду, можно с карандашом
в руке на листе бумаги. Современный ученик или ученица фыркнут и скажут – нужно
взять калькулятор. Специалисты посерьезнее напишут программу для своих
вычислений, включат компьютер. Какое разнообразие: одним для вычисления
понадобятся несколько пальцев на руках, другим – решить дифференциальное
уравнение, «взять» интеграл и т.д. и т.п. Сказать вычислимость (или
невычислимость) – мало. Мол, решилась задача – вычислимость, не решилась –
невычислимость. Может быть, взявшийся за решение задачи человек, слабоват в
математике? Пригласим самых сильных – и нет невычислимости.
Напомним, что
несколько выше мы сказали, что существуют задачи, которые вообще невычислимы
(та же проблема Ферма). Как же узнать, что проблема не решаема, не вычислима,
или, как говорят математики – алгоритмически неразрешима? Не посадишь же сотню
самых сильных математиков – решайте, ребята, и пока не решите, будете сидеть на
сухарях и воде. Сто дней сидели на сухарях с водой – не решили. А на сто первый
день отыскался еще один, сильнее сильных, взял и «щелкнул». Как же быть, если
не найдется один, сильнее самых сильных? Если и тысяча и десять тысяч дней
пройдут, а задача ни с места? Нет, нужен какой-то иной надежный способ
определения невычислимости. Но для этого прежде нужно поточнее разобраться –
что же такое вычислимость?
Несколькими строками выше было упомянуто о
большом различии между вычислениями, например, «на палочках», или на
компьютере. Однако, нужно найти нечто общее, единое в самых различных
вычислениях. Это общее, единое и будет определением понятия
«вычислимость». Упомянутому нами ранее английскому математику Алану Тьюрингу
принадлежит открытие этого самого общего, единого, характеризующего
самые разнообразные вычисления.
Продолжается путешествие лайнера с гордым названием «Наука», и на палубе появляется незнакомое неспециалистам «устройство», с названием «Машина Тьюринга». Машина Тьюринга – «машина», придуманная им в первой трети XX столетия. В ней все вычисления сведены к небольшому набору весьма простых, однообразных операций. Мы слово «машина» взяли в кавычки по одной причине: это в обычном смысле не машина, например, из железа или электронных схем. Когда ее «изготавливают», то обычно рисуют или распечатывают на листе бумаги, иногда – программируют на компьютере (последнему есть мудреное название – эмуляция машины Тьюринга).
Сопоставим две совершенно непохожие задачи: домохозяйка в магазине подсчитывает на калькуляторе свои расходы за купленные продукты и расчет на современном компьютере траектории движения космического корабля. И там и там имеют место вычисления, но они настолько различны, что даже как-то «неудобно» их сравнивать. А почему? В одном случае используется последовательность элементарных арифметических действий (скажем, сложений и вычитаний), в другом – расчет по сложнейшим формулам. Часто же вычисления нужно сравнивать, сопоставлять. Даже существует такая научная дисциплина – теория алгоритмов, одна из целей которой – сопоставление алгоритмов, по которым ведутся вычисления.
Пришла пора рассказать, что понимается под
машиной Тьюринга (раскрыть ее «кухню») и почему для моделирования
вычислительных (а где-то невычислительных) способностей мозга мы предлагаем
подключить эту машину. У читателя возникает недоуменный вопрос: почему
мы, говоря о мозге, сложнейшем «устройстве», работа которого до сих пор до
конца не понята, вдруг заговорили о какой-то машине, придуманной Тьюрингом
давным-давно? Обычно ученые сопоставляют работу мозга с работой современных
суперкомпьютеров (вспомните о проекте Brain Blue!), и то – не находят ответов на многие интересующие их
вопросы. А тут вдруг мозг и какая-то машина Тьюринга! (Один из моих оппонентов,
человек явно мыслящий, обсуждая мою первую книгу «Феномен вечного бытия»
упрекнул меня, мол, на дворе суперкомпьютеры, микроэлектронные чипы, и вообще –
чудеса микробиологии, а автор – о «неонках и перфолентах»). Понять наш
дальнейший рассказ будет совсем не трудно, разве что читать скучновато.
Важно – не потерять нить, ибо никакой явной связи между машиной Тьюринга и
сознанием сразу не просматривается; ее нужно почувствовать, уловить. И то не
сейчас, а когда разглядим в машине Тьюринга кое-что необычное.
Представим себе ленту произвольной длины. Лента
вертикальными черточками разделена на равные участки, называемые ячейками. В
каждой ячейке может быть записан один символ (цифра, буква, знак препинания,
математический символ и прочее). Некий образец такой ленты изображен на рис.1
Рис. 1 Входное слово на ленте для
сложения чисел 5 и 3
Примечание: греческая буква «ламбда» у нас будет обозначать
пустую ячейку, в которой никакой символ не записан.
Последовательность символов на ленте будем
называть записью или словом. В нашем примере запись предлагает
решить элементарную задачу – сложить два числа. Под лентой размещается так
называемая головка ( положение ее у нас показано символом состояния машины – в данном случае
символ q0), способная читать
определенный символ в ячейке, или, стерев старый, записать в ячейку новый.
Также головка способна перемещаться вдоль ленты на одну позицию за один такт
работы машины Тьюринга влево или вправо. Можно считать головку неподвижной, а
за один такт на одну ячейку смещается лента (в этом случае влево, вправо
меняются местами). Кроме того машина Тьюринга (далее - МТ) должна иметь еще
одно принципиальной важности устройство – устройство управления.
Назначение устройства управления – задать машине правила записи-стирания
символов на ленте, правила движения головки (ленты), а также правила изменения
состояния машины. Создать (запрограммировать) МТ, фактически означает создать
ее устройство управления.
Устройство управление – это никакое ни
«железо», ни «электроника». Это – нарисованная (напечатанная) на листе бумаги
прямоугольная таблица. Мы уже уточнили, что представленную на рис.1 запись
можно трактовать как исходное задание машине решить задачу. Разработать таблицу
управления машины, если задание задано в общем виде, т.е. вместо цифр 5 и 3
будут любые цифры или числа десятичной системы счисления уже достаточно трудно.
Поэтому для примера изобразим таблицу управления МТ только для конкретной
записи, изображенной на рис.1. Такая таблица может выглядеть так, как показано
на рис.2.
Рис.2 «Устройство управления»
машины Тьюринга для сложения чисел 5 и 3
Примечание: Таблица для удобства размещения на странице разделена на две части – верхнюю и нижнюю. Для восстановления ее единства необходимо нижнюю часть «приклеить» справа к верхней.
Как понимать эту таблицу? Пусть до начала
работы головка находится, как показано на рис.1, под буквой «с», а машина пребывает
в начальном состоянии, обозначенным символом q0. Смотрим клетку
таблицы на пересечении строки с буквой «с» и столбца с символом q0. В этой клетке
записана последовательность (тройка) символов сRq0. Тройка символов –
это команда МТ. В данном конкретном случае эту тройку следует понимать так:
машина в ячейке, под которой расположена головка, сохранит букву «с» (точнее –
сотрет букву «с» и вновь запишет букву «с»); оставит машину в прежнем состоянии
q0 и сдвинет головку
(пусть движется головка) на один шаг вправо (буква R
от слова Right – вправо).
В начале следующего такта головка теперь
расположена под ячейкой с буквой «л». Смотрим в таблице строку с буквой «л» и
столбец с символом q0, т.к. машина по прежнему находится в состоянии q0. На их
пересечении – команда (тройка) уRq0. Нам уже понятно, что по этой команде буква «а» стирается,
на ее место записывается буква «у», машина по прежнему остается в состоянии q0, а головка вновь
сдвигается на один шаг вправо.
Читатель теперь без труда, самостоятельно, может
проследить как будет работать машина до момента, когда головка прочитает с
ленты символ «?». Очевидно, что вместо знака вопроса она запишет цифру 8. Следует только обратить внимание, что машина
теперь перейдет в состояние q1, а головка никуда не сдвинется (буква «H» от слова Halt – стоять).
Теперь по таблице легко проследить, что головка, ничего на ленте не изменяя,
будет двигаться влево (буква «L» от слова Left – влево) до тех пор, пока не окажется под пустой ячейкой (символ
«ламбда»). Здесь видно, что головка остановится и машина перейдет в состояние S (от слова Stop – останов).
Читатель может спросить – зачем нужно было после получения ответа (число 8) двигать головку вдоль всей ленты влево: результат же был получен раньше? В самом деле, можно было без этого обойтись, но для более строгой (в математическом смысле) трактовки работы МТ целесообразно головку в конце работы помещать относительно ленты там, где она была вначале. Наиболее внимательные обязательно заметят, что это требование нашей машиной нарушено: головка на одну позицию оказалась левее исходной. Исправить этот «недостаток» легко: достаточно команду-тройку lHS последней строки таблицы ( на рис.2) заменит командой-тройкой lRS. Слово-результат после окончания вычислений показано на рис.3.
Рис.3 Слово на ленте после окончания вычислений
Еще какой-нибудь придирчивый читатель обязательно скептически заметит: подумаешь – машина записала заранее известный результат, она его не вычислила, он был записан человеком, создателем таблицы. Стоило ли для этого «городить» машину? Отвечаем. Во-первых, пусть читатель, если он не только придирчив, но и внимателен, попробует «сгородить» машину хотя бы для произвольных одноразрядных слагаемых (сумма уже может оказаться двухразрядной). И, во-вторых, и это самое главное – в машине Тьюринга всевозможные математические (и не только математические) задачи оказались сведенными к сколь угодно длинной череде одних и тех же простейших операций: считать-записать символ, сдвинуть головку и перевести машину из одного состояния в другое. Всё!!! Это и есть общее, единое для любых, самых разных вычислений. Поэтому, в более строгой форме мы можем заявить – задача вычислима (существует алгоритм решения задачи), если существует машина Тьюринга, решающая эту задачу. В данном случае не важно – идет ли речь о подсчете на калькуляторе стоимости покупок в магазине, или расчете в компьютере траектории полета космического корабля. Разумеется, никто не будет использовать машину Тьюринга для решения даже самых простых задач. Неоспоримая заслуга Алена Тьюринга состоит в том, что он нашел единый (и достаточно наглядный) способ определения вычислимости.
Ладно, разобрались с принципом работы машины
Тьюринга. Теперь пора ответить на вопрос, как с ее помощью узнать
«вычислимость» или «невычислимость»? В элементарной задаче «5+3=8» (Рис.1) мы
не зря «прогнали» головку туда, где она была в начале. Правда, сразу чуть-чуть
проскочили нужную позицию, но потом поправились. Существует следующее
определение. Если в начале работы считывающе-записывающая головка занимала
определенное положение (у нас в примере, допустим, под первым символом входного
слова), если в процессе работы машина «прочитала» входное слово полностью (т.е.
обошла все символы входного слова, кстати, можно и по нескольку раз), если
останов машины произошел в исходном положении головки, то говорят – задача
решена, существует алгоритм ее решения, проблема вычислима.
Как узнать, что алгоритма нет, и проблема не вычислима? Очень просто – подходящих для решения данной задачи машин Тьюринга можно придумать много, но ни одна из них не сможет удовлетворить вышеприведенному определению вычислимости (алгоритма). Правильнее сказать: не придумывать надо, а доказать, что вышеуказанные требования не могут быть выполнены. Здесь возможно много вариантов: входное слово не будет прочитано целиком, головка остановится не в нужном положении, головка вообще никогда не остановится и будет бесконечно двигаться по одному и тому же участку ленты, головка «попытается» уйти за левую или правую границы ленты (как бы в бесконечность), машина встретится с такой командой (тройкой), которую не сможет «понять». Все это – признаки невычислимости. Вспомним, что из-за невычислимости нас не примут в гаванях «Алгоритм» и «Старый закон», идти в «Новый закон» мы пока как-то поостереглись, а в «God» курса даже не прокладывали. Так и мотаемся в открытом океане с обязательством «невычислимости» и странной «машиной» на борту. Мы ее не будем опускать в трюм, она нам еще понадобится…
Остерегайся, не остерегайся, а кроме, как в
«Новый закон» получается – идти некуда. Но на пути туда, у нас нет «новой
физики». Однако если бы она была, смущает меня нарушение одного малозаметного
для многих обстоятельства, известного под названием «принцип Оккама» (иногда
говорят – «бритва Оккама»). Бритва Оккама еще со средних веков известна, как
неписанный закон науки, гласящий – не преумножай сущностей. Это, конечно, не
закон, наподобие законов Ньютона или Ома и множества других законов физики и
прочих наук. Но, как показывает история развития наук в течение нескольких
столетий, «бритва Оккама» срабатывала как бы сама собой. Это не означает, что в
науку новые сущности не вводятся. Еще как вводятся! Но введение новой сущности
– это, как правило, смена научной парадигмы. И тут, вопреки естественной
устремленности науки вперед, обязательно должен проявиться также свойственный
ей консерватизм.
В нашем
примере не вводить новых сущностей, значит, пытаться «отшвартоваться» в гаванях
«Алгоритм» или «Старый закон». Но туда из-за опасного груза невычислимости нас
не пустят. Однако с новой сущностью в форме «новой физики», двигаясь в сторону
«Нового закона», мы вступим в противоречие с принципом Оккама. Нетрудно
сообразить, что противоречие легко преодолевается (снимается), если принять иную
трактовку позиций Пенроуза.
Нам нелегко сделать этот шаг: Р.Пенроуз –
маститый ученый, обладающий чувством глубокой интуиции, что, в свою очередь,
является признаком большого и глубоко ума. Не прислушаться к его мнению –
высока вероятность совершить ошибку в самом начале нашего пути. И все-таки, и
все-таки… Наша интуиция, подсказывает, что если исходить из эволюционного
развития сознания от его несуществования к сознанию человека, то самые исходные
зачатки сознания не могли быть очень сложными, чтобы требовать своего, как
пишет Р.Пенроуз, квантового выполнения. Неужели у какой-то амебы, или более
«продвинутого» в смысле своей «сознательности» червяка их «нервные» процессы
идут уже на квантовом уровне? Очевидно,
что поведение этих весьма простых представителей животного мира может быть
описано на уровне совсем не сложных вычислительных моделей.
Несколько ниже мы подойдем к формулировке
научной гипотезы, что даже для сознания человека можно предложить «как бы
вычислительную» модель, которая позволит сказать – что же такое
представляет собой сознание? Другое дело, что описываемая ниже модель не
поможет ответить на другой вопрос: как это такое реализуется в
материальном мозге? Однако продвижение в построении ответа на первый вопрос –
важный шаг к нахождению ответа на второй.
Итак, руководствуясь принципом бритвы Оккама и
соображениями эволюционного развития сознания, мы задаем следующий вопрос:
можно ли объединить особым образом позиции «A»
и «B» (по Пенроузу) и поискать новую, подходящую для швартовки
бухту, сообразно нашей сюжетной линии? Так уж и быть, скажем: «Слава, Богу»,
ибо такую бухточку наш штурман отыскал, и мы тут же дали ей название «Машина
Тьюринга».
Связались по радио и получили следующий ответ,
над которым долго ломали голову: В нашей бухте мы разрешим бросить якорь,
если ваш корабль с названием «Наука»,
удовлетворяет следующему определению сознания – сознание есть
функция деятельности мозга по известным физическим законам. Эти законы можно
перевести в некую компьютерную форму, точнее – машину Тьюринга, которая при
определенных режимах своей работы не будет соответствовать никакому алгоритму,
т.е. – перестанет быть машиной Тьюринга.
- Час от часу не легче, – тихо процедил сквозь зубы какой-то матрос из нашей, готовой взбунтоваться, команды. – Наш капитан вознамерился «бритвой Оккама», отсечь «новую физику», как лишнюю сущность, а они (тут матрос махнул рукой в сторону уютной бухточки) требуют, чтобы мы незаметно приклеили другую – «определенный режим работы». И волки сыты, и овцы целы. Что же такое, братцы, машина Тьюринга, оставаясь машиной Тьюринга, должна перестать быть машиной Тьюринга? Кошмарный сон, да и только! Чем же она становится? Явно – назревал бунт. Матросню удалось успокоить разъяснением (пока для нас не совсем понятным), что машина Тьюринга, которая перестает быть машиной Тьюринга – это еще не известный науке преобразователь информации.
При попытке получить по радио приписку к бухте, названной нами «Машина Тьюринга», между начальником порта (НП), оказавшимся на том конце линии связи, и капитаном нашего лайнера (КЛ) произошел неприятный для последнего обмен мнениями. Впрочем, закончился он вполне благополучно.
НП: Вам известно, что получить право на приписку к нашей бухте имеет только то судно, на борту которого имеется «невычислимость»?
КЛ: Да, известно.
НП: Предъявите, пожалуйста, Вашу невычислимость. Поясняю, что речь идет о невычислимых способностях Вашей «машины Тьюринга».
КЛ: Проще простого. То есть, я хочу сказать, что это совсем не просто. Невычислимости бывают разные – «правильные» и «неправильные». У нашей машины Тьюринга – «правильная» невычислимость.
НП: Что-то вы, капитан, говорите непонятное. Укачали вас, наверное, шторма?
КЛ: Совсем наоборот – приободрили. «Правильная невычислимость» возникает тогда, когда машина сталкивается с алгоритмически неразрешимой проблемой. Все остальное – «невычислимость неправильная»: задача может быть решена, но из-за каких-то причин возникла ошибка в вычислениях.
НП: Странно, в математике такого разделения «невычислимостей» нет. Ну, да ладно, пусть будет по вашему. Расскажите кратко о вашей, как вы называете, «правильной невычислимости».
КЛ: Если кратко, то попробуйте развернуть двумерную таблицу машины Тьюринга в одномерную запись и подайте эту запись на вход этой же самой машины.
НП: Гмм. Это нечто экзотическое. Для меня, если честно, ваша попытка заставить машину «читать саму себя» – некая искусственно подстроенная уловка. Вот что пишет известный американский мэтр в области кибернетики Марвин Минский: «Что случится, если машине сопоставить ее собственное описание? Можно ожидать, что машина будет «парализована», потому что он будет бесконечное число раз повторять интерпретирующие циклы и никогда не сможет произвести какого-либо вычисления. Сперва такие явления кажутся занимательными, потом они начинают раздражать, и, наконец, мы вынуждены сделать вывод, что они свидетельствуют о непреодолимых препятствиях на пути нашего исследования». Вы что, решили нас развлечь любопытными фокусами? Фокусы уместны на эстраде.
КЛ: Что вы, какая эстрада, какие фокусы!? Исключительно научное любопытство.
НП: Я в детстве тоже хотел проявить «научное», как вы изволили выразиться, любопытство. Решил подрезать у мухи крылья и посмотреть – взлетит ли.
КЛ: Ну и как – взлетела?
НП: Нет, не взлетела, муху раздавил.
КЛ: Вот видите, научное любопытство очень часто приводит к неожиданным результатам. Вы же не хотели раздавить муху?
НП: Я только хотел подрезать ей крылья, чтобы увидеть, как мушиная мощность прикладывается к облегченным крыльям.
КЛ: А мы хотим преодолеть препятствие, которое М.Минский назвал «непреодолимым». Ну, как, припишите?
НП: Да.
Блуждание между портами и разговор я, разумеется, придумал, вообразил. Но за воображением кроется серьезный вывод: пока еще можно попытаться обойтись без «новой физики» и непонятность сознания поискать в границах существующей научной парадигмы.
Всем известно, что из ванн вместе с водой
иногда выплескивают детей. Мы позицию
Пенроуза «C» обкромсали «бритвой Оккама»
(выплеснули ребенка). А был ли мальчик-то? (Это – крылатая фраза из романа
М.Горького «Клим Самгин»). Точно, был! Это – «новая физика». По русской грамматике – физика, правда,
девочка. Девочка тоже ребенок. А была ли девочка? Мы точно знаем – у Р. Пенроуза была. Правда, мы кое-что, в
виде «правильной невычислимости» (тоже девочки) к машине Тьюринга, добавили.
Девочки обычно нечто теряют, а здесь, надо же – приобретение, заключающееся в
дополнительном, особом свойстве, заставившем машину Тьюринга «читать саму
себя». Мы еще не дали этому свойству какого-то названия; остановимся на
нем подробнее в следующем разделе, т.
к. в дальнейшем, при изложении темы сознания, оно, на наш взгляд, будет играть
определяющую роль.
