|
C1 X X C2 C1 | П C1 C2 X Л C2 C2 | | C1 Убедимся, что данная программа имитирует поведение нашей кошки. На ленте написана единственная палочка (остальные ячейки пусты); эту палочку воспринимает машина, находящаяся в состоянии С1. В соответствии со второй командой считывающе‑записывающая головка машины сделает движение по ленте вправо (кошка залезет на сосну) и останется в том же состоянии (кошка еще не испугалась). Второй такт работы машины определит первая команда: воспринимая символ х, машина, сохраняя этот символ в обозреваемой ячейке (кошка остается на верхушке сосны), переходит в состояние С2 (кошка пугается высоты). Воспринимая в состоянии С2 символ X, машина приведет в движение свою считывающее‑записывающую головку, которая сдвинется влево по ленте на одну ячейку (кошка, воздействуя на барабанные перепонки людей, добивается того, что ее перемещают вниз); это описывается третьей из четверок списка. Последняя команда показывает, что, обозревая символ | в состоянии С2, машина переходит в состояние C1 (увидя привычную обстановку, кошка успокаивается). Дальше опять сработает вторая команда, и процесс начнет повторяться. Машина Тьюринга будет работать неограниченно долго. Вернемся к вопросу: не шире ли круг действий, осуществляемых машинами Тьюринга, чем круг действий, подведомственных рекурсивным функциям? Оказывается, нет – это доказано совершенно строго, методами, не вызывающими сомнений. То обстоятельство, что рекурсивные функции имеют дело только с числами, а машины Тьюринга – с произвольным алфавитом, содержащим сколь угодно большое (но обязательно конечное) число символов, не имеет существенного значения, поскольку символы можно занумеровать, то есть превратить в числа. Наконец, рассмотрим еще один подход к понятию вычислимости, разработанный А. А. Марковым. Ведущий отечественный «математический конструктивиста поставил перед собой вопрос: к каким элементарным и математически точно определимым операциям можно было бы свести все процедуры, широко применяющиеся в математике и других науках и носящие название процессов, задаваемых алгоритмами? Известно, что математика прямо‑таки изобилует алгоритмами – четкими предписаниями о подлежащих выполнению действиях. Но задача состояла в нахождении общего определения алгоритма (алгорифма) – определения, под которое подпадали бы не только все известные алгоритмы, но и те, которые появятся в будущем. Искомое точное определение алгоритма должно было соответствовать содержательно‑интуитивному пониманию алгоритмов в математике: алгоритм – это «точное предписание, определяющее вычислительный процесс, ведущий от варьируемых исходных данных к искомому результату»[135]. Для построения такого определения необходимо было найти «атомы», из которых можно сформировать любое предписание – общепонятное, ясное, однозначно понимаемое. Задача эта была очень важна. Вот как раскрывает ее особую роль известный отечественный специалист по философским проблемам математики С. А. Яновская (1896–1966). — 101 —
|