Борис Бирюков - Жар холодных числ и пафос бесстрастной логики

3. Исходная конфигурация та же. Программа машины Тьюринга задается списком команд:

C1 Х Х Ck

C1 | X C2

С2 X П С1

Первый такт определится второй командой. Машина сотрет левую палочку и перейдет в новое состояние С2. Восприняв в этом состоянии пустую ячейку (в ней на предыдущем такте был стерт знак|), она сдвинет считывающе-записывающую головку по ленте вправо и вновь перейду в состояние С1. Такое стирание и передвижение вправо будет повторяться до тех пор, пока в состоянии С1 машина не увидит пустую ячейку (это случится, когда палочки будут исчерпаны). Тогда машина остановится. Если ленту, состоящую из одних пустых ячеек, отождествить с нулем, то можно считать, что машина с такой программой осуществляет ту же операцию, что и рекурсивная функция N 1(х), но только над положительными целыми числами: если на ленте помещен единственный массив из n палочек, то машина перерабатывает ленту с такой конфигурацией в пустую ленту.

4. Исходная конфигурация та же. Программа такова:

C1 X | Сk

C1 | Л С1.

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

5. Исходная конфигурация:

... X X X | | |...| | | X | | |...| | | X X X ...

(два массива палочек, разделенных одной пустой ячейкой;

число палочек в каждом массиве произвольно). Работа машины Тьюринга задается списком команд:

С1 | ПС2

С2 Х | С3

С2 | П С2

С3 Х Л С4

С3 | П С3

С4 Х Х Ck

C4 | X С4

Предоставляем читателю убедиться, что машина Тьюринга с данной программой производит сложение чисел /целых положительных), записывая на ленте результат в виде последовательно расположенных палочек в количестве, равном сумме двух заданных чисел (которые тоже были записаны в виде массивов палочек) [10].

Доказано, что машины Тьюринга в состоянии делать все, что могут делать с числами рекурсивные функции. Возникает вопрос: а не способны ли они делать большее? Ведь, во-первых, они могут работать с произвольным алфавитом, а не только с «числовым». Во-вторых, «механическая» процедура, реализуемая машиной Тьюринга, представляется на первый взгляд более универсальной, чем довольно однообразная математическая процедура, осуществляемая рекурсивным аппаратом. Нетрудно вообразить себе очень сложные машины Тьюринга — с громадным количеством внутренних состояний, работающие над богатым символами алфавитом. действие которых определяется весьма длинными программами. Такие машины могут имитировать поведение не только механических устройств типа «андроидов», столь популярных в XVIII веке, кибернетических игрушек и роботов [11], но и живых существ.

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

В этой связи расскажем о кошке, чье поведение живо в памяти одного из авторов этих строк, хотя с того времени прошло уже около двадцати лет. Дело было на даче, при которой был участок, поросший соснами. Гуляя по участку кошка иногда набредала на сосну, вид которой очень располагал на нее забраться. Ни о чем не заботясь, она залезла на высоту двадцати метров, и через несколько минут окрестности оглашались душераздирающим мяуканием - кошка не могла слезть, пугалась и просила о помощи. Поднималась суматоха, где-то добывалась длинная лестница люди лезли на сосну и снимали животное. Придя в чувство и успокоившись, кошка выходила гулять, и если снова набредала на соблазнительную сосну, то залезала на ее ветви и событие повторялось.

Здесь мы наблюдаем действие живой «машины Тьюринга», описание которой исключительно просто. Обозначим обычное состояние кошки через С1, состояние испуга через С2, движение вверх по сосне через П, движение вниз через Л, вид подножья сосны зашифруем символом |, вид, открывающийся с верхушки сосны, символом X. Тогда наша «машина Тьюринга» будет задана списком четверок: