Презентация на тему: 1 ОБЧИСЛЮВАНІСТЬ КВАЗІАРНИХ ФУНКЦІЙ НА N Розглядаємо спосіб задання

Реклама. Продолжение ниже
1 ОБЧИСЛЮВАНІСТЬ КВАЗІАРНИХ ФУНКЦІЙ НА N Розглядаємо спосіб задання
1 ОБЧИСЛЮВАНІСТЬ КВАЗІАРНИХ ФУНКЦІЙ НА N Розглядаємо спосіб задання
1 ОБЧИСЛЮВАНІСТЬ КВАЗІАРНИХ ФУНКЦІЙ НА N Розглядаємо спосіб задання
1 ОБЧИСЛЮВАНІСТЬ КВАЗІАРНИХ ФУНКЦІЙ НА N Розглядаємо спосіб задання
1 ОБЧИСЛЮВАНІСТЬ КВАЗІАРНИХ ФУНКЦІЙ НА N Розглядаємо спосіб задання
1 ОБЧИСЛЮВАНІСТЬ КВАЗІАРНИХ ФУНКЦІЙ НА N Розглядаємо спосіб задання
1 ОБЧИСЛЮВАНІСТЬ КВАЗІАРНИХ ФУНКЦІЙ НА N Розглядаємо спосіб задання
1 ОБЧИСЛЮВАНІСТЬ КВАЗІАРНИХ ФУНКЦІЙ НА N Розглядаємо спосіб задання
1 ОБЧИСЛЮВАНІСТЬ КВАЗІАРНИХ ФУНКЦІЙ НА N Розглядаємо спосіб задання
1 ОБЧИСЛЮВАНІСТЬ КВАЗІАРНИХ ФУНКЦІЙ НА N Розглядаємо спосіб задання
1 ОБЧИСЛЮВАНІСТЬ КВАЗІАРНИХ ФУНКЦІЙ НА N Розглядаємо спосіб задання
1 ОБЧИСЛЮВАНІСТЬ КВАЗІАРНИХ ФУНКЦІЙ НА N Розглядаємо спосіб задання
1 ОБЧИСЛЮВАНІСТЬ КВАЗІАРНИХ ФУНКЦІЙ НА N Розглядаємо спосіб задання
1 ОБЧИСЛЮВАНІСТЬ КВАЗІАРНИХ ФУНКЦІЙ НА N Розглядаємо спосіб задання
1 ОБЧИСЛЮВАНІСТЬ КВАЗІАРНИХ ФУНКЦІЙ НА N Розглядаємо спосіб задання
1 ОБЧИСЛЮВАНІСТЬ КВАЗІАРНИХ ФУНКЦІЙ НА N Розглядаємо спосіб задання
1 ОБЧИСЛЮВАНІСТЬ КВАЗІАРНИХ ФУНКЦІЙ НА N Розглядаємо спосіб задання
1 ОБЧИСЛЮВАНІСТЬ КВАЗІАРНИХ ФУНКЦІЙ НА N Розглядаємо спосіб задання
1 ОБЧИСЛЮВАНІСТЬ КВАЗІАРНИХ ФУНКЦІЙ НА N Розглядаємо спосіб задання
1 ОБЧИСЛЮВАНІСТЬ КВАЗІАРНИХ ФУНКЦІЙ НА N Розглядаємо спосіб задання
1 ОБЧИСЛЮВАНІСТЬ КВАЗІАРНИХ ФУНКЦІЙ НА N Розглядаємо спосіб задання
1 ОБЧИСЛЮВАНІСТЬ КВАЗІАРНИХ ФУНКЦІЙ НА N Розглядаємо спосіб задання
1 ОБЧИСЛЮВАНІСТЬ КВАЗІАРНИХ ФУНКЦІЙ НА N Розглядаємо спосіб задання
1 ОБЧИСЛЮВАНІСТЬ КВАЗІАРНИХ ФУНКЦІЙ НА N Розглядаємо спосіб задання
1 ОБЧИСЛЮВАНІСТЬ КВАЗІАРНИХ ФУНКЦІЙ НА N Розглядаємо спосіб задання
1 ОБЧИСЛЮВАНІСТЬ КВАЗІАРНИХ ФУНКЦІЙ НА N Розглядаємо спосіб задання
1 ОБЧИСЛЮВАНІСТЬ КВАЗІАРНИХ ФУНКЦІЙ НА N Розглядаємо спосіб задання
1 ОБЧИСЛЮВАНІСТЬ КВАЗІАРНИХ ФУНКЦІЙ НА N Розглядаємо спосіб задання
1 ОБЧИСЛЮВАНІСТЬ КВАЗІАРНИХ ФУНКЦІЙ НА N Розглядаємо спосіб задання
1 ОБЧИСЛЮВАНІСТЬ КВАЗІАРНИХ ФУНКЦІЙ НА N Розглядаємо спосіб задання
1 ОБЧИСЛЮВАНІСТЬ КВАЗІАРНИХ ФУНКЦІЙ НА N Розглядаємо спосіб задання
1/31
Средняя оценка: 4.2/5 (всего оценок: 89)
Код скопирован в буфер обмена
Скачать (163 Кб)
Реклама. Продолжение ниже
1

Первый слайд презентации

1 ОБЧИСЛЮВАНІСТЬ КВАЗІАРНИХ ФУНКЦІЙ НА N Розглядаємо спосіб задання обчислюваних функцій, який ґрунтується на породженні таких функцій за допомогою обчислюваних операцій ( композицій ) з певних базових функцій. Для випадку еквітонних V - квазіарних функцій на N основними обчислюваними операціями є параметричні операції: суперпозиції S v 1,…, vn примітивної рекурсії R y, z мінімізації M y.

Изображение слайда
1/1
2

Слайд 2

2 Операція R y, z двом V - квазіарним функціям g та h зіставляє V - квазіарну функцію f = R y, z ( g, h ) таку: – при у  і m ( d ) значення f ( d )  ; – при у  і m ( d ) значення f ( d ) визначається рекурсивно f ( d  y  0) = g ( d  y  0  z  0); f ( d  y  a +1) = h ( d  y  a  z  f ( d  y  a )) для всіх a < d ( y ). Для всіх d  V N таких: d ( y ) = b, значення f ( d ) обчислюється так : f ( d  у  0) = g ( d  у  0  z  0); f ( d  у  1) = h ( d  у  0  z  f ( d  у  0)) ................................. f ( d ) = f ( d  у  b ) = h ( d  у  b –1  z  f ( d  у  b – 1)).

Изображение слайда
1/1
3

Слайд 3

3 Функція f   =   R y, z ( g,   h ) однозначно визначається за функціями g та h, причому z неістотне для функції f. Твердження 1. Функція R y, z ( g, h ) алгоритмічно обчислювана відносно функцій g, h та відносно операції накладки  і відносно V - ІМ над N як функцій. Твердження 2. Функція R y, z ( g,   h ) алгоритмічно обчислювана відносно V- фінарних функцій g та h.

Изображение слайда
1/1
4

Слайд 4

4 Операція мінімізації M y V - квазіарній функції g зіставляє V - квазіарну функцію f  =  M y ( g ) таку: Для кожного d  V N значення f ( d ) – це перше a  N таке, що g ( d  y  a ) = 0 і для всіх k < a значення g ( d  y  k )       0. Якщо таке a  N не існує, то f ( d )  Для кожного d  V N  значення f ( d ) обчислюється так. Послідовно обчислюємо g ( d  y  k ) для k   =   0,   1,   2,... Перше таке a  N, що g ( d  y  a ) = 0 – шукане f ( d ). Для всіх k < a g ( d  y  k )  0.

Изображение слайда
1/1
5

Слайд 5

5 Процес знаходження M y ( g )( d ) ніколи не закінчиться : – якщо g ( d  y  0)  ; – якщо для всіх k  N значення g ( d  y  k )       0. – якщо для всіх k < a значення g ( d  y  k )       0 та g ( d  y  a ) . Функція f   =   М y ( g ) однозначно визначається за g, причому y неістотне для f. Твердження   3. Функція М y ( g ) алгоритмічно обчислювана відносно функції g, відносно  і відносно V - ІМ над N як функцій. Твердження   4. Функція М y ( g ) алгоритмічно обчислювана відносно V- фінарної функції g. Твердження   5. Операції R y, z та M y зберігають еквітонність V- квазіарних функцій, заданих на N.

Изображение слайда
1/1
6

Слайд 6

6 Базові обчислювані функції для V - квазіарних функцій на N – це о,   s х та ' v. о ( d ) = 0 для всіх d  V N ; s х ( d ) = d ( x )+1 ' v ( d ) = d ( v ) Функцію, яку можна отримати з базових функцій о, s х, ' v за допомогою скінченної кількості застосувань операцій S v 1,…, vn, R y, z та M y, назвемо V - квазіарною частково рекурсивною ( V - КЧРФ ). Обмежуючись V - фінарними функціями, отримуємо: Функцію, яку можна отримати з фінарних функцій о, s х, ' v за допомогою скінченної кількості застосувань операцій S v 1,…, vn, R y, z та M y, назвемо V - фінарною частково рекурсивною ( V - ФЧРФ ).

Изображение слайда
1/1
7

Слайд 7

7 Твердження   6. Кожна V - КЧРФ алгоритмічно обчислювана відносно відносно операції  та V - ІМ над N як функцій. Твердження   7. Кожна V - ФЧРФ алгоритмічно обчислювана. Твердження   8. Кожна V - КЧРФ еквітонна. Алгебра V - КЧРФ – це алгебра (  q ; R y, z, M y, S v 1,…, vn ), носієм  q якої є клас усіх V - КЧРФ, а операціями – R y, z, M y, S v 1,…, vn. Алгебра V - ФЧРФ – це алгебра (  f ; R y, z, M y, S v 1,…, vn ), носієм  f якої є клас усіх V - ФЧРФ, а операціями – R y, z, M y, S v 1,…, vn.

Изображение слайда
1/1
Реклама. Продолжение ниже
8

Слайд 8

8 Операторні терми ( ОТ ) алгебри V - КЧРФ. Алфавіт мови алгебри V - КЧРФ: символи о, s x, ' v ; R y, z,  M y,  S v 1,…, vn, допоміжні символи "(", ")", ",". Індуктивне визначення ОТ алгебри V - КЧРФ : 1)   кожен символ базової функції є атомарним ОТ ; 2) якщо t 0, t 1,..., t n – ОТ, то S v 1,…, vn ( t 0, t 1,..., t n ) – ОТ ; 3) якщо t 0 та t 1 – ОТ, то R y, z ( t 0, t 1 ) – ОТ ; 4) якщо t – ОТ, то M y ( t ) – ОТ. Інтерпретація на множині  q : кожна V - КЧРФ є значенням деякого ОТ алгебри V - КЧРФ. Інтерпретація на множині  f : кожна V - ФЧРФ є значенням деякого ОТ алгебри V - КЧРФ.

Изображение слайда
1/1
9

Слайд 9

9 Якщо f є значенням ОТ , то кажуть: –  – ОТ функції f, – функція f задана ОТ . Неоднозначність задання V - КЧРФ і V - ФЧРФ за допомогою ОТ: о, S х ( о,   s x ), S х ( о,   о ) та S х,у ( о,   о,   s x ) задають функцію о. Приклади V - КЧРФ При обмеженні на V - ФЧРФ – це приклади V - ФЧРФ. Приклад  1. Функції - константи – V - КЧРФ. Константи 0, 1, 2,... задаються ОТ о, S x ( s x, о ), S x ( s x, S x ( s x, о )),... ОТ для констант 1, 2,..., k,... позначимо 1, 2,..., k,...

Изображение слайда
1/1
10

Слайд 10

10 Пр и клад  2. Параметрична функція + xy є V - КЧРФ. + xy ( d ) = ' x ( d )+ ' y ( d ). Нехай x,  y  im ( d ). Тоді + xy ( d  y  0) = 'x ( d  y  0  z  0) = ' x ( d ); + xy ( d  y  b +1) = s z ( d  у  b  z  + xy ( d  y  b )). Отже, + xy утворена з базових ' v та s z за допомогою R y, z. ОТ функції + xy  : R y, z (' x, s z ). Позначимо його  xy. Пр и клад  3. Параметрична функція множення  xy є V - КЧРФ.  xy ( d ) = ' x ( d )  ' y ( d ). Нехай x,  y  im ( d ). Тоді  xy ( d  y  0) = о ( d  y  0  z  0) = о ( d ) = 0;  xy ( d  y  b +1) = ’x ( d )  ( b +1) = + x z ( d  y  b  z   xy ( d  y  b )). Отже,  xy утворена з о та + x z за допомогою R y, z. ОТ функції  xy  : R y, z (о,  x z ). Позначимо його  xy. 

Изображение слайда
1/1
11

Слайд 11

11 Приклад  4. Функція s g x задається так: s g x ( d )   =  0 при ‘x ( d ) = 0, s g x ( d )   = 1 при ‘x ( d ) > 0, s g x ( d )  при x  im ( d ). Така s g x є V - КЧРФ. sg x ( d  x  0) = о ( d  x  0  y  0) = о ( d ) = 0; sg x ( d  x  b +1 ) = 1. Функція sg x утворена з о та 1 за допомогою R x, y. ОТ функції sg x  : R x, y ( о, 1 ). Такий терм позначимо sg x. Приклад  5. Функція ns g x задається так: ns g x ( d )   = 1 при ‘x ( d ) = 0, ns g x ( d )   = 0 при ‘x ( d ) > 0, ns g x ( d )  при x  im ( d ). Така ns g x є V - КЧРФ. n sg x ( d  x  0) = 1; nsg x ( d  x  b +1 ) = 0. Функція nsg x утворена з 1 та о за допомогою R x, y. ОТ функції ns g x  : R x, y ( 1,   о ). П означимо його nsg x.

Изображение слайда
1/1
12

Слайд 12

12 Приклад  6. Параметрична функція ÷ xy задається так: ÷ xy ( d )   =  ‘x ( d )   – ‘y ( d ) при ‘x ( d )   ‘y ( d ), ÷ xy ( d )   =  0 при ‘x ( d )   ‘y ( d ), ÷ xy ( d )  при x  im ( d ) або y  im ( d ). Така ÷ xy є V - КЧРФ. Спочатку покажемо: функція ÷ x 1 є V - КЧРФ. Маємо ÷ x 1 ( d  x  0) = 0; ÷ x 1 ( d  x  b +1) = b = ' x ( d  x  b  y  ÷ x 1 ( d  x  b )). ОТ функції ÷ x 1 має вигляд R x, y ( о, ' x ). Маємо ÷ xy ( d  y  0) = ' x ( d ); ÷ xy ( d  y  b +1 ) = ÷ x 1 ( d  y  b  z    ÷ xy ( d  y  b )). Отже, ÷ xy утворена з ' x та ÷ z 1 за допомогою R y, z. ОТ функції ÷ xy   :  R y, z (' x, R z, y ( о, ' z )). П означимо його ÷ xy.

Изображение слайда
1/1
13

Слайд 13

13 Пр и клад  7. Параметрична функція |-| ху є V - КЧРФ. |-| ху ( d ) = |' x ( d ) – ' y ( d )| ОТ функції |-| ху  : S x, y (  xy, ÷ xy, ÷ yx ). П означимо його |–| xy. Пр и клад  8. Параметрична функція – ху є V - КЧРФ. – ху ( d ) = ' x ( d ) – ' y ( d ) Я кщо a = m – n, то a – це перше, починаючи з 0, таке число, що m  =  n + a, тобто |( n + a )– m | = 0. ОТ функції – ху має вигляд M z ( S v (|–| vx,  yz )). Приклад  9. Функція [ x/y ] є V - КЧРФ. [ x/y ] =  z ( y  ( z +1) > x ). ОТ функції [ x/y ] має вигляд M z ( S u,v (÷ uv, s x, S v (  yv, s z )). Приклад 10. Функція є V - КЧРФ. =  y (( y +1)  ( y +1) > x ). ОТ функції має вигляд M y ( S u,v (÷ uv, s x, S u,v (  uv, s y, s y )).

Изображение слайда
1/1
14

Слайд 14

14 Обчислюваність n -арних функцій на N. Примітивно-рекурсивні, частково рекурсивні та рекурсивні функції Основні обчислювані операції для n - арних функцій на N : – суперпозиції S n +1 – примітивної рекурсії R – мінімізації M. Операція S n +1 n - арній g ( x 1,..., x n ) та n функціям g 1 ( x 1,..., x m ),..., g n ( x 1,..., x m ) однакової арності зіставляє функцію f = S n +1 ( g, g 1,..., g n ): f ( x 1,..., x m ) = g ( g 1 ( x 1,..., x m ),..., g n ( x 1,..., x m )). Арність f збігається з арністю функцій g 1,..., g n.

Изображение слайда
1/1
Реклама. Продолжение ниже
15

Слайд 15

15 F n – клас усіх функцій на N фіксованої арності n, тобто N n  N. F – клас усіх n - арних функцій на N – об ’ єднання усіх F n. Операцію S n +1 можна розглядати як: – тотальну функцію F n  ( F m ) n  F m, – часткову ( n +1)- арну функцію на F. Твердження  1. Якщо функції g,   g 1,...,   g n тотальні та АОФ, то S n +1 ( g, g 1,..., g n ) тотальна та АОФ.

Изображение слайда
1/1
16

Слайд 16

16 Операція R n - арній функції g та ( n +2)- арній h зіставляє ( n   +   1)- арну f  =  R ( g,  h ), що задається рекурсивним визначенням f ( x 1,..., x n, 0) = g ( x 1,..., x n ); f ( x 1,..., x n, y + 1) = h ( x 1,..., x n, y, f ( x 1,..., x n, y )). Для всіх a 1,..., a n, b значення f ( a 1,..., a n, b ) обчислюється так : f ( a 1,..., a n,0) = g ( a 1,..., a n ) f ( a 1,..., a n,1) = h ( a 1,..., a n, 0, f ( a 1,..., a n, 0)) ................................. f ( a 1,..., a n, b ) = h ( a 1,..., a n, b – 1, f ( a 1,..., a n, b – 1)). Функція f однозначно визначається за функціями g та h.

Изображение слайда
1/1
17

Слайд 17

17 Якщо f ( a 1,..., a n,   b ) , то f ( a 1,..., a n,   t )  для всіх t  b. При n = 0 за визначенням функція g – це 1- арна константа. Твердження  2. Якщо функції g та h тотальні та АОФ, то R ( g,   h ) тотальна та АОФ. Операцію примітивної рекурсії R можна розглядати як: – тотальну функцію F n    F m +2  F n +1 ( при n = 0 – F 1    F 2  F 1 ), – часткову бінарну функцію на F.

Изображение слайда
1/1
18

Слайд 18

18 Операція M кожній ( n   +   1)- арній функції g зіставляє n - арну функцію f  =  M ( g ), що задається співвідношенням f ( x 1,..., x n ) =  y ( g ( x 1,..., x n, y ) = 0). Для всіх значень x 1,..., x n значення f ( x 1,..., x n ) обчислюється так. Послідовно обчислюємо g ( x 1,..., x n, y ) для y = 0, 1, 2,... Перше таке значення y, для якого g ( x 1,..., x n, y ) = 0 – шукане значення f ( x 1,..., x n ).  t   <   y необхідно g ( x 1,..., x n,   t )    0. Операцію мінімізації M можна розглядати як: – тотальну функцію F n +1  F n ( при n  = 0   – із F 1  F 1 ) – часткову 1- арну функцію на F. Процес знаходження  y ( g ( x 1,..., x n, y ) = 0) ніколи не закінчиться: – якщо g ( x 1,..., x n, 0)  – якщо для всіх значень y значення g ( x 1,..., x n, y )    0 – якщо для всіх t < y g ( x 1,..., x n, t )    0 та g ( x 1,..., x n, y ) .

Изображение слайда
1/1
19

Слайд 19

19 Не завжди найменше значення y таке, що g ( x 1,..., x n,   y ) = 0, збігається з  y ( g ( x 1,..., x n, y )   =   0). Для довільного значення x існує єдине значення y  =  x +1 таке, що y –( x +1) = 0. Однак функція  y ( y – ( x +1) = 0) усюди невизначена, тому що 0–( x +1) завжди невизначене. Твердження  3. Якщо функція g АОФ, то M ( g ) теж АОФ. Функція g може бути тотальною, а M ( g ) – навіть f . Наприклад, f ( x ) =  y ( x + y +1 = 0). Базові обчислювані n - арні функції : о ( x ) = 0, s ( x ) = x   +   1 та I m n ( x 1,..., x n ) = x m, де n  m  1. Вони тотальні й алгоритмічно обчислювані.

Изображение слайда
1/1
20

Слайд 20

20 Функцію, яку можна отримати з базових за допомогою скінченної кількості застосувань операцій суперпозиції та примітивної рекурсії, назвемо примітивно-рекурсивною ( ПРФ ). Функцію, яку можна отримати з базових за допомогою скінченної кількості застосувань операцій суперпозиції, примітивної рекурсії, мінімізації, назвемо частково рекурсивною ( ЧРФ ). Тотальну ЧРФ називають рекурсивною функцією ( РФ ). 1) кожна ПРФ – тотальна АОФ 2) кожна ЧРФ – АОФ 3) кожна РФ – тотальна АОФ. ПРФ  РФ  ЧРФ

Изображение слайда
1/1
21

Слайд 21

21 Алгебра ЧРФ ( алгебра Чорча ) – це алгебра (  ;  R,  M,  S 2,  S 3,...) носій  – клас усіх ЧРФ, операції – R, M, S n +1, де n  1. Алгебра ПРФ – це алгебра (  pR ;   R,  S 2,  S 3,...) носій  pR – клас усіх ПРФ, операції  – R, S n +1, де n  1. Операторні терми алгебри ЧРФ та алгебри ПРФ. Алфавіт мови алгебри ЧРФ: символи о, s, I m n, де n  m  1; R,   M,  S n +1, де n  1; допоміжні символи "(", ")", ",". Індуктивне визначення ОТ алгебри ЧРФ : 1) кожен символ базової функції є атомарним ОТ ; 2) якщо t 0, t 1,..., t n – ОТ, то S n +1 ( t 0, t 1,..., t n ) – ОТ ; 3) якщо t 1 та t 2 – ОТ, то R ( t 1, t 2 ) – ОТ ; 4) якщо t – ОТ, то M ( t ) – ОТ.

Изображение слайда
1/1
22

Слайд 22

22 Індуктивне визначення ОТ алгебри ПРФ : пп. 1, 2 та 3. Кожна ЧРФ є значенням деякого ОТ алгебри ЧРФ. Через порушення умов арності не кожен ОТ алгебри ЧРФ має певне значення: напр, R ( o, I 2 4 ), S 3 ( I 1 2, I 2 3, I 2 2 ) Якщо f є значенням ОТ , то кажуть: –  – ОТ функції f, – функція f задана ОТ . Неоднозначність задання ЧРФ за допомогою ОТ: о, S 2 ( s ), S 2 ( о, о ), S 3 ( о, S 2 ( о, s )) задають функцію о ( x ).

Изображение слайда
1/1
23

Слайд 23

23 Приклади ПРФ, ЧРФ та РФ Приклад 1. Функції - константи – ПРФ. n - арна о n ( x 1,..., x n ) = 0 задається ОТ S 2 ( о, I 1 n ); n - арна k n ( x 1,..., x n ) = k задається ОТ S 2 ( s, S 2 ( s,..., S 2 ( о, I 1 n )...). Пр и клад 2. Функція f ( x 1, x 2 ) = x 1 + x 2 – ПРФ. f ( x 1, 0) = x 1 = I 1 1 ( x 1 ); f ( x 1, x 2 +1) = x 1 + ( x 2 +1) = ( x 1 + x 2 )+1 = s ( x 1 + x 2 ) = s ( f ( x 1, x 2 )). x 1 + x 2 утворена примітивною рекурсією з функцій g ( x 1 ) =  I ( x 1 ) та h ( x 1, x 2, x 3 ) = x 3 +1 = s ( x 3 ) = S 2 ( s, I 3 3 )( x 1, x 2, x 3 ). ОТ функції x 1 + x 2 : R ( I 1 1, S 2 ( s, I 3 3 )). Позначимо його .

Изображение слайда
1/1
24

Слайд 24

24 Приклад  3. Функція f ( x 1, x 2 ) = x 1  x 2 – ПРФ. f ( x 1, 0) = 0 = о ( x 1 ); f ( x 1, x 2 +1) = x 1  ( x 2 +1) = x 1  x 2 + x 1 = f ( x 1, x 2 ) + x 1. x 1  x 2 утворена R з функцій g ( x 1 ) =  о ( x 1 ) та h ( x 1,   x 2,   x 3 ) = x 3 + x 1. ОТ функції x 1  x 2 : R ( о, S 3 ( ,   I 3 3, I 1 3 )).. Приклад  4. 1-арна функція sg задається так: s g ( x )   =  0 при x  = 0, s g ( x )   = 1 при x  1. Така sg ( x ) є ПРФ. sg (0) = 0 = о ( x ); sg ( x +1) = 1. ОТ функції sg ( x ): R ( о, S 2 ( s, S 2 ( о, I 1 2 ))). Приклад  5. 1-арна функція n sg задається так: ns g ( x )   = 1 при x  = 0, ns g ( x )   = 0 при x  1. Така n sg є ПРФ. ОТ функції ns g ( x ): R ( S 2 ( s, о ), S 2 ( о, I 1 2 )).

Изображение слайда
1/1
25

Слайд 25

25 Приклад  6. Функція f ( x 1, x 2 ) = x 1   ÷   x 2 задається так: x 1   ÷   x 2 = x 1 – x 2 при x 1  x 2, x 1   ÷   x 2 = 0. при x 1  x 2, Така x 1   ÷   x 2 є ПРФ. Спочатку покажемо, що функція x 1   ÷ 1 – ПРФ. 0   ÷ 1 = 0 = о ( x 1 ); ( x 1 +1)   ÷ 1 = x 1 = I 1 2 ( x 1, x 2 ). ОТ функції x 1   ÷ 1 : R ( о, I 1 2 ). Тепер покажемо, що f ( x 1, x 2 ) = x 1   ÷   x 2 – ПРФ. Маємо f ( x 1, 0) = x 1   ÷ 0 = I 1 1 ( x 1 ); f ( x 1, x 2 +1) = ( x 1   ÷   x 2 )   ÷   1 = f ( x 1, x 2 ) ) ÷   1. x 1   ÷   x 2 утворена примітивною рекурсією з функцій g ( x 1 ) = I 1 1 ( x 1 ) та h ( x 1, x 2, x 3 ) = x 3  ÷   1. ОТ функції x 1   ÷   x 2 : R ( I 1 1, S 2 ( R ( о, I 1 2 ), I 3 3 )).

Изображение слайда
1/1
26

Слайд 26

26 Приклад  7. Функція f ( x 1, x 2 ) = | x 1  –   x 2 | = ( x 1   ÷   x 2 ) + ( x 2  ÷   x 1 ) – ПРФ. Пр и клад  8. Функція f ( x 1, x 2 ) = x 1  –   x 2 – ЧРФ. x 1 – x 2 =  x 3 ( x 1 = x 2 + x 3 ) =  x 3 (| x 1 –   ( x 2 + x 3 )| = 0). Пр и клад  9. Функція f ( x 1, x 2 ) = [ x 1 / x 2 ] – ЧРФ. [ x 1 / x 2 ] =  x 3 ( x 2  ( x 3 +1) > x 1 ) =  x 3 ( nsg ( x 2  ( x 3 +1)   ÷   x 1 ) = 0). Пр и клад 10. Функція f ( x 1 ) = – РФ. =  x 2 (( x 2 +1)  ( x 2 +1) > x 1 ) =  x 2 ( nsg (( x 2 +1)  ( x 2 +1)   ÷   x 1 ) = 0). Приклад 1 1. Усюди невизначена функція f  – ЧРФ. f  ( x 1 ) =  x 2 ( x 1 +1 = 0), тому f  – значення ОТ М ( s ).

Изображение слайда
1/1
27

Слайд 27

27 Властивості ПРФ і РФ. Позначаємо x n +1 та x n +2 як y та z. При z < y вважаємо = 0. Теорема  1. Нехай ( n +1)- арна функція g є ПРФ. Тоді ( n +1)- арна функція f ( x 1,..., x n, y ) = – ПРФ.  f ( x 1,..., x n, 0) = g ( x 1,..., x n, 0); f ( x 1,..., x n, t +1) = f ( x 1,..., x n, t ) + g ( x 1,..., x n, t +1). Функція f утворена примітивною рекурсією з g ( x 1,..., x n, 0) та h ( x 1,..., x n,   y,  z ) =  z + g ( x 1,..., x n, y +1)

Изображение слайда
1/1
28

Слайд 28

28 Тeорeма   2. Нехай ( n +1)- арна функція g є ПРФ. Тод i ( n +2)- арна – ПРФ. Теорема  3. Нехай ( n +1)- арна функція g та n- арні p та q – ПРФ. Тоді n- арна функція h ( x 1,...,  x n ) = – ПРФ. h ( x 1,..., x n ) = f ( x 1,..., x n, p ( x 1,..., x n ), q ( x 1,..., x n )), де f – із теореми 2 Теореми 1–3 – теореми про підсумовування. Замінивши в них символ  на , одержимо теореми про мультиплікацію.

Изображение слайда
1/1
29

Слайд 29

29 Пр и клад  1 2. Довизначи мо f ( x 1,   x 2 ) =  [ x 1 / x 2 ] так : [ x 1 /0] =  x 1. Тоді функція [ x 1 / x 2 ] є ПРФ. Значення [ a / b ] рівне кількості нулів у послідовності 1  b   ÷   a, 2  b   ÷   a,..., a  b   ÷   a. Тому Приклад  13. Функція mod ( x 1, x 2 ) є ЧРФ. mod ( x 1, x 2 ) = x 1 ÷   ( x 2  [ x 1 / x 2 ]). Беручи довизначену [ x 1 / x 2 ], дістанемо довизначену функцію mod ( x 1,   x 2 ): mod ( x 1, 0) = 0. Довизначена mod ( x 1,   x 2 ) є ПРФ.

Изображение слайда
1/1
30

Слайд 30

30 ( n +1)- арна функція f отримується з ( n +1)- арної функції  g за допомогою операції обмеженої мінімізації, якщо f задається умовою : f ( x 1,..., x n, у ) – це перше, починаючи з 0 значення z таке, що z  у та g ( x 1,..., x n, у )   =   0, якщо таке значення z існує, інакше f ( x 1,..., x n,   у )   =   у. Це позначаємо так : f ( x 1,..., x n, y )   =    x  y (( g ( x 1,..., x n, z ) = 0). Теорема  4 ( про обм e ж e ну мінімізацію ). Нехай ( n +1) - арна функція g є ПРФ. Тоді ( n +1)- арна f ( x 1,..., x n,  y ) =  z  y (( g ( x 1,...,   x n,  z ) = 0) є ПРФ. Функцію позначимо q ( x 1,..., x n,  z ). Зафіксуємо значення x 1,..., x n, y. Нехай  z  y (( g ( x 1,..., x n, z ) = 0) = b. Тоді q ( x 1,..., x n, z ) рівне 1 при z  b та 0 при z  b. Звідси . Наслідок. Нехай g ( x 1,..., x n,   y ) та h ( x 1,..., x n ) є ПРФ. Тоді функція є ПРФ.

Изображение слайда
1/1
31

Последний слайд презентации: 1 ОБЧИСЛЮВАНІСТЬ КВАЗІАРНИХ ФУНКЦІЙ НА N Розглядаємо спосіб задання

31 Приклад  12. Функція f ( x ) = є ПРФ. =  x  y (( nsg (( y +1)  ( y +1) ÷   x ) = 0). Пр и клад  13. Довизначи мо f ( x 1,   x 2 ) =  [ x 1 / x 2 ] так : [ x 1 /0] =  x 1. Тоді функція [ x 1 / x 2 ] є ПРФ. Значення [ a / b ] рівне кількості нулів у послідовності 1  b   ÷   a, 2  b   ÷   a,..., a  b   ÷   a. Тому Приклад  14. Функція mod ( x 1, x 2 ) є ЧРФ. mod ( x 1, x 2 ) = x 1 ÷   ( x 2  [ x 1 / x 2 ]). Беручи довизначену [ x 1 / x 2 ], дістанемо довизначену функцію mod ( x 1,   x 2 ): mod ( x 1, 0) = 0. Довизначена mod ( x 1,   x 2 ) є ПРФ.

Изображение слайда
1/1
Реклама. Продолжение ниже