10.1. Программы с конечным числом переменных

Мы хотим показать, что график всякой вычислимой функции является арифметическим множеством, то есть выразим формулой арифметики. Для этого удобно перей­ти от машин Тьюринга к другой модели, которую мож­но условно назвать машинами с конечным числом реги­стров.

Программа для такой машины использует конечное число переменных, значениями которых являются нату­ральные числа. Числа эти могут быть произвольного раз­мера, так что машина реально имеет память неограни­ченного объёма. Программа состоит из нумерованных по порядку команд. Каждая команда имеет один из следую­щих видов:

• а:=0

• а:=Ь

• а:=Ь+1

• а:=Ъ-1

• goto (номер)

• if а=0 then goto (номер1) else goto (номер2)

• stop

Для тех, кто не сталкивался с командой goto, поясним, что имеется в виду в команде if: если значение пере­менной а равно нулю, то далее исполняется команда с номером, указанным после then (этот номер — конкрет­ное натуральное число, не превосходящее числа командв программе); если а не равно нулю, то дальше выполня­ется команда с номером, указанным после else. Коман­да goto без условия всегда выполняет переход к команде с указанным в ней номером.

Поскольку мы считаем, что значения переменных — натуральные (целые неотрицательные) числа, условимся считать разность 0—1 равной 0 (впрочем, это не так важно — можно было бы считать это аварией).

Дойдя до команды stop, программа заканчивает ра­боту.

Как и для машин Тьюринга, полезна некоторая прак­тика программирования. Для тренировки напишем прог­рамму сложения двух чисел. Она помещает в с сумму чи­сел, которые были в переменных а и Ь. Такая программа на паскале имела бы вид

с:=а;

{инвариант: ответ=сумма текущих значений с и Ь} while ЬОО do begin

c:=c+i;

b:=b-i; end;

Имитируя цикл с помощью операторов перехода, получа­ем программу для нашей машины:

1 с:=а

2 if b=0 then goto в else goto 3

3 c:-c+l

4 b:=b-i

5 goto 2 в stop

Теперь легко понять, как написать программы для вычитания, умножения (которое реализуется как цикл с повторным сложением), деления с остатком (как учил ещё Энгельс в забытой ныне книге «Диалектика приро­ды», деление есть сокращённое вычитание), возведения в степень, проверки простоты, отыскания n-го простого числа и т. п. Вообще по сравнению с машинами Тьюрингаэтот язык более привычен и потому легче поверить, что на нём можно запрограммировать все алгоритмы.

Единственное, чего в нём реально не хватает — это массивов. Но это легко обойти, поскольку есть числа произвольного размера и нас не интересует число опе­раций (как это принято в общей теории алгоритмов). Вместо массива битов мы можем хранить число, двоич­ной записью которого он является, а для массивов чисел воспользоваться, скажем, основной теоремой арифме­тики и хранить последовательность (а, Ь, с, ё, е) как чи­сло 2а365с7й11е. При этом операции а[д] :=Ъ и Ь:=а[д] заменяются на небольшие программы, которые содер­жат переменные а, Ь, з. и ещё несколько переменных. (Частью этих программ является нахождение простого числа с заданным порядковым номером.)

Легко определить понятие вычислимой (в этой моде­ли) функции. Пусть есть программа с двумя переменны­ми х и у (и, возможно, другими). Поместим в х некото­рое число п, а в остальные переменные поместим нули. •Запустим программу. Если она не остановится, то вычи­сляемая ей функция в точке п не определена. Если оста­новится, то содержимое переменной у после остановки и будет значением функции, вычисляемой нашей програм­мой (в точке п). Функция называется вычислимой (в этой модели), если существует вычисляющая её программа.

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

82. Покажите, что класс вычислимых функций не изме­нится, если исключить из определения команду копирова­ния а:=Ь.

Несколько более удивительно, что число переменных можно ограничить, скажем, сотней — но и это не так уж странно, если вспомнить, что мы можем хранить в одной переменной целый массив.

83. Проверьте это.