Свойства алгоритма. Примитивно-рекурсивные функции и операторы. Частично-рекурсивные функции. Тезис Черча

вычислениях функций (рекурсивные функции)
Основанные на наличии устройства, выполняющего примитивные операции

(машина Тьюринга)

Основанные на преобразованиях слов из символов алфавита в другие слова (алгоритмы Маркова)

выбора Unm (x1, x2,…,xn)=xm (m

h(y1,…, ym), g1(x1,…, xn), …, gm(x1,…, xn)
Snm (h, g1,…, gm) = h(g1(x1,…, xn), …, gm(x1,…, xn)) = f(x1,…, xn).

Оператор примитивной рекурсии Rn определяет (n+1)-местную функцию f через n-местную функцию g и (n+2)-местную функцию h так:
f(x1,…,xn,0)=g(x1,…,xn);
f(x1,…,xn, y+1)=h(x1,…,xn, y, f(x1,…,xn, y)).

Краткая запись: f(x1,…,xn, y)=Rn(g, h).

f(x)=s’(s’(…s’(0(x)))), если применить функцию следования конечное число раз, равное константе

k.

f(x)=x
Первый способ доказательства: f(x)= U11 (x)
Второй способ доказательства:
f(0)=0=const – что const – ПРФ – доказано
f(x+1)=x+1=s’(x)=s’(f(x))=U22 (x, s’(f(x))) – получено с помощью конечного числа ПРФ, операторов ПР и суперпозиции
f(x,y)=x+y
f(x,0)=x – ПРФ
f(x,y+1)=x+y+1=f(x,y)+1=s’(f(x,y))= U33 (x, y, s’(f(x,y)))

1, если x>0
7)

sg(x)=
0, если x=0

1, если x=0
8) sg(x)=
0, если x>0

x-1, x>0
9)f÷1 (x)=
0, x=0

x-y, если x>=y
x÷y=
0, если x11) max(x,y)
12) min (x,y)
13) |x-y|
a+b
14) h(a,b)=aa+1

a
15) q(a,b)=(a+b)(a+b-1)


Логические функции:
Если x,y∈{0,1}
x = 1÷x
x ∨ y = max(x,y)
x ∧ y = min(x,y)

P(x), истинное для некоторых хi и ложное для остальных, называется

одноместным предикатом на множестве А.
Декартово произведение множеств А1,…,АM:
А1хА2х…xАM: {(x1,x2,…,xm)|x1∈A1,…,xm∈AM}.
Для предиката вводится его характеристическая функция:
χP(x1,…,xn)= 1, если P(x1,…,xn) истинен,
0, в противном случае.

Условный переход или разветвление. Обозначим его B, который по функциям q1(x1,…,xn), q2(x1,…,xn) и предикату P(x1,…,xn) строит функцию f(x1,…,xn)=B(q1, q2, P):
f(x1,…,xn)= q1(x1,…,xn), если P(x1,…,xn) истинно.
q2(x1,…,xn), если P(x1,…,xn) ложно.

f(x1,…,xn)=g1(x1,…,xn) χp(x1,…,xn)+g2(x1,…,xn) (1- χp(x1,…,xn)).

Операции суммирования и умножения по переменной y с пределом z

– это операторы, которые из функции f(x1,…,xn y) порождают новые функции:
q(x1, . . . , xn, z) = f(x1, . . . , xn, y),
h(x1, . . . , xn, z)= f(x1, . . . , xn, y).
Они примитивно-рекурсивны (если f – примитивно – рекурсивна) в силу следующих соотношений:
g(x1,…, xn, 0)=0 (ПРФ по определению);
g(x1,…, xn, z+1)=g(x1,…, xn, z)+f(x1,…,xn, z);
h(x1,…, xn, 0)=1 (по определению);
h(x1,…,xn, z+1)=h(x1,…,xn, z) f(x1,…,xn, z).

Пример: количество делителей числа х: τ(х)=

случае z - функция.
Пример: k=µy≤4 (y>x+2).
Для х=0 процесс вычислений:

y=0. y ≤ 4 - истина. Предикат: 0>2 – ложь
y=1. y ≤ 4 - истина. Предикат: 1>2 – ложь
y=2. y ≤ 4 - истина. Предикат: 2>2 – ложь
y=3. y ≤ 4 - истина. Предикат: 3>2 – истина, значит k=3.
Для x=3 процесс вычислений:
y=0. y ≤ 4 - истина. Предикат: 0>5 – ложь
y=1. y ≤ 4 - истина. Предикат: 1>5 – ложь
y=2. y ≤ 4 - истина. Предикат: 2>5 – ложь
y=3. y ≤ 4 - истина. Предикат: 3>5 – ложь
y=4. y ≤ 4 - истина. Предикат: 4>5 – ложь
y=5. y ≤ 4 - ложь. Предикат в истину не обратился, значит k=4
– значению ограничителя.
Доказательство ПРФ ограниченного оператора минимизации:

P2 (a, x)=ax

P1 (a, x+1)=P0 (a, P1(a, x));

P1 (a, 1)=a; P1 (a, 0)=0;
P2 (a,x+1)=P1(a,P2(a,x)); P2(a,1)=a; P2(a,0)=1.

Продолжим эту цепочку, полагая по определению для n=2, 3,…
Pn+1 (a, 0)=1;
Pn+1 (a, 1)=a;
Pn+1 (a, x+1)=Pn (a, Pn+1 (a, x)).

Растут функции Pn крайне быстро. Например, при n=3 имеем:
P3 (a, 0)=1; P3 (a, 1)=a; P3 (a, 2)=aa; P3 (a, 3)=a a a.
Введем новые функции:
B (n, x)=Pn (2,x), A(x)=B (x, x).
B (n, x) - функция Аккермана, A(x) – диагональная функция Аккермана

x+1)=B(n,B(n+1, x))

Для любой примитивно-рекурсивной функции f(x) найдется такое n ,

что для любого x≥n, A(x)>f(x)

Неограниченный µ - оператор:
f(x1,…,xn)=µy(P(x1,…, xn,y))

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

f(x)=x-1=µy(y+1=x) не определена при x=0