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. Тогда наша «машина Тьюринга» будет задана списком четверок:
C1 X X C2
C1 | П C1
C2 X Л C2
C2 | | C1
Убедимся, что данная программа имитирует поведение нашей кошки. На ленте написана единственная палочка (остальные ячейки пусты); эту палочку воспринимает машина, находящаяся в состоянии С1. В соответствии со второй командой считывающе-записывающая головка машины сделает движение по ленте вправо (кошка залезет на сосну) и останется в том же состоянии (кошка еще не испугалась). Второй такт работы машины определит первая команда:
воспринимая символ х, машина, сохраняя этот символ в обозреваемой ячейке (кошка остается на верхушке сосны), переходит в состояние С2 (кошка пугается высоты). Воспринимая в состоянии С2 символ X, машина приведет в движение свою считывающее-записывающую головку, которая сдвинется влево по ленте на одну ячейку (кошка, воздействуя на барабанные перепонки людей, добивается того, что ее перемещают вниз); это описывается третьей из четверок списка. Последняя команда показывает, что, обозревая символ | в состоянии С2, машина переходит в состояние C1 (увидя привычную обстановку, кошка успокаивается). Дальше опять сработает вторая команда, и процесс начнет повторяться. Машина Тьюринга будет работать неограниченно долго.
Вернемся к вопросу: не шире ли круг действий, осуществляемых машинами Тьюринга, чем круг действий, подведомственных рекурсивным функциям? Оказывается, нет — это доказано совершенно строго, методами, не вызывающими сомнений. То обстоятельство, что рекурсивные функции имеют дело только с числами, а машины Тьюринга — с произвольным алфавитом, содержащим сколь угодно большое (но обязательно конечное) число символов, не имеет существенного значения, поскольку символы можно занумеровать, то есть превратить в числа.
Наконец, рассмотрим еще один подход к понятию вычислимости, разработанный А. А. Марковым. Ведущий отечественный «математический конструктивиста поставил перед собой вопрос: к каким элементарным и математически точно определимым операциям можно было бы свести все процедуры, широко применяющиеся в математике и других науках и носящие название процессов, задаваемых алгоритмами? Известно, что математика прямо-таки изобилует алгоритмами — четкими предписаниями о подлежащих выполнению действиях. Но задача состояла в нахождении общего определения алгоритма (алгорифма) — определения, под которое подпадали бы не только все известные алгоритмы, но и те, которые появятся в будущем. Искомое точное определение алгоритма должно было соответствовать содержательно-интуитивному пониманию алгоритмов в математике: алгоритм — это «точное предписание, определяющее вычислительный процесс, ведущий от варьируемых исходных данных к искомому результату»[12]. Для построения такого определения необходимо было найти «атомы», из которых можно сформировать любое предписание — общепонятное, ясное, однозначно понимаемое. Задача эта была очень важна. Вот как раскрывает ее особую роль известный отечественный специалист по философским проблемам математики С. А. Яновская (1896—1966).
«Начиная с глубокой древности математики строили алгоритмы ... для решения целых классов задач определенного рода. Таковы, например: всем известный алгоритм Эвклида, представляющий собой программу действий, которые нужно выполнить, чтобы, имея любые два целых числа a и b, отыскать их общий наибольший делитель; алгоритм Штурма, позволяющий по заданию коэффициентов многочлена отделить его корни; многие другие алгоритмы алгебры, теории чисел, дифференциальных уравнений и многие, многие другие.
Когда какой-нибудь алгоритм отыскан, то всем ясно что он уже есть: его существование не приходится доказывать.
Но если алгоритм упорно ищут и не находят, то естественно возникает вопрос, возможен ли он вообще? Разве обязательно должен существовать единый прием, позволяющий механически решить (по одной и той же программе) любую из всего класса задач, отличающихся друг от друга значениями каких-либо параметров? Но как доказать несуществование алгоритма, его принципиальную невозможность?
Для этого нужно знать, что, собственно, ищут; нужно иметь четкое определение алгоритма, позволяющее оперировать с этим понятием, как с математическим объектом»[13].
Значимость этой задачи для математики явственно видна на следующем важном примере. Среди двадцати трех проблем, поставленных Гильбертом в докладе «Математические проблемы» на Втором Международном конгрессе математиков в Париже (август 1900 г.), были и такие, которые впоследствии получили отрицательное решение. В частности, такой была десятая по номеру проблема. Приводим ее в формулировке самого Гильберта:
«10. Задача о разрешимости диофантова уравнения.
Пусть задано диофантово уравнение[14] с произвольными неизвестными и целыми рациональными числовыми коэффициентами. Указать способ, при помощи которого возможно после конечного числа операций установить, разрешимо ли это уравнение в целых рациональных числах»[15].
