201

программа для произвольного заданного входа. Смысл этого утверждения для теоретического программирования состоит в следующем: не существует общего метода проверки программ на наличие в них бесконечных циклов.

6.Не существует алгоритма, позволяющего установить, вычисляет ли некоторая конкретная программа (на любом языке программирования) постоянную нулевую функцию Z(x)=0. Как следствие, можно утверждать, что проблема о том вычисляют ли две произвольные программы одну и ту же одноаргументную функцию, тоже алгоритмически неразрешима. Тем самым получаем, что в области тестирования компьютерных программ имеются принципиальные ограничения.

Сделаем несколько замечаний.

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

Рможет быть и можно выяснить, применим к нему данный нормальный алгоритм или нет, но нет алгоритма, позволяющего выяснить применимость любого нормального алгоритма к любому слову. Это означает, что рассматриваемый класс задач достаточно обширен и надо как-то разумно делить их на подклассы и для них искать разрешающие алгоритмы.

2.Теоремы об алгоритмической неразрешимости показывают, что математика не сводится к построению алгоритмов.

3.Область применения алгоритмов весьма широка и к ней относятся не только вычислительные процессы. Более того, для многих проблем, считающихся трудными, теоретически можно построить алгоритм, но его реализация сопряжена с очень долгим счетом и необходимостью запоминать большое количество промежуточных результатов. Создание быстродействующих вычислительных машин значительно расширило круг решаемых задач.

§14. Сведение любого преобразования слов в алфавите к вычислению значений целочисленных функций

Пусть А - алфавит, содержащий n букв. Поставим в соответствие каждой букве a (a A) число (геделев номер) g(a) из чисел 1,2,...,n, причем различным буквам поставим в соответствие различные числа (геделевы номера). Очевидно, что по каждому g(a) всегда можно восстановить букву. Если задано некоторое слово Р, например, P=ak1ak2...akm (aki A), то сопоставим ему

геделев номер:

g(P)=2b1 3b2 5b3...qmbm,

где bi=g(aki) и qm - m−е простое число. Легко видеть, что таким образом можно определить геделев номер каждому слову Р и по каждому геделеву номеру g(P) легко восстановить слово, которому соответствует этот номер.

202

Пример. Пусть А={a,b,c}. Тогда можно положить g(a)=1, g(b)=2, g(c)=3. Если P=ааbа, то g(P)=21*31*52*71. Если же задано число N=18, то, представив 18 в виде произведения степеней простых чисел 18=2 *32, получаем, что 18 является геделевым номером слова Q=ab.

Пусть задана последовательность слов в алфавите А (которую можно, например, назвать предложением в алфавите А). Тогда этой последовательности слов можно сопоставить последовательность геделевых номеров каждого слова в том же порядке, что и слова, либо, считая, что пробел между словами имеет геделев номер (n+1), сопоставить всей последовательности один геделев номер. Например, Пусть А={a,b,c} и задана последовательность слов Р=аbb саbb аа, тогда либо

g(P)=g(abb), g(cabb), g(aa) = 21*32*52, 23*31*52*72, 21*31

либо g(P)=21*32*52*74*113*131*172*192*234*291*311.

Ясно, что в данных случаях по данному номеру или последовательности номеров можно единственным образом восстановить исходную последовательность слов (предложение).

Как только проведена нумерация, становится понятным, что любое преобразование слов или предложений в алфавите А в слова или предложения А можно свести к вычислению значений функции

m= ϕ(n) или m= ϕ (n1,n2,...nk),

где n,n1,n2,...,nk - геделевы номера преобразуемых слов или предложений, а m - геделев номер результата. Это следует из того, что после введения нумерации можно иметь дело уже только с соответствующими номерами слов или предложений, а не с самими словами или предложениями.

Очевидно, что если у нас есть метод преобразования слов (предложений) алфавита А, то есть и метод вычисления значений соответствующей функции. Действительно, чтобы найти значение ϕ(n) при n=α, можно по α восстановить слово (предложение), затем с помощью имеющегося метода преобразовать его в слово являющееся результатом и по результирующему слову (предложению) найти геделев номер ϕ(α). Следовательно, ϕ(α)=β.

Наоборот, если есть метод вычисления функции ϕ(n), то, стало быть, имеется и метод преобразования исходного слова (предложения). Действительно, по записи слова (предложения) можно найти соответствующий ему номер α, затем вычислить β=ϕ(α) и по β определить результирующее слово (предложение).

Таким образом, всякое преобразование слов или предложений алфавита А в слова или предложения того же алфавита можно свести к вычислению значения некоторой функции, и наоборот.

Ранее среди всевозможных преобразований слов алфавита нас интересовали преобразования, которые используют механическую процедуру, т.е. преобразования с помощью алгоритмов. В следующем параграфе займемся изучением функций, значения которых вычисляются с

203

помощью некоторых "механических" процедур, и установим связь с вычислимостью с помощью нормальных алгоритмов.

§ 15. Примитивно рекурсивные и общерекурсивные функции

Рекурсивное определение функции - это, грубо говоря, определение, в котором значения функции для данных аргументов непосредственно определяются значениями этой же функции для "более простых" аргументов или значениями "более простых" функций. (Понятие "более простой" следует уточнить: например, простейшей функцией можно считать функциюконстанту). Такой подход к рассмотрению функций удобен тем, что рекурсивные определения можно рассматривать как алгоритмы.

Здесь, как и при определении вычислимости по Маркову или Тьюрингу, будем рассматривать только арифметические функции.

Теперь приступим к строгому определению примитивно рекурсивных и общерекурсивных функций.

1. Следующие функции называются исходными (простейшими)

функциями:

1)нуль функция: Z(x)=0 при x (x≥0),

2)функция прибавления единицы: N(x)=x+1 при x(x≥0), ясно, что,

используя функции Z и N, можно получить любую функцию-константу, например:

1=N(Z(x)), 2=N(N(Z(x))), 3=N(N(N(Z(x)))),

. . . . . . . .

3)проектирующие функции Jin (x1,x2,...,xn)=xi при всех x1,x2,...,xn≥0 (i=1,2,...,n; n=1,2,...)

2. Следующие правила служат для получения новых функций, исходя из уже имеющихся функций.

Подстановка

f(x1,x2,...,xn)=g(h1(x1,x2,...,xn),...,hm(x1,x2,...,xn)), тогда говорят, что функция f

получена с помощью подстановки из функций g, h1, h2,..., hm.

204

Рекурсия: f(x1,x2,...,xn,0)=g(x1,x2,...,xn),

а)

f(x1,x2,...,xn,y+1)=h(x1,x2,...,xn,y,f(x1,x2,...,xn ,y)),

при этом исключается случай n=0, для которого:

f(0)=k, где k - фиксированное целое неотрицательное число,

б)

f(y+1)=h(y,f(y)).

Вслучае а) будем говорить, что функция f получена из g и h с помощью рекурсии, а x1,x2,...,xn - параметры рекурсии.

Вслучае б) говорят, что функция f получена из одной функции h с помощью рекурсии.

Заметим, что функция f всегда определена: в случае а) значение

f(x1,x2,...,xn,0) определяется из 1-го равенства, далее, если мы знаем f(x1,x2,...,xn,y), то из 2-го равенства определяем f(x1,x2,...,xn,y+1), аналогично и для случая б).

µ- оператор:

пусть функция g(x1,x2,...,xn,y) такова, что для любых x1,x2,...,xn существует по крайней мере одно значение у, при котором g(x1,x2,...,xn,y)=0.

Обозначим через µy(g(x1,x2,...,xn,y)=0) наименьшее значение у при котором g(x1,x2,...,xn,y)=0.

Пусть f(x1,x2,...,xn)=µy(g(x1,x2,...,xn,y)=0). Будем тогда говорить, что функция f получена из функции g с помощью µ-оператора, если для любых x1,x2,...,xn существует по крайней мере одно значение у, для которого

g(x1,x2,...,xn,y)=0.

Функция называется примитивно рекурсивной, если она может быть получена из исходных функций 1), 2) и 3) с помощью конечного числа подстановок и рекурсий.

Функция f называется общерекурсивной, если она может быть получена из исходных функций 1), 2) и 3) с помощью конечного числа подстановок, рекурсий и µ-оператора. Общерекурсивные функции иногда называют рекурсивными функциями.

Из определений очевидно, что каждая примитивно рекурсивная функция является общерекурсивной, но не наоборот.

Отметим, что примитивно и общерекурсивные функции являются всюду определенными функциями, так как исходные функции всюду определены, а подстановки, рекурсии и µ-оператор не меняют всюду определенности.