Презентация на тему: 1 Примітивно-рекурсивні, рекурсивні, рекурсивно-перелічні множини Множина M  N

Реклама. Продолжение ниже
1 Примітивно-рекурсивні, рекурсивні, рекурсивно-перелічні множини Множина M  N
1 Примітивно-рекурсивні, рекурсивні, рекурсивно-перелічні множини Множина M  N
1 Примітивно-рекурсивні, рекурсивні, рекурсивно-перелічні множини Множина M  N
1 Примітивно-рекурсивні, рекурсивні, рекурсивно-перелічні множини Множина M  N
1 Примітивно-рекурсивні, рекурсивні, рекурсивно-перелічні множини Множина M  N
1 Примітивно-рекурсивні, рекурсивні, рекурсивно-перелічні множини Множина M  N
1 Примітивно-рекурсивні, рекурсивні, рекурсивно-перелічні множини Множина M  N
1 Примітивно-рекурсивні, рекурсивні, рекурсивно-перелічні множини Множина M  N
1 Примітивно-рекурсивні, рекурсивні, рекурсивно-перелічні множини Множина M  N
1 Примітивно-рекурсивні, рекурсивні, рекурсивно-перелічні множини Множина M  N
1 Примітивно-рекурсивні, рекурсивні, рекурсивно-перелічні множини Множина M  N
1 Примітивно-рекурсивні, рекурсивні, рекурсивно-перелічні множини Множина M  N
1 Примітивно-рекурсивні, рекурсивні, рекурсивно-перелічні множини Множина M  N
1 Примітивно-рекурсивні, рекурсивні, рекурсивно-перелічні множини Множина M  N
1 Примітивно-рекурсивні, рекурсивні, рекурсивно-перелічні множини Множина M  N
1 Примітивно-рекурсивні, рекурсивні, рекурсивно-перелічні множини Множина M  N
1 Примітивно-рекурсивні, рекурсивні, рекурсивно-перелічні множини Множина M  N
1 Примітивно-рекурсивні, рекурсивні, рекурсивно-перелічні множини Множина M  N
1 Примітивно-рекурсивні, рекурсивні, рекурсивно-перелічні множини Множина M  N
1 Примітивно-рекурсивні, рекурсивні, рекурсивно-перелічні множини Множина M  N
1 Примітивно-рекурсивні, рекурсивні, рекурсивно-перелічні множини Множина M  N
1 Примітивно-рекурсивні, рекурсивні, рекурсивно-перелічні множини Множина M  N
1 Примітивно-рекурсивні, рекурсивні, рекурсивно-перелічні множини Множина M  N
1 Примітивно-рекурсивні, рекурсивні, рекурсивно-перелічні множини Множина M  N
1 Примітивно-рекурсивні, рекурсивні, рекурсивно-перелічні множини Множина M  N
1 Примітивно-рекурсивні, рекурсивні, рекурсивно-перелічні множини Множина M  N
1 Примітивно-рекурсивні, рекурсивні, рекурсивно-перелічні множини Множина M  N
1 Примітивно-рекурсивні, рекурсивні, рекурсивно-перелічні множини Множина M  N
1 Примітивно-рекурсивні, рекурсивні, рекурсивно-перелічні множини Множина M  N
1 Примітивно-рекурсивні, рекурсивні, рекурсивно-перелічні множини Множина M  N
1 Примітивно-рекурсивні, рекурсивні, рекурсивно-перелічні множини Множина M  N
1 Примітивно-рекурсивні, рекурсивні, рекурсивно-перелічні множини Множина M  N
1 Примітивно-рекурсивні, рекурсивні, рекурсивно-перелічні множини Множина M  N
1 Примітивно-рекурсивні, рекурсивні, рекурсивно-перелічні множини Множина M  N
1 Примітивно-рекурсивні, рекурсивні, рекурсивно-перелічні множини Множина M  N
1 Примітивно-рекурсивні, рекурсивні, рекурсивно-перелічні множини Множина M  N
1/36
Средняя оценка: 4.3/5 (всего оценок: 76)
Код скопирован в буфер обмена
Скачать (223 Кб)
Реклама. Продолжение ниже
1

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

1 Примітивно-рекурсивні, рекурсивні, рекурсивно-перелічні множини Множина M  N n рекурсивна (РМ) : характеристична функція  M рекурсивна. Множина M  N n примітивно-рекурсивна (ПРМ) :  M примітивно-рекурсивна. Кожна ПРМ є рекурсивною множиною. Множина M  N рекурсивно-перелічна (РПМ), якщо M  =   або M = E f для деякої РФ f. Множина M  N n н РПМ, якщо M =  або існують 1-арні РФ g 1,..., g n такі, що M = {( g 1 ( x ),..., g n ( x )) | x  N }. Наслідки тези Чорча: – клас РМ збігається з класом алгоритмічно розв’язних множин на N – клас РПМ збігається з класом алгоритмічно перелічних множин на N

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

Слайд 2

2 Для L  N n визначимо множину-згортку: C n ( L ) = { C n ( x 1,..., x n ) | ( x 1,..., x n )  L }. Нехай L  N n та M  N n. C n ( L  M ) = C n ( L )  C n ( M ), C n ( L  M ) = C n ( L )  C n ( M ), C n ( N n \ L ) = N \ C n ( L ). Теорема 1. L  N n є РМ ( ПРМ, РПМ )  C n ( L ) є РМ ( ПРМ, РПМ ). Нехай L  N є РМ   L ( x 1,...,  x n ) є Р =  L ( C n 1 ( x ),  ...,   C nn ( x )) Нехай C n ( L ) є РМ  є РФ  L ( x 1,..., x n ) = Нехай L  N n є РПМ  L  = {( g 1 ( x ),..., g n ( x )) | x  N } для РФ g 1,...,  g n. C n ( g 1 ( x ),..., g n ( x )) є РФ  C n ( L ) = { C n ( g 1 ( x ),..., g n ( x )) | x  N } є РПМ Нехай C n ( L ) є РПМ  C n ( L ) = { g ( x ) |  x  N } для деякої РФ g. C n 1 ( g ( x )),..., C nn ( g ( x )) РФ  L  = {( C n 1 ( g ( x )),..., C nn ( g ( x ))) | x  N } є РПМ. .

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

Слайд 3

3 Теорема 2. 1) кожна скінченна множина є ПРМ ; 2) кожна рекурсивна множина є РПМ ; 3) клас ПРМ строго включається в клас РМ. 1) Нехай L = { a 1,..., a n }. Тоді 2) Нехай L  N є РМ. Якщо L = , то L є РПМ. L   зафіксуємо b  L.  L є РФ  f ( x ) =  x   L ( x ) + b  nsg (  L ( x )) є РФ, L  =  E f. Отже, L є РПМ. 3) Нехай u ( t,  x ) –універсальна РФ для ПРФ 1. Тоді f ( x ) =  nsg ( u ( x,  x )) – х.ф. деякої РМ L. f ( x ) є ПРФ  за універсальністю u ( t,  x )  k  N : f ( x )     u ( k,  x ) f ( k ) =  u ( k,  k ) =   nsg ( u ( k,   k )) – суперечність  f ( x ) не ПРФ  L не ПРМ Теорема 3. Класи ПРМ та РМ замкнені відносно , , доповнення  Нехай  A та  B є РФ (ПРФ).   A ( x ) = nsg (  A ( x ) )  A  B ( x ) = sg (  A ( x )+  B ( x ))  A  B ( x ) =  A ( x )   B ( x )

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

Слайд 4

4 Теорема 4. L є нескінченна РМ  L = E f для деякої строго  РФ f. Для строго  функцій f ( x )      x  x  D f  f є РФ  E f є РМ. Нехай L – нескінченн a РМ. Задамо f схемою примітивної рекурсії f (0) =  k (  L ( k )=1); f ( x + 1) =  k (  L ( k )=1 та k > f ( x )). За побудовою L = E f ; f строго , тотальна ( L нескінченн a), РФ Теорема   5. L – нескінченна РПМ  існує нескінченна РМ M  L L – нескінченна РПМ  L = E g для деякої РФ g. Задамо f f (0) = g (0); f ( x +1) = g (  k ( g ( k )> f ( x )). За побудовою f строго , тотальна ( E g нескінченн a), РФ. За теоремою 4 E f – некінченна РМ, E f    E g  =   L  E f – шукана M.

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

Слайд 5

5 Теорема 6. L – нескінченна РПМ  існує ін’єктивна РФ f : L = E f. Маємо L = E g для деякої РФ g. Функцію f задамо схемою примітивної рекурсії f (0) = g (0); f ( x +1) = g (  k ( g ( k )  f (0),..., g ( k )  f ( x ))) За нескінченністю E g РФ f ін’єктивна й тотальна, E f   =   E g  =   L.

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

Слайд 6

6 Теорема 7. Існує РФ  :  x  N E  ( x )   =   D x та   ( x ) є РФ при D x  . Зафіксуємо x  N. Задамо ефективний процес поетапного породження D x, формуючи список елементів D x з повторами. Крок обчислення – виконання однієї команди МНР-програми (МТ) Етап 1. 1-й крок обчислення  x (0); якщо  x (0) обчислене, то 0 до списку Етап n +1. Робимо по n +1 кроків обчислення для  x (0),  x (1),...,  x ( n ); усі k  n, для яких  x ( k ) обчислене, – до списку. Задамо f ( x, y ) так.  фіксованого x  N f ( x, 0) є 1-м елементом списку; За ТЧ f є ЧРФ  за s - m - n  РФ   ( x ):  x, y f ( x, y ) =   ( x ) ( y ) За побудовою E  ( x ) = D x. D x =     ( x ) = f . D x    f ( x,  y )   y  N    ( x ) тотальна    ( x ) є РФ.

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

Слайд 7

7 Теорема   8. Існують РФ s та t :  x  N маємо E s ( x )  =  D x та D t ( x ) = E x. За s - m - n -теоремою  РФ  t ( x ):  x,  y f ( x,  y ) =   t ( x ) ( y ). y  E x  f ( x,  y )    t ( x ) ( y )   y  D t ( x ). Звідси D t ( x ) = E x. За s - m - n -теоремою  РФ  s ( x ):  x,  y g ( x,  y ) =   s ( x ) ( y ). За побудовою E s ( x )  =   D s ( x ). y  D x  f ( x,  у )    s ( x ) ( y )   y  D s ( x )  y  E s ( x ). Звідси D x = E s ( x ) Теорема   9. Існує РФ  :  x  N E  ( x ) = Е x та   ( x ) є РФ при Е x  . Для функцій , t з теорем 7 та 8 маємо:  x  N D t ( x )   =   E x ; E  ( x )  =   D x та   ( x ) є РФ при D x  . Тоді  x  N E  ( t ( x ))  =   D t ( x )  =   E x та   ( t ( x )) є РФ при D t ( x )  =   E x      . РФ  ( x ) =   ( t ( x )) – шукана.

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

Слайд 8

8 Теорема 10. Такі визначення РПМ еквівалентні : df 1) L =  або L є областю значень деякої РФ ; df 2) L є областю значень деякої ЧРФ ; df 3) L є областю визначення деякої ЧРФ ; df 4) часткова характеристична функція L є ЧРФ. df 1  df 2 та df 4  df 3 є очевидними. df 3  df 1. Нехай L = D ЧРФ, x – індекс такої ЧРФ, тобто L = D x. Для РФ  ( x ) з теореми 7 E  ( x ) = D x, причому   ( x ) є РФ при D x . Отже, або D x = , або D x = E  ( x ) та   ( x ) є РФ. Аналогічно (викор. теорему 9) df 2  df 1. df 2  df 3 випливає з теореми 8. df 3  df 4. Нехай L = D f для деякої ЧРФ f. Тоді  ч L ( x ) = s ( o ( f ( x ))). Rm. df 3 та df 4 можна використовувати для РПМ, заданих на N n.

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

Слайд 9

9 Стандартна нумерація РПМ Ефективну нумерацію РПМ вводимо згідно df 3 Номером РПМ L  N n є номер n -арної ЧРФ f : L = D f. РПМ L  N n із номером (індексом) m позначаємо D m n для n =1 позначаємо D m { L  N n | L є РПМ} позначаємо РПМ n. Аналогічно – позначення РМ n та ПРМ n. Теорема 11. Клас РПМ замкнений відносно  та . Нехай f та g – РФ : A = E f та B = E g. Задамо h ( 2  x )  =  f ( x ), h (2  x +1) =  g ( x ). Тоді h є РФ, E h  =   E f  E g  =   A  B  A  B – РПМ.  ч A  B ( x ) =  ч A ( x )   ч B ( x ) – ЧРФ  з a df 4 A  B є РПМ.

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

Слайд 10

10 Теорема 12 (узагальнена Поста). A, B – РПМ, A  B = , A  B – РМ  A, B – РМ. Нехай A , B . Нехай f, g – такі РФ: A = E f та B = E g. Укажемо алгоритм , який за b  N визначає, b  A чи b  A. Задамо h ( 2  x )  =  f ( x ), h (2  x +1) =  g ( x ). Тоді h є РФ, E h  =   E f      E g  =   A  B. Множина A  B рекурсивна, тому алгоритмічно розв’язна. Якщо b  A  B, то b  A. Якщо b  A  B, то обчислюємо h (0), h (1),  ... Маємо E h  =   A  B  b  =  h ( n ) для деякого n. n парне  b   =   h ( n )   =   f ( n /2)  b  A. n непарне  b   =   h ( n )   =   g (( n– 1)/2)  b  B  b  A за A  B =  A алгоритмічно розв’язна  за ТЧ A є РМ. Аналогічно B є РМ Наслідок (теорема Поста). L та  L – РПМ  L та  L – РМ

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

Слайд 11

11 Теорема   13 (принцип редукції).  РПМ A та B  РПМ L та M такі : L  A, M  B, L  M = , L  M = A  B. Вважаємо A , B , A      B (інакше твердження тривіальне). Візьмемо a  A та b  B такі, що a      b. Нехай f та g – такі РФ: A = E f та B = E g. Задамо функції u та v : За ТЧ u та v є РФ. L = E u та M = E v задовольняють умову теореми

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

Слайд 12

12 Для L  N введемо позначення L 2 x ={2 x | x  L } та L 2 х +1 = {2 x +1 | x  L }. Для множин на N визначимо операції сполучення  та добутку  : A  B = {2 x | x  A }  {2 x +1| x  B } = A x  B 2 x +1 ; A  B = { C ( x, y )| x  A, y  B }. Теорема   14 1) A та B є РМ /РПМ  A  B є РМ /РПМ. 2)   Якщо A , B , то A та B є РМ /РПМ  A  B є РМ /РПМ. Доведемо для РПМ. Для РМ замість ч.х.ф. беремо х.ф. 1) x  A  B  ( x парне та x /2  A ) або ( x  непарне та ( x –1)/2  B ). A, B є РПМ  за ТЧ  ч A  B є ЧРФ  A  B є РПМ. x  A  2 x  A  B та x  B  2 x +1  A  B.  ч A ( x ) =  ч A  B (2 x ),  ч B ( x ) =  ч A  B (2 x +1). Тому A  B РПМ  A, B РПМ. 2)   x  A  B  l ( x )  A та r ( x )  B, звідки  ч A  B ( x ) =  ч A ( l ( x ))   ч B ( x ). Зафікс. a  A, b  B. Тоді x  A  C ( x,  b )  A  B та x  B  C ( a,  x )  A  B. Тому  ч A ( x ) =  ч A  B ( C ( x,  b )) та  ч B ( x ) =  ч A  B ( C ( a,  x )).

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

Слайд 13

13 Примітивно-рекурсивні, рекурсивні, ч астково рекурсивні предикати n -арний предикат P на N рекурсивний, якщо  P є РФ n -арний предикат P на N примітивно-рекурсивнй, якщо  P є ПРФ n -арний предикат P на N частково рекурсивний, якщо  ч P є ЧРФ. Теорема 1. 1) P є ЧРП ( РП, ПРП )  T P є РПМ ( РM, ПРМ ); 2) класи ПРП та РП замкнені відносно , & та  ; 3) клас ЧРП замкнений відносно  та &; 4) клас ПРП строго включається в клас РП ; 5) кожний РП є ЧРП ; 6) якщо P та  P – ЧРП, то P та  P – РП. Тв. 1) випливає з визначень. T P  Q = T P  T Q, T P & Q = T P  T Q, T  P =  T P З урахув. 1) тв. 2) –6) випливають з відп. теорем для РМ, РПМ. Наслідки ТЧ : – клас РП збігається з класом алгоритмічно розв’язних предикатів на N – клас ЧРП збігається з класом позитивно розв’язних предикатів на N

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

Слайд 14

14 Теорема 2. Q ( x 1,...,  x n ) є ЧРП  існує РП R ( x 1,...,  x n,  y ) такий : Q ( x 1,...,  x n )   yR ( x 1,..., x n, y ). Нехай Q – ЧРП, нехай  ч Q обчислюється МНР-програмою P. Маємо Q ( x 1,..., x n )   y ( P ( x 1,..., x n )  за k кроків) " P ( x 1,..., x n )  за k кроків" позначимо R ( x 1,…, x n, y ). За ТЧ R є РП Нехай R ( x 1,...,  x n,  y ) – РП, нехай Q ( x 1,...,  x n )   yR ( x 1,...,  x n,  y ). Тоді Q ( x 1,...,  x n )   R ( x 1,..., x n, y ) = 1. f ( x 1,..., x n ) = s ( o (  y ( nsg (  R ( x 1,..., x n, y )) = 0)) – ч.х.ф.  yR ( x 1,..., x n, y ). Маємо f =  ч Q,  R є РФ  f є ЧРФ  Q є ЧРП

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

Слайд 15

15 Теорема 3. Нехай Q ( x 1,...,  x n,  y ) є ЧРП. Тоді  yQ ( x 1,...,  x n,  y ) теж ЧРП. Q ( x 1,..., x n, y ) є ЧРП  (теорема 2) існує РП R ( x 1,...,  x n,  y,  z ): Q ( x 1,...,  x n,  y )   zR ( x 1,...,  x n,  y,  z ). Поклавши u  =  C ( y,  z ), звідси  yQ ( x 1,...,  x n,  y )   y  zR ( x 1,...,  x n,  y,  z )    u R ( x 1,...,  x n,  l ( u ),  r ( u )). l та r є ПРФ, R ( x 1,...,  x n,  y,  z ) є РП  R ( x 1,..., x n, l ( u ), r ( u )) є РП. Тоді  uR ( x 1,..., x n, l ( u ), r ( u )), а з ним і  yQ ( x 1,..., x n, y ), є ЧРП за теоремою 2 Наслідок. Якщо Q ( x 1,..., x n, y ) є ЧРП, то  y 1...  y k Q ( x 1,..., x n, y 1,..., у k ) теж ЧРП.

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

Слайд 16

16 Приклад 1. Предикат " y  E x " є ЧРП. y  E x   z  k ( P x ( z )  y за k кроків). В дужках – РП, тому за теоремою 2 " y  E x " є ЧРП Приклад 2. Предикат " D x   " є ЧРП. D x    z  k ( P x ( z )  за k кроків). В дужках – РП, тому за теоремою 2 " D x   " є ЧРП Приклад 3. Предикат "{ x, y }  D z " є ЧРП. { x, y }  D z  x  D z & y  D z    k ( P z ( x )  y за k кроків) &  k ( P z ( y )  y за k кроків). В дужках РП, тому "{ x, y }  D z " є ЧРП. Приклад 4. Предикат "  x неін ' єктивна " є ЧРП.  x неін'єктивна   a  b  c ( a  b &  x ( a ) = c &  x ( b ) = c )    a  b  c  k  l ( a  b &( P x ( a )  c за k кр.) & ( P x ( b )  c за l кр.)).

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

Слайд 17

17 Теорема 4. f ( x 1,..., x n ) є ЧРФ  предикат " y   =   f ( x 1,..., x n )" є ЧРП. Нехай f ( x 1,..., x n ) є ЧРФ, P – МНР-програма для f. Тоді y  =  f ( x 1,..., x n )   k ( P ( x 1,..., x n )  y за k кроків). " P ( x 1,...,  x n )  y за k кроків" є РП  " y = f ( x 1,..., x n )" є ЧРП. Нехай " y = f ( x 1,..., x n )" – ЧРП. За теоремою2 існує РП R : y  =  f ( x 1,..., x n )   zR ( x 1,..., x n, y, z ). Покладемо t = C ( y,   z ), тоді y   =   f ( x 1,..., x n )   tR ( x 1,..., x n, l ( t ), r ( t )). Покладемо g ( x 1,..., x n, t )   =   nsg (  R ( x 1,..., x n, l ( t ), r ( t ))). Тоді  tR ( x 1,..., x n, l ( t ), r ( t ))   t ( y   =   l ( t ) та g ( x 1,...,  x n,  t ) = 0). Узявши перше таке t, маємо  t ( y   =   l ( t ) та g ( x 1,..., x n, t ) = 0)  y   =   l (  t ( g ( x 1,..., x n, t ) = 0). Отже, y   =   f ( x 1,...,  x n )  y   =   l (  t ( g ( x 1,..., x n, t ) = 0)), тому f є ЧРФ

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

Слайд 18

18 Нормальна форма Кліні Теорема 5 (Кліні про нормальну форму). Для кожної n-арної ЧРФ f існує ( n +1)- арна РФ g :  x 1,..., x n  N f ( x 1,..., x n ) = l (  t ( g ( x 1,..., x n, t )   =   0)). Подання l (  t ( g ( x 1,...,  x n,  t )   =   0)) – нормальна форма функції f ( x 1,..., x n ). За теоремою 4 " y   =   f ( x 1,...,  x n )" є ЧРП, тому для деякого РП R y   =   f ( x 1,..., x n )   zR ( x 1,..., x n, y, z ). Покладемо g ( x 1,..., x n, t ) = nsg (  R ( x 1,..., x n, l ( t ), r ( t ))). Повторюючи доведення теореми 4, маємо y   =   f ( x 1,..., x n )  y = l (  t ( g ( x 1,..., x n, t ) = 0)). Отже, f ( x 1,..., x n ) = l (  t ( g ( x 1,..., x n, t ) = 0)) Функцію g можна брати з класу ПРФ (посилений варіант теореми 5) У цьому випадку теорема Кліні про НФ засвідчує, що кожну ЧРФ можна отримати з деякої ПРФ не більше ніж одним застосуванням операції мінімізації, причому певним стандартним чином.

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

Слайд 19

19 Алгоритмічна нерозв’язність проблем зупинки та самозастосовності Масова проблема ( алгоритмічно ) розв’язна, якщо відповідний предикат рекурсивний, інакше проблема нерозв’язна Масова проблема частково розв’язна ( напіврозв’язна, позитивно розв’язна ) якщо відповідний предикат є ЧРП " x є квадратом натурального числа" " P ( x 1,...,  x n )  за k кроків" – алгоритмічно розв’язні. Проблема зупинки : за x та y встановити,  x ( y )  чи  x ( y ) . Проблема самозастосовності : за x встановити,  x ( x )  чи  x ( x ) . Неформально: установити за x, чи зупиниться МНР-програма з кодом x при роботі над власним кодом. "  x ( y ) визначене" позначимо Q ( x,   y ). "  x ( x ) визначене" позначимо S ( x ). S ( x )  Q ( x, x )

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

Слайд 20

20 Теорема 1. Проблема самозастосовності алгоритмічно нерозв’язна. Припустимо супротивне: предикат S ( x ) рекурсивний. Тоді Нехай n – індекс f в нумерації ЧРФ 1, тобто f ( x )   n ( x ). Тоді Наслідок. Проблема зупинки алгоритмічно нерозв’язна. Супротивне  Q ( x,  y ) є РП S ( x ) є РП – суперечність теоремі 1.

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

Слайд 21

21 Теорема 2. Проблеми зупинки та самозастосовності напіврозв’язні. Алгоритм  обчислення  ч Q : за x – P x і обчислюємо P x ( y ). P x ( y )    видає 1 як результат P x ( y )    ніколи не видасть результату   ч Q ( x,   y )  За ТЧ  ч Q є ЧРФ  Q є ЧРП. Але  ч S ( x ) =    ч Q ( x, х )  S теж ЧРП. Теорема 3. D  = { x  |   x ( x )  визначене } – нерекурсивна РПМ.  D   =    S – не РФ за теоремою 1. D – область визначення ЧРФ u ( x ) =  x ( x ), тому D є РПМ. Наслідок 1. Множина  D = { x |  x ( x ) невизначене } не є РПМ. Супротивне:  D є РПМ  за теор. Поста  D та D є РМ – суп-ть Наслідок 2. Предикат  S ( x ) не є ЧРП Наслідок 3. Клас РПМ незамкнений відносно доповнення Наслідок 4. Клас ЧРП незамкнений відносно  та  x

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

Слайд 22

22 Теорема 4. ПРФ  РФ  ЧРФ СкМ  ПРМ  РМ  РПМ ПРП  РП  ЧРП g – розширення функції f, якщо D f  D g та  x  D f f ( x ) = g ( x ) тоді f – звуження функції g. Позначення: f  g Тотальне розширення функції – довизначення цієї функції. Теорема 5. Функція  x ( x ) не має рекурсивних довизначень. Супротивне:  x ( x ) має рек. довизначення f ( x )  nsg (  x ( x )) має рек. довизначення g ( x ). Нехай k – індекс g в нумерації ЧРФ 1, тобто g =  k g є РФ   k ( k ) =  g ( k )   nsg (  k ( k ))  Маємо nsg (  k ( k ))   =   g ( k )   =  k ( k ) – суперечність.

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

Слайд 23

23 Операція мінімізації  у істотно відрізняється від неконструктивної операції m i n y для знаходження найменшого y, яке задовольняє певну умову. f ( x 1,..., x n ) виникає з g ( x 1,..., x n, y ) за допомогою операції mіn y, якщо: Теорема 6. Існує ЧРФ h така, що f ( x ) = m i n y ( h ( x, y ) = 0) не є ЧРФ. f ( x ) = m i n y  ( h ( x,  y ) = 0) тотальна:  x  N f ( x ) = 1 або f ( x ) = 0. x  D  h ( x, 0) = 0  f ( x ) = 0. x  D  h ( x, 0) , але h ( x,1) = 1  f ( x ) = 1. Отже, f ( x ) = nsg  D ( x ))  f не є РФ і не є ЧРФ.

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

Слайд 24

24 Співвідношення між класами функцій та їх графіків Теорема 1. 1) Якщо функція f є ПРФ /РФ, то  f є ПРМ /РМ. 2) Існують нерекурсивні ЧРФ зі скінченним графіком. 3) Існує РФ f така, що  f не є ПРМ. Для 1):   f   ( x 1,..., x n, y ) = nsg (| y   –   f ( x 1,..., x n )|) Для 2): скінченні функції не є РФ. Для 3): f ( x ) =  nsg ( u ( x,  x )), де u ( t,  x ) – універсальна РФ для ПРФ 1.   f   ( x,  y ) =  nsg (| y – f ( x )|) є ПРФ     f   ( x, 1) =  nsg (|1– nsg ( u ( x,  x ))|) =  nsg ( u ( x,  x )) =  f ( x ) теж ПРФ. Однак u ( t,  x ) не є ПРФ  тому   f   не ПРФ   f не є ПРМ. Теорема 2 (про графік). Функція f ( x 1,..., x n ) є ЧРФ   f є РПМ.  f = {( x 1,..., x n, y ) | ( x 1,..., x n )  D f та y = f ( x 1,..., x n )} – область істинності предиката " y = f ( x 1,..., x n )". Q є ЧРП  T Q є РПМ   f є РПМ.

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

Слайд 25

25 Теорема   3 (Сколем).  f є РМ/ПРМ  існує РФ/ПРФ g така :  x 1,..., x n  N маємо f ( x 1,..., x n ) =  t ( g ( x 1,..., x n, t ) = 0). Наслідок 1. Існують РФ f, які не можна подати у вигляді f ( x 1,..., x n ) =  t ( g ( x 1,..., x n, t ) = 0) для деякої ПРФ g. Візьмемо РФ f таку, що  f не є ПРМ. Наслідок 2. Існують РФ h такі, які не є ПРФ, але  h є ПРМ. f ( x ) =  nsg ( u ( x,  x )), де u ( t,  x ) – універс. РФ для ПРФ 1, не є ПРФ. За теоремою Кліні про НФ в посиленій формі існує ПРФ g така: f ( x ) =  l (  t ( g ( x,  t ) = 0)). h ( x )   =   t ( g ( x,  t ) = 0) за теоремою Сколема має  h ПРМ. h є ПРФ  f ( x ) =  l ( h ( x )) теж ПРФ – суперечність, тому h не є ПРФ.

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

Слайд 26

26 Теорема 4. Існують ЧРФ із нерекурсивним графіком. Такими є, зокрема,  ч L для нерекурсивних РПМ L.  ч L = {( x,   1) |  x  L } рекурсивна  за ТЧ рекурсивна – суперечність Наслідок. Існують ЧРФ f такі, які не можна подати у вигляді f ( x 1,...,  x n ) =  t ( g ( x 1,..., x n, t ) = 0) для деякої РФ g. Візьмемо функцію  ч L для нерекурсивної РПМ L. Тоді її графік нерекурсивний, і за теоремою Сколема таке подання неможливе. Зауваження. Теорема Сколема дає вичерпну відповідь на питання, наскільки необхідна зовнішня функція l у поданні ЧРФ f у НФ Кліні.

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

Слайд 27

27 Індексні множини Теореми Райса та Райса – Шапіро Введення ефективних нумерацій ЧРФ ставить питання, які саме властивості ЧРФ можна (частково) розпізнати за номерами функцій, тобто чи будуть множини номерів відповідних класів ЧРФ РМ (РПМ).    : N →  – ефективна нумерація . Для  визначимо множину номерів усіх об’єктів з  : N (  )   =    –1 (  ). Множини вигляду N (  ), де  ЧРФ n – індексні.

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

Слайд 28

28 Теорема 1 (Райс). Нехай  ЧРФ n та       . Тоді N (  ) нерекурсивна Вважаємо f  . Зафіксуємо довільну g . Задамо За s - m - n існує РФ s :  z, x 1,..., x n f ( z,   x 1,..., x n ) =  n s ( x ) ( x 1,...,   x n ). z  D   n s ( x ) ( x 1,...,   x n )   =   f ( z,   x 1,...,   x n )   =   g ( x 1,...,   x n )   n s ( x ) = g. Отже,  n s ( x )   s ( z )  N (  ). z  D   n s ( x ) ( x 1,...,   x n )   =   f ( z,   x 1,...,   x n )    n s ( x ) = f . Отже,  n s ( x )   s ( z )  N (  ). Маємо z  D  s ( z )  N (  ). Звідси  D ( z ) =   N (  ) ( s ( z ) ). N (  ) є РМ   N (  ) є РФ   N (  ) ( s ( z ) ) є РФ ( s є РФ)   D ( z ) є РФ. Це суперечить нерекурсивності D  N (  ) нерекурсивна. Наслідок. Нехай  РПМ та       . Тоді N (  ) не є РМ. Теорема Райса стверджує: жодна нетривіальна властивість у класах усіх n -арних ЧРФ та всіх РПМ не може бути ефективно розпізнана!

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

Слайд 29

29 Теорема 2 (дуальна). Нехай  ЧРФ n та f  . Тоді N (  ) не є РПМ. Зафіксуємо довільну g . Задамо функцію f : За s - m - n існує РФ s :  z, x 1,..., x n f ( z,   x 1,..., x n ) =  n s ( x ) ( x 1,...,   x n ). z  D   n s ( x ) ( x 1,...,   x n )   =   f ( z,   x 1,...,   x n )   =   g ( x 1,...,   x n )   n s ( x ) = g. Отже,  n s ( x )   s ( z )  N (  ). z  D   n s ( x ) ( x 1,...,   x n )   =   f ( z,   x 1,...,   x n )    n s ( x ) = f . Отже,  n s ( x )   s ( z )  N (  ). Маємо z  D  s ( z )  N (  ). Звідси  ч  D ( z ) =   ч N (  ) ( s ( z ) ) N (  ) є РПМ   ч N (  ) є ЧРФ   ч N (  ) ( s ( z ) ) є ЧРФ   ч  D ( z ) є ЧРФ. Але  D не є РПМ – суперечність. Отже, N (  ) не є РПМ.

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

Слайд 30

30 Наслідок. Множини { x | D x є РМ} та { x | D x скінченна } не є РПМ.  скінченна та РМ  f   {  x | D x скінченна} та f   {  x | D x є РМ} Теорема   3. Не існує ЧРФ f такої, що  x  N Якщо така ЧРФ f існує, то D x є РМ  f ( x )  Тоді D f   = { x  |  D x  є РМ}  D f не є РПМ – суперечність. Отже, в загальному випадку за індексом x РМ D x неможливо ефективно знайти індекс  D x, якщо вона РМ.

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

Слайд 31

31 Канонічна нумерація скінченних множин на N Нехай L = { x 1,..., x n }, де x 1 <...< x n. Канонічний номер ( канонічний індекс ) множини L – це число Число 0 – номер множини . F m – скінченна множина з канонічним індексом m. Канонічна нумерація скінченних множин на N n Канонічний номер (канонічний індекс) множини L  N n – це канонічний індекс множини C n ( L ). F n m – скінченна L  N n з канонічним індексом m. Можливий ефективний перехід від канонічного індексу скінченної множини до її стандартного індексу як РПМ, але зворотний ефективний перехід неможливий.

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

Слайд 32

32 Теорема 4. 1) Існує РФ g така :  x  N F x = D g ( x ) 2) Не існує ЧРФ f такої, що  x  N Доводимо 1). " y  F x " є РП рекурсивний, тому За s - m - n існує РФ g :  x,   y  N h ( x, y )   =    g ( x ) ( y )  F x = D g ( x ). Доводимо 2). Якщо така ЧРФ f існує, то D x скінченна  f ( x )  Звідси D f  =   { x  |  D x скінченна}, але D f не є РПМ  f не є ЧРФ.

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

Слайд 33

33 Сформулюємо критерій належності функції до конструктивної (РПМ) індексної множини. Виявляється, що для цього достатньо скінченної інформації про функцію. Теорема 5 (Райса – Шапіро). Нехай  ЧРФ n така, що N (  ) є РПМ. Тоді для довільної f  ЧРФ n маємо : f    скінченна  :  f та . Випадок f = f  тривіальний, тому розглядаємо випадок f      f . Зауважимо, що при f   N (  ) є РПМ    = ЧРФ n.

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

Слайд 34

34 Доводимо . Припустимо супротивне: f , але не існує скінченної  :  f та . Нехай P – МНР-програма така, що P ( z )   z  D. За ТЧ така g є ЧРФ. За s - m - n існує РФ s така:  z,  x 1,...,  x n g ( z, x 1,..., x n ) =  n s ( z ) ( x 1,..., x n ) z  D  P ( z )      t   : P ( z )  за t кроків   k  t P ( z )  за  k кроків   n s ( z ) ( x 1,...,   x n )   x 1,...,   x n таких : C n ( x 1,..., x n )  t   n s ( z ) скінч.  (  z  n s ( z )     f   ) за припущенням  n s ( z )   s ( z )  N (  ). z  D  P ( z )    x 1,...,   x n P ( z ) не зупиниться за  C n ( x 1,..., x n ) кроків   n s ( z ) – це f  за припущенням  n s ( z )   s ( z )  N (  ). Маємо z  D  s ( z )  N (  ). Звідси  ч  D ( z ) =   ч N (  ) ( s ( z ) ) N (  ) є РПМ   ч N (  ) є ЧРФ   ч N (  ) ( s ( z ) ) є ЧРФ   ч  D ( z ) є ЧРФ. Але  D не є РПМ – маємо суперечність.

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

Слайд 35

35 Доводимо . Припустимо супротивне: маємо ЧРФ f таку, що f  та існує скінченна  f : . За ТЧ h є ЧРФ. За s - m - n існує РФ s така:  z,  x 1,...,  x n h ( z, x 1,..., x n ) =  n s ( z ) ( x 1,..., x n ) z  D   n s ( z ) – це функція f  за припущенням  n s ( z )   s ( z )  N (  ). z  D  при ( x 1,..., x n )  D   n s ( z ) ( x 1,..., x n ) = f ( x 1,..., x n ) та при ( x 1,..., x n )  D   n s ( z ) ( x 1,..., x n )    n s ( z ) – це   за припущенням  n s ( z )   s ( z )  N (  ). Маємо z  D  s ( z )  N (  ). Знову суперечність.

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

Последний слайд презентации: 1 Примітивно-рекурсивні, рекурсивні, рекурсивно-перелічні множини Множина M  N

36 Приклад 1. Множина { x | D x       } – нерекурсивна РПМ. D x         y  k ( P x ( y )  за k кроків), " P x ( y )  за k кроків" є РП  " D x   " є ЧРП  { x   |   D x   } є РПМ  ( Rice ) { x | D x   } не є РМ. Приклад 2. Множина { x |  x є РФ} не є РПМ. { x |  x є РФ} є РПМ  ( Rice-Sh)  РФ  x  скінченна  така, що        x та  {  x |  x є РФ}. Але скінченні функції не можуть бути РФ. Приклад 3. Множина { x | D x нескінченна} не є РПМ. { x  |  D x нескінченна} є РПМ  ( Rice-Sh)  нескінченної  x  скінченна  така, що        x та  {  x  |  D x нескінченна}. Але тоді  нескінченна !

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