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

Сентябрь 3, 2022

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

Содержание

2. Свойства алгоритма и типы алгоритмических моделей Свойства алгоритма: Массовость Дискретность Элементарность Детерминированность Результативность Типы моделей Основанные
3. Примитивно-рекурсивные функции Простейшие базисные функции: 1) нуль-функция 0(х)=0; 2) функция следования s’(x)=x+1; 3) функция выбора Unm
4. Примеры ПРФ. Доказательство ПРФ по определению f(x)=k (функция-константа) f(x)=s’(s’(…s’(0(x)))), если применить функцию следования конечное число раз,
5. Расширение набора ПРФ 4) f(x,y)=x*y 5) f(x,y)=xy 6) f(x)=x! 1, если x>0 7) sg(x)= 0, если
6. Предикаты и примитивно-рекурсивные операторы А – множество объектов хi (i=1,..,N), утверждение P(x), истинное для некоторых хi
7. Операторы суммирования и умножения f(x1,…,xn, y) – функция от (n+1)-й переменной. Операции суммирования и умножения по
8. Ограниченный оператор минимизации (μ-оператор) Ограниченный оператор минимизации: µy≤z (P(x1,…,xn, y)). В общем случае z - функция.
9. Быстро растущие функции. Функции Аккермана P0 (a, x)=a+x, P1 (a, x)=ax, P2 (a, x)=ax P1 (a,
11. Скачать презентацию

Слайд 2

Свойства алгоритма и типы алгоритмических моделей
Свойства алгоритма:
Массовость
Дискретность
Элементарность
Детерминированность
Результативность
Типы моделей
Основанные на вычислениях

функций (рекурсивные функции)

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

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

Слайд 3

Примитивно-рекурсивные функции
Простейшие базисные функции:
1) нуль-функция 0(х)=0;
2) функция следования s’(x)=x+1;
3) функция выбора

Unm (x1, x2,…,xn)=xm (m<=n).
Оператор суперпозиции Snm
Для функций 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).

Слайд 4

Примеры ПРФ. Доказательство ПРФ по определению
f(x)=k (функция-константа)
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)))

Слайд 5

Расширение набора ПРФ
4) f(x,y)=x*y
5) f(x,y)=xy
6) f(x)=x!
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)

Слайд 6

Предикаты и примитивно-рекурсивные операторы
А – множество объектов хi (i=1,..,N),
утверждение 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)).

Слайд 7

Операторы суммирования и умножения
f(x1,…,xn, y) – функция от (n+1)-й переменной. Операции

суммирования и умножения по переменной 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).
Пример: количество делителей числа х: τ(х)=

Слайд 8

Ограниченный оператор минимизации (μ-оператор)
Ограниченный оператор минимизации:
µy≤z (P(x1,…,xn, y)). В общем случае

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
– значению ограничителя.
Доказательство ПРФ ограниченного оператора минимизации:

Слайд 9

Быстро растущие функции. Функции Аккермана
P0 (a, x)=a+x, P1 (a, x)=ax, 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) – диагональная функция Аккермана

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

Содержание

Примитивно-рекурсивные функцииПростейшие базисные функции:1) нуль-функция 0(х)=0;2) функция следования s’(x)=x+1;3) функция выбора

Примеры ПРФ. Доказательство ПРФ по определениюf(x)=k (функция-константа) f(x)=s’(s’(…s’(0(x)))), если применить функцию

Расширение набора ПРФ4) f(x,y)=x*y5) f(x,y)=xy 6) f(x)=x! 1, если x>07) sg(x)=

Предикаты и примитивно-рекурсивные операторыА – множество объектов хi (i=1,..,N), утверждение P(x),

Операторы суммирования и умноженияf(x1,…,xn, y) – функция от (n+1)-й переменной. Операции

Ограниченный оператор минимизации (μ-оператор)Ограниченный оператор минимизации:µy≤z (P(x1,…,xn, y)). В общем случае

Быстро растущие функции. Функции АккерманаP0 (a, x)=a+x, P1 (a, x)=ax, P2

Похожие презентации