yandex rtb 1
ГоловнаЗворотній зв'язок
yande share
Главная->Математика і інформатика->Содержание->6.4. Примитивно рекурсивные и рекурсивные функции.

Математическая логика

6.4. Примитивно рекурсивные и рекурсивные функции.

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

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

(I) Нуль-функция: Z(x)=0 при каждом х.

(II) Прибавление единицы: N(x)=x+1 при каждом x.

(III) Проектирующие функции: U1n(x1,..,xn)=xi при всех х1,...,хn (i = l,.. ,n; i = 1.2,...).

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

(IV) Подстановка:

f(х1,...,хn )=g(h1(x1,…,xn),..., hm(x1,...,xn,));

Говорят, что функция f получена с помощью подстановки из функций

g(y1,...,ym}, h1(x1,...,xn),…, hm(x1,…,.xn).

(V) Рекурсия:

f(x1,…,xn,0)=g(x1,...,xn),

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

при этом исключается случай n=0, для которого отдельно: f(0)=k ( где k -фиксированное целое неотрицательное число), f(y+l)=h(y, f(y)).

Мы будем говорить, что функция f получена из функции g и h (или в случае n=0 из одной лишь функции h) с помощью рекурсии, а х1,...,xn назовем параметрами рекурсии. Заметим, что функция f вполне определена: значение f(x1,...,xn,0) определяется из первого равенства, а если мы уже знаем значение f(x1,...,xn,y), то из второго равенства мы можем найти значение f(x1,…,xn,y+1).

(VI) -оператор: пусть функция g(xl,..,xn,y) такова, что для любых x1,…,xn существует по крайней мере одно значение у, при котором g(x1,....,xn,y)=0. Обозначим через y(g(xl,..,xn,y)=0) наименьшее значение у, при котором g(x1,…,хn, у)=0. Вообще, для всякого отношения R(x1,...,xn,y) будем через yR(x1,...,xn,y) обозначать то наименьшее значение у, при котором R(x1,...,xn.y) истинно, если вообще такие значения существуют. Пусть f(x1,...,xn)=(y(g(x1,...,xn,y)=0). будем говорить, что функции f получена из функции g с помощью -оператора, если выполнено вышеприведенное предположение о функции g для любых х1,...,хn существует по крайней мере о значение у, для которого g(x1,...,xn.y)=0.

(3) Функция f называется примитивно рекурсивной, если она может быть получена из исходных функций с помощью конечного числа подстановок (IV) рекурсий (V), т.е. если существует такая конечная последовательность функций f1,...,fn, что fn=f и для каждого i, 0i<n, функция f1 либо исходная, либо может быть получена из некоторых  предшествующих ей в этой последовательности функций с помощью применения правила (IV) (подготовки) или правила (V) (рекурсии).

(4) Функция f называется рекурсивной если она может быть получена из исходных функций с помощью конечного числа применений подстановки рекурсии (V) и -оператора (VI). Это последнее определение отличается от определения примитивно рекурсивной функции лишь дополнительным разрешением применять -оператор. Поэтому всякая примитивно рекурсивная функция является также и рекурсивной функцией. Обратное  впрочем, не всегда верно.

Мы покажем, что класс рекурсивных функций совпадает с классом функций, представимых в S. (В литературе вместо термина "рекурсивный" иногда употребляется термин "общерекурсивный".)

Теорема 6.2. Следующие функции являются примитивно рекурсивными:      (а) х+у,

(b) х*у;   

(с) хy;

(d) (x)=x-l,   если х>0 и (х)=0, если х=0;

(e) х+у=х-у, если х0 и х+у=0, если х=0;

(f) |х-у|=x-у. если ху, |х-у|=0, если х<у;

(g) sg(x)=0 если х=0, sg(x)=1 если х0;

(h) ¬sg(x)=l если х=0, ¬sg{x)=0 если x0;

(I) х!; (j) min(x,y)=наименьшему из чисел х и у;

(k) min(x1,…,xn)

(1) max(x,y)=наибольшему из чисел x и у,

(m) max(x1, ..., хn);

(n) rm(х,у)=остатку от деления х на у, если x0, и у, если х=О;

(о) qt(х.,у) = частному от деления на х.

Доказательство.

(a) По правилу рекурсии (V); х+0=х        т. е. f(x,0)=U1n(x)=x1

x+(y+l)=N(x+y) т.е.         f(x,y+l)=N<f(x,y)).

(b)     x=0      т. е.          g(x,Q)=Z(x)                  x*(у+1)=(х*у)+х    т. е. g(x,y+l)=f(g(x,y),x), где f есть функция сложения.

(c)     х0=1            хy+1=(ху)*х

(d)      (0)=0     (у+1)=у

(e)     х+0=х     х+(у+1)= (х+у)

(f)  |x-y|=(x+y)+(y+x) (подстановка)

(g) sg(0)=0 sg(y+1)=1

(h) ¬sg(x)=1+sg(x)

(I) 0!=1       (y+1)!=(y!)*(y+1)

(j)  min(x,y)=x+(x+y)

(k) Предположим, что функция min(x1,...,xn) - примитивно рекурсивная. Для min(x1,...,xn,) имеем min(xl,…,xn+1)=min(min(x1,...,xn),xn+1) (1)      max(x,y)=y+(x+y) (m)   max(x1,...,xn+1)=max(max(xl,...,xn),xn+1) (n)     rm(x,0)= 0   rm(х,у+1)=N(rm(х,у))*sg(|х-N(rm(х,у))|) (о)     qt(x,0)=0                 qt(x,y+1)=qt{x,y)+-sg(|x-N(rm(x,y))|) Определения 6.6 - 6.8.

5. если z=0 и f(x1,…,xn, 0)+…+f(x1,…,xn, z-1), если z>0, 6.

7.

8.

Эти ограниченные суммы и произведения являются функциями аргументов х1 .... хn, z. Суммы и произведения, ограниченные с двух сторон, можно теперь определить через введенные только что ограниченные суммы  произведения, например:

Теорема   6.3.   Если  f   -   примитивно  рекурсивная  (или рекурсивная) функция, то все определенные выше ограниченные суммы, и произведения этой функции являются также примитивно рекурсивными (или рекурсивными) функциями.

Определение 6.9. Наконец,  ограниченный  -оператор определим так:

yy<z R(x1,…,xn,y)=наименьшему  у такому, что y<z и R(x1,…,xn,.y). если такое у существует, и z в противном случае.

(Здесь выбор z в качестве значения оператора во втором случае продиктован только  интересами удобства и дальнейших доказательствах никакого содержательного смысла в это не вкладывается.)

Определение 6.10. Отношение R(x1,...,хn) называется примитивно рекурсивным (рекурсивным) отношением, если примитивно рекурсивной (соответственно рекурсивной)     является    его     характеристическая функция CR(x1,...,xn). В частности, данное множество А натуральных  чисел является примитивно рекурсивным (рекурсивным) если примитивно рекурсивной (рекурсивной) является его характеристическая функция СА(х).

Примеры. (1) Отношение x1=x2 примитивно рекурсивно, так как характеристическая функция его совпадает с функцией sg(|x1-x2|), которая примитивно рекурсивна, в силу предложения (f), (g) теоремы (5,2.)

(2) Примитивно рекурсивная функция sg(x2x1) служит характеристической функцией отношения х12, которое, таким образом примитивно рекурсивно.

{3} Отношение х12 примитивно рекурсивно, так как его характеристической функцией является примитивно рекурсивная функция sg(rm(x1,x2)).

(4) Отношение Pr(x), т.е. "х есть простое число", примитивно рекурсивно так как Cpr(x)=sg((D(x)2)+sg(|x-l|+sg(|x-0|)).

Теорема 6.4. Отношении, которые можно получить из примитивно рекурсивных (или рекурсивных) с помощью пропозициональных связок и ограниченных операторов и кванторов, также  примитивно рекурсивны  ( соответственно рекурсивны); применение ограниченных   -оператором yy<z или yz  к примитивно рекурсивным (рекурсивным) отношениям приводит к примитивно рекурсивным (рекурсивным) функциям.

Теорема 6.5. Всякая рекурсивная функция представима в S.

Доказательство. Исходные функции Z, N, Uin представимы в S, согласно примерам (а) - (с). В силу примера (d), правило подстановки (IV) не выводит за пределы класса представимых функций. Доказательство для правила рекурсии и -оператора см. (Мендельсон Э. стр.147-150).

Следствие. Всякое рекурсивное отношение выразимо в S.

Доказательство. Пусть R(x1,...,xn) - рекурсивный предикат. Характеристическая функция СR этого предиката рекурсивна. В силу теоремы 6.5, функций СR представима в S и, следовательно, в силу теоремы 6.1, предикат R выразим в S.

 

40