Эксперименты с ИМТ
Если долго портить
машину, она сломается.
Закон Шмидта
Вернемся к испорченной машине Тьюринга, предварительно договорившись, какую из правильно работающих машин мы будем «ломать». Удобно с этой целью остановиться на уже знакомой нам машине – инвертору двоичного кода. Часто в науке, когда заранее не известно, что же произойдет на том или ином повороте исследования, приходится использовать так называемый, по-просту говоря, «метод тыка»: попробовали «так» – получили «этак», попробовали «этак» – в результате получили «так». По научному говоря – метод проб и ошибок. Вот мы для начала из огромного множества всевозможных машин Тьюринга «ткнем» в инвертор. Но и здесь вопрос – что и как ломать? Понятно, что в абстрактной таблице поломка сводится к изменению символов таблицы: вместо одних символов писать другие, а также изменять местоположение символов в тройках. От второго предложения мы сразу же откажемся, т.е. не будем, например, вместо символа движения головки записывать символ состояния машины: слишком грубая поломка, машина тут же «заткнется», встретив подобным образом испорченную команду. Возьмем для начала неисправность «потоньше».
На следующем таблице изображен знакомый нам «инвертор», ИМТ-1. На первый взгляд поломки и не видно: именно невидимые с первого взгляда неисправности во многих случаях жизни вызывают наибольшую досаду – все, казалось бы, исправно, а не работает, или работает не так, как нужно.
|
|
q0 |
q1 |
|
0 |
1R q0 |
0L q0 |
|
1 |
0R q0 |
1L q1 |
|
l |
lL q1 |
lR q2 |
Присмотревшись чуть внимательнее, замечаем, что в команде второй строки третьего столбца вместо символа q1 записан символ q0 – машина перешла не в то состояние, в которое было бы нужно. Каким образом обнаружить неисправность, проявит ли она себя? Один из ответов, который приходит в голову, «построить» такую ИМТ, и начать подавать на ее вход различные двоичные коды. Делать это в уме или на бумаге – пустая трата времени: сами тут же ошибёмся. В моем распоряжении оказалась (написали студенты) программа, эмулирующая произвольную машину Тьюринга. Я ввел в программу эмулятора мою ИМТ-1, и получил следующие результаты:
а) при подаче на вход кода 111…111 (все единицы), машина останавливается, но вместо нужного кода 000…000 выдает не верный результат.
б) при подаче на вход кода 000…000 машина останавливается и выдает правильный результат 111…111.
в) при подаче на вход кода с чередующейся последовательностью единичек и нулей (например, вида 101010…101010), машина не останавливается, и, следовательно, не выдает ни какого результата.
г) при подаче на вход нерегулярной последовательности единичек и нулей (вида, например, 1011010…0110) машина в зависимости от нерегулярности то может остановиться, то нет, но даже при остановке ответ оказывается не верным.
На следующей таблице представлен иной способ поломки «инвертора – ИМТ-2 (в команде третьей строки третьего столбца вместо символа L записан символ R), а первоначальная
|
|
q0 |
q1 |
|
0 |
1R q0 |
0L q1 |
|
1 |
0R q0 |
1R q0 |
|
l |
lL q1 |
lR q2 |
поломка также осталась – наш «инвертор» оказался дважды поломанным. Результаты испытания следующие:
а) входной код – одни единицы, инвертор останавливается и выдает на удивление правильный результат.
б) достаточно во входном коде появиться хотя бы одному нулю, «инвертор» через какое-то время входит в бесконечный цикл, результата, естественно, не наблюдается.
Не будем утомлять читателя другими поломками, да в различных сочетаниях с видом входных кодов (очевидно, что всевозможных комбинации даже для простого инвертора можно придумать весьма много, не говоря о более сложных машинах Тьюринга), вывод один: ИМТ чаще всего работает неверно (во многих вариантах входит в бесконечный цикл), и лишь в очень редких случаях возможна выдача правильного результата.
Закономерен вопрос, а зачем мы в предыдущем разделе заговорили об абстрактных автоматах? Ответ необычайно прост – не будешь же каждый раз эмулировать ИМТ и подбирать на ее вход различные кодовые комбинации: работает, не работает. Гораздо проще, если ИМТ проинтерпретирована соответствующим ей абстрактным автоматом, установить закономерность поломок. Любопытно посмотреть – какой абстрактный автомат соответствует ИМТ-1? Любопытство быстро вознаграждается рассмотрением графа такого автомата (рис.1).
Рис.1 Автомат, соответствующий ИМТ-1
Целесообразно дать пояснения к этому рисунку. Во-первых, здесь небольшое отличие от автомата, интерпретирующего исправный инвертор: символы, размещенные у начала стрелки – входные символы, у конца – соответствующий выходной символ. Во-вторых, что особенно занимательно, получился недетерминированный автомат. Недетерминированный – значит автомат, работающий в разных ситуациях по разному. Так, например, у цикла, выполняющего переход из состояния q0 в то же самое состояние q0 при подаче на вход символа 0, автомат на выходе выдает символ 1, а иногда – 0. То же самое происходит, когда автомат при воздействии на его вход символа l переходит из состояния q0 в состояние q1, выдавая на выходе при этом то 0, то 1. То есть один и тот же автомат «изображает» себя в разных «лицах» и в каком-то случае это «лицо» – правильное.
Не составляет особого труда изобразить автомат, интерпретирующий ИМТ-2. Он
Рис.2 Автомат, соответствующий ИМТ-2
изображен на рис.2. Если более подробно, то сначала он работает, как настоящий инвертор, т. е. «преобразует» единички в нули (эта стадия работы на рисунке не изображена). Но как только на его вход поступает 0, он еще некоторое время, не останавливаясь, работает правильно, но затем «превращается» в автомат рис.2., который «тупо» и бесконечно переходит из q0 в q1 и обратно.
Видимо, пора сделать какие-то выводы из экспериментов с «ломкой дров». Честно говоря, для меня они оказались неожиданными. Удивил, например, факт, что для определенного вида поломок и при определенных воздействиях «внешней среды» ИМТ работает правильно. Я не случайно употребил здесь словесный оборот «внешняя среда». Как это похоже на «неисправный» человеческий мозг. Допустим, психиатром поставлен правильный диагноз: у данного человека имеется такое-то конкретное психическое заболевание. Однако, не все же такой больной делает неправильно. В одних ситуациях имеет место неадекватное поведение, в других – реакции вполне предсказуемы и адекватны. Разумеется, ошибочно устанавливать непосредственную связь между конкретной поломкой конкретной машины Тьюринга и наличием определенного психического заболевания. Здесь – всего лишь намек на то, что Тьюрингова модель переработки информации мозгом является не такой уж неподходящей для данного случая моделью.
