Презентация на тему: 1 ЗВІДНОСТІ Проблема  зводиться до проблеми  : з розв’язності  випливає

Реклама. Продолжение ниже
1 ЗВІДНОСТІ Проблема  зводиться до проблеми  : з розв’язності  випливає
1 ЗВІДНОСТІ Проблема  зводиться до проблеми  : з розв’язності  випливає
1 ЗВІДНОСТІ Проблема  зводиться до проблеми  : з розв’язності  випливає
1 ЗВІДНОСТІ Проблема  зводиться до проблеми  : з розв’язності  випливає
1 ЗВІДНОСТІ Проблема  зводиться до проблеми  : з розв’язності  випливає
1 ЗВІДНОСТІ Проблема  зводиться до проблеми  : з розв’язності  випливає
1 ЗВІДНОСТІ Проблема  зводиться до проблеми  : з розв’язності  випливає
1 ЗВІДНОСТІ Проблема  зводиться до проблеми  : з розв’язності  випливає
1 ЗВІДНОСТІ Проблема  зводиться до проблеми  : з розв’язності  випливає
1 ЗВІДНОСТІ Проблема  зводиться до проблеми  : з розв’язності  випливає
1 ЗВІДНОСТІ Проблема  зводиться до проблеми  : з розв’язності  випливає
1 ЗВІДНОСТІ Проблема  зводиться до проблеми  : з розв’язності  випливає
1 ЗВІДНОСТІ Проблема  зводиться до проблеми  : з розв’язності  випливає
1 ЗВІДНОСТІ Проблема  зводиться до проблеми  : з розв’язності  випливає
1 ЗВІДНОСТІ Проблема  зводиться до проблеми  : з розв’язності  випливає
1 ЗВІДНОСТІ Проблема  зводиться до проблеми  : з розв’язності  випливає
1 ЗВІДНОСТІ Проблема  зводиться до проблеми  : з розв’язності  випливає
1 ЗВІДНОСТІ Проблема  зводиться до проблеми  : з розв’язності  випливає
1 ЗВІДНОСТІ Проблема  зводиться до проблеми  : з розв’язності  випливає
1 ЗВІДНОСТІ Проблема  зводиться до проблеми  : з розв’язності  випливає
1 ЗВІДНОСТІ Проблема  зводиться до проблеми  : з розв’язності  випливає
1 ЗВІДНОСТІ Проблема  зводиться до проблеми  : з розв’язності  випливає
1 ЗВІДНОСТІ Проблема  зводиться до проблеми  : з розв’язності  випливає
1 ЗВІДНОСТІ Проблема  зводиться до проблеми  : з розв’язності  випливає
1 ЗВІДНОСТІ Проблема  зводиться до проблеми  : з розв’язності  випливає
1 ЗВІДНОСТІ Проблема  зводиться до проблеми  : з розв’язності  випливає
1 ЗВІДНОСТІ Проблема  зводиться до проблеми  : з розв’язності  випливає
1 ЗВІДНОСТІ Проблема  зводиться до проблеми  : з розв’язності  випливає
1 ЗВІДНОСТІ Проблема  зводиться до проблеми  : з розв’язності  випливає
1 ЗВІДНОСТІ Проблема  зводиться до проблеми  : з розв’язності  випливає
1 ЗВІДНОСТІ Проблема  зводиться до проблеми  : з розв’язності  випливає
1 ЗВІДНОСТІ Проблема  зводиться до проблеми  : з розв’язності  випливає
1 ЗВІДНОСТІ Проблема  зводиться до проблеми  : з розв’язності  випливає
1 ЗВІДНОСТІ Проблема  зводиться до проблеми  : з розв’язності  випливає
1 ЗВІДНОСТІ Проблема  зводиться до проблеми  : з розв’язності  випливає
1 ЗВІДНОСТІ Проблема  зводиться до проблеми  : з розв’язності  випливає
1 ЗВІДНОСТІ Проблема  зводиться до проблеми  : з розв’язності  випливає
1 ЗВІДНОСТІ Проблема  зводиться до проблеми  : з розв’язності  випливає
1 ЗВІДНОСТІ Проблема  зводиться до проблеми  : з розв’язності  випливає
1 ЗВІДНОСТІ Проблема  зводиться до проблеми  : з розв’язності  випливає
1 ЗВІДНОСТІ Проблема  зводиться до проблеми  : з розв’язності  випливає
1 ЗВІДНОСТІ Проблема  зводиться до проблеми  : з розв’язності  випливає
1 ЗВІДНОСТІ Проблема  зводиться до проблеми  : з розв’язності  випливає
1 ЗВІДНОСТІ Проблема  зводиться до проблеми  : з розв’язності  випливає
1 ЗВІДНОСТІ Проблема  зводиться до проблеми  : з розв’язності  випливає
1 ЗВІДНОСТІ Проблема  зводиться до проблеми  : з розв’язності  випливає
1 ЗВІДНОСТІ Проблема  зводиться до проблеми  : з розв’язності  випливає
1/47
Средняя оценка: 4.3/5 (всего оценок: 81)
Код скопирован в буфер обмена
Скачать (208 Кб)
Реклама. Продолжение ниже
1

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

1 ЗВІДНОСТІ Проблема  зводиться до проблеми  : з розв’язності  випливає розв’язність . Нерозв’язна  зводиться до    нерозв’язна. Метод нумерацій дозволяє масові проблеми подавати за допомогою числових множин, тому далі – звідність множин. Уточнення поняття звідності A до B відрізняються способом застосування та обсягом інформації про B, яку використовуємо для розв’язання питання про A. Сильні звідності : m- звідність та її окремий випадок – 1-звідність. Неформально m- звідність множини A до множини B : для розв'язання питання " x  A " треба поставити єдине питання до множини B, причому заздалегідь указаним ефективним способом, який можна уточнити як певну РФ g, тобто питання " g ( x )  B ".

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

Слайд 2

2 m -звідність, 1-звідність A   m   B, якщо існує РФ g :  x  N x  A  g ( x )  B. Записуємо також g   :   A   m   B. A   1  B, якщо існує ін’єктивна РФ g :  x  N x  A  g ( x )  B. Властивості m -звідності та 1-звідності r 1) Якщо A  1 B, то A  m B. r 2) Відношення  1 та  m рефлексивні й транзитивні. r 3) A  m  B   A    m   B ; те саме вірно для  1. r 4) Якщо A  m B та B є РМ, то A є РМ; те саме для  1. g : A  m B   A ( x ) =  B ( g ( x )) – РФ, адже  B та g є РФ. r 5) Якщо A  m B та B є РПМ, то A є РПМ; те саме для  1. РФ g : A  m B   ч A ( x ) =  ч B ( g ( x )) – ЧРФ, адже  ч B є ЧРФ. r 6) A – нерекурсивна РПМ  невірно A    m   A та невірно  A    m   A ; те саме для  1. Справді,  A не є РПМ (теорема Поста). За r 5) невірно  A    m   A ; за r 3) невірно  A    m   A. .

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

Слайд 3

3 r 7) A  m N  A = N ; те саме для  1. Нехай g   : A  m N, тоді x  A  g ( x )  N. Але g ( x )  N вірно завжди. r 8) A  m   A =  ; те саме для  1. r 9) N  m A  A  . Якщо РФ g :   N  m А, то A  Е g  . Якщо A  , то зафіксуємо a  A і задамо g ( x ) = a  x  N ; тоді g : N  m A. r 10)   m A  A  N. r 11) N  1 A  A містить нескінченну РПМ. Нехай g : N    1 A. Тоді x  N  g ( x )  A, звідки E g  A. Однак E g є нескінченною РПМ як область значень ін’єктивної РФ g. Якщо L – нескінченна РПМ та L  A, то L = E g для деякої ін’єктивної РФ g. Тоді g ( x )  A для всіх x  N, звідки g   : N  1 A.

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

Слайд 4

4 r 12) Якщо A рекурсивна і B   та B  N, то A  m B. Виберемо b  B, a  B. РФ g ( x ) = b   A ( x )+ a  nsg (  A ( x )) m -зводить A до B. r 13) Для довільної B маємо A  m A  B та A  m B  A. 2 x : A  m A  B та 2 x +1 : A  m B  A. r 14) Для довільної B  маємо A  m A  B та A  m B  A. Візьмемо довільний b  B. Тоді C ( x,  b ) : A  m A  B та C ( b,  x ) : A  m B  A. r 15 ) Якщо A є РПМ, то A  m D.

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

Слайд 5

5 m -еквівалентність A  m B  A  m B та B  m A. B ведемо класи еквівалентності відносно  m – m-степені. d m ( A ) = { B | A  m B }. Пишемо A < m B, якщо A  m B та невірно B  m A. Пишемо A | m B, якщо невірно A  m B та невірно B  m A. Відношення  m індукує на множині m -степенів відношення  m : a  m b, якщо A  m B для деяких A  a, B  b. a  m b  A  m B для всіх A  a, B  b.  m – відношення часткового порядку на множині m -степенів – рефлексивність і транзитивність маємо за r 1) – антисиметричність: a    m   b та b    m   a  A    m B та B    m A для деяких A  a та B  b  A  m B для деяких A  a та B  b  a = b.

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

Слайд 6

6 Пишемо a < m   b, якщо a  m b та a  b. Пишемо a   | m b, якщо невірно a  m b та невірно b  m a. Аналогічно – відношення  1, 1-степені, відношення  1 Кожний m -степінь складається із 1-степенів. m -степінь рекурсивний, якщо він містить РМ. m -степінь рекурсивно-перелічний, якщо він містить РПМ. Аналогічно – рекурсивні та РП 1-степені. – кожний РП m -степінь складається тільки з РПМ – кожний рекурсивний m -степінь складається тільки з РМ. Те саме вірно для 1-степенів. Існують 2 специфічні сингулярні m -степені з єдиної множини: 0 = d m (  ) = {  } та n = d m ( N ) = { N }. Усі інші РМ утворюють рекурсивний m -степінь  0 т. Визначимо РП m -степінь 0' m = d m ( D ).

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

Слайд 7

7 Властивості m -степенів Згідно r 4), r 5), r 7), r 8), r 12), r 15) маємо d 1) 0 m    m a для всіх m -степенів a  0,  n. d 2) n  m a для всіх m -степенів a  0. d 3) 0  m a для всіх m -степенів a  n. d 4) Якщо a  m b і m -степінь b – РП, то a – РП m -степінь. d 5) Існує найбільший РП m -степінь 0' m   : b   m 0 ' m  РП m -степеня b. Точна верхня грань (супремум) m -степенів a та b – m -степінь a  b : – a  m a  b та b  m a  b ; – a  b  m d  m -степеня d такого, що a  m d та b  m d.

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

Слайд 8

8 Теорема (про супремум). Для кожної пари m-степенів a та b існує єдина точна верхня грань. Покладемо a  b = d m ( A  B ), де A  a, B  b. Тоді 2 x : A  m A  B та 2 x +1 : B  m A  B. Отже, a  m a  b, b  m a  b. Якщо a та b – РП m -степені, то a  b – РП m -степінь Нехай d – довільний m -степінь такий, що a  m d та b  m d. Нехай M  d, f та g – такі РФ, що f : A  m M та g : B  m M. m -зводить A  B до M. Тому a  b = d m ( A  B )  m d. Звідси a  b – точна верхня грань m -степенів a та b.

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

Слайд 9

9 Продуктивні та креативні множини Нехай A – не РПМ. Тоді не існує такого n, що A = D n. Тому для кожної D x    A існує y  A \   D x (множина таких y нескінченна). Якщо таке y ефективно обчислюється за x, то A – продуктивна. A продуктивна, якщо існує РФ g така, що D x      A  g ( x )  A \   D x. Така g – продуктивна функція множини A. Множина креативна, якщо вона є РПМ і має продуктивне доповнення. Приклад 1. Множина  D продуктивна з продуктивною функцією g ( x ) = x. Нехай D x     D. Якщо x  D x, то  x ( x ) , тому x  D, що суперечить D x     D. Отже, x  D x, тому x  D. Звідси x  D \ D x. Приклад 2. Множина D креативна, тому що D є РПМ і  D продуктивна.

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

Слайд 10

10 Теорема 1. Нехай A – продуктивна та A   m  B. Тоді множина B продуктивна. Нехай РФ f :  A  m  B, g – продуктивна функція для A. Візьмемо довільну D x  B. Маємо x  A  f ( x )  B, тому f – 1 ( D x ) = { y  |  f ( y )  D x }     A.  x ( f ( y )) є ЧРФ, тому за s - m - n існує РФ k така:  x  y маємо  x ( f ( y )) =  k ( x ) ( y ). Звідси y  f – 1 ( D x )  f ( y )  D x  y  D k ( x ), тому f – 1 ( D x ) =  D k ( x ). Однак f – 1 ( D x )  A і g продуктивна для A, тому g ( k ( x ))  A \ f – 1 ( D x ) = A \ D k ( x ). Звідси f ( g ( k ( x )))  B \ D x. Отже, B продуктивна з продуктивною f ( g ( k ( x ))). Наслідок. Нехай A креативна, B – РПМ та A   m   B. Тоді B креативна. Якщо A    m B, то  A    m   B за r 3); але A креативна, тому  A продуктивна, звідки  B продуктивна, тому РПМ B креативна.

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

Слайд 11

11 Приклад 3. Для кожного a  N множина C a  =   { x   |    x ( x )   =   a } креативна. За s - m - n існує РФ s така: f ( z,  x ) =  s ( z ) ( x ) для всіх z, x. Звідси z  D   s ( z ) ( s ( z ))  = а  s ( z )  C a, тому РФ s : D  m C a. Однак " x  C a " є ЧРП: x  C a  P x ( x )  a. Отже, C a є РПМ, за наслідком теореми 1 множина C a креативна.

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

Слайд 12

12 Достатні умови продуктивності для індексних множин Такі умови базуються на теоремі Райса – Шапіро. Теорема 2. Для продуктивності N (  ) достатньою є одна з умов: Пр1)  ЧРФ n та f   ; Пр2) існує f  ЧРФ n така, що   для кожної скінченної   f ; Пр3) існують f  ЧРФ n та g  ЧРФ n такі, що g  та f  g. Для доведення Пр1 та Пр2 повторимо доведення теореми Райса дуальної та теореми Райса–Шапіро. Для побудованих там РФ s маємо z  D  s ( z )  N (  ). Для доведення Пр3 задамо Повторимо доведення теореми Райса–Шапіро та знайдемо РФ s таку: z  D  s ( z )  N (  )

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

Слайд 13

13 Пр1 випливає з Пр3. Візьмемо f   =   f , тоді f  g для довільної g . За Пр3 N (  ) продуктивна. Приклад 4. Множина A = { x |  х є заданою ЧРФ g } продуктивна. Якщо g – нескінченна функція, то А продуктивна за Пр2. Якщо g – скінченна, то А продуктивна за Пр3. Приклад 5. A  = { x |  х не є заданою ЧРФ g } продуктивна при g  f  та креативна при g = f . Якщо g  f , то f   {  х |  х не є заданою ЧРФ g }, тому множина А продуктивна за Пр1. Якщо g = f , то A = { x |  х  f  } = { x | D х   } є РПМ, тому вона креативна.

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

Слайд 14

14 Теорема   3. 1) Нехай  ЧРФ n. Тоді N (  ) рекурсивна   =  або  = ЧРФ n. 2) Нехай  ЧРФ n та . Тоді N (  ) є РПМ  N (  ) креативна. Твердження 1) випливає з теореми Райса. Неможливо f  , так як тоді N (  ) продуктивна за Пр1, тому не є РПМ. Отже, f  , звідси N (  ’) =  N   \   N (  ) за Пр1 продуктивна, і якщо N (  ) є РПМ, то вона креативна. Теорема 4. Клас продуктивних множин незамкнений відносно , , . A = { x |  x не є РФ} продуктивна за Пр1: f   {  x |  x не є РФ}. B   ={ x |  x є РФ} продуктивна за Пр2, тому що для кожної РФ g кожна скінченна       g не є РФ. Звідси: A  B = N та A  B =  – не продуктивні. Якщо L креативна, то M =  L продуктивна, але РПМ L =  M не продуктивна.

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

Слайд 15

15 Теорема 5. 1) Якщо A продуктивна, то A  B та B  A продуктивні. 2) Якщо A креативна та B є РПМ, то A  B та B  A креативні. 3) Якщо A продуктивна та B      , то A  B та B  A продуктивні. 4) Якщо A креативна, B       та В є РПМ, то A  B та B  A креативні. Якщо A креативна та B є РПМ, то A  B, B  A, A  B та B  A є РПМ Твердження теореми випливає з теореми 1, її наслідку, r 13, r 14. Теорема 6. Клас креативних множин незамкнений відносно , , . Якщо A креативна, то A  N та N  A креативні за теоремою 5. Однак ( A  N )  ( N  A ) = N не креативна, тому що рекурсивна. За прикладом 3 C 0 = { x |  x ( x ) = 0} та C 1 = { x |  x ( x ) = 1} креативні. Однак C 0  C 1 =  – рекурсивна, тому не креативна. Якщо A креативна, то  A продуктивна, тому не креативна

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

Слайд 16

16 Теорема 7. Кожна продуктивна множина містить нескінченну РПМ. Нехай A – продуктивна множина з продуктивною функцією g. За s - m - n виначимо РФ k таку: D k ( x ) = D x  { g ( x )} для кожного x. Побудуємо послідовності x 0, x 1,..., x n,... та y 0, y 1,..., y n,... Нехай x 0 – один з індексів функції f . Тоді y 0 = g ( x 0 ). Але D x 0  =       A, тому за продуктивністю A y 0 = g ( x 0 )  A \ D x 0  = A. Після n -го кроку : D x n   = { y 0, y 1,..., y n –1 }  A, де всі y k попарно різні. На ( n +1)-му кроці : х n +1  =  k ( x n ), y n +1  =  g ( x n +1 ). Маємо D x n +1  =   D k ( x n )  =   D x n  { g ( x n ) } =  D x n  { y n } = { y 0, y 1,..., y n }. За продуктивністю A тоді y n +1 = g ( x n +1 )  A \ D x n +1  =   A \{ y 0, y 1,..., y n }. Таким чином, y n +1  A та y n +1  { y 0, y 1,..., y n }. Отже, B = { y 0, y 1,..., y n } нескінченна та B  A. Множина B алгоритмічно перелічна, тому за ТЧ B є РПМ.

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

Слайд 17

17 Імунні та прості множини Нескінченна множина імунна, якщо вона не містить нескінченних РПМ. Іімунна не може бути РПМ. За теоремою 7 імунна не може бути продуктивною. Множина проста, якщо вона є РПМ і має імунне доповнення. A проста  A є РПМ,  A нескінченна та A  R    нескінченної РПМ R. Проста множина не може бути ні рекурсивною, ні креативною.

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

Слайд 18

18 Теорема 1. Існує ЧРФ f така, що  Е f імунна та Е f проста. Побудуємо ЧРФ f таку, що Е f містить хоч би по одному елементу кожної нескінченної РПМ та  Е f нескінченна. Жодна нескінченна РПМ повністю в таку Е f не вміщається, тому  Е f імунна, а E f – проста. Визначимо f ( x ) =  x (  z (  x ( z )>4 x )). Тоді f ( x )> 4 x для всіх x  D f. Для довільного n  N множина {0,..., 4 n } містить  n елементів E f, так як f ( n )>4 n і елементи E f можуть братися тільки з f (0),..., f ( n –1). Тому  n  N {0, ..., 4 n } містить > 3 n елементів множини  Е f. Отже,  Е f нескінченна. Нехай B – довільна нескінченна РПМ. Тоді B = E g для деякої РФ g. Нехай k – індекс функції g, тобто g суть  k. Значення f ( x ) =  x (  z (  x ( z )>4 x )) визначене, тому що  k є РФ із нескінченною множиною значень. Отже, f ( k )  E k  E f = E g  E f = B  E f, тому B  E f    неможливо B  E f

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

Слайд 19

19 Теорема 2. Множина A проста   A нескінченна та A  R є нескінченною РПМ для кожної нескінченної РПМ R. Доводимо . Припустимо супротивне: існує така нескінченна РПМ  R, що A  R скінченна. Тоді R \( A  R ) = R \   A теж нескінченна РПМ, але A  ( R \   A ) = . Це суперечить простоті множини A. Доводимо . N є нескінченною РПМ, тому за умовою множина A  N  =  A є нескінченною РПМ. Якщо для кожної нескінченної РПМ  R множина A    R нескінченна, то A  R . Отже, A проста. Теорема 3. Якщо множини A та B прості, то A  B проста. Нехай R – нескінченна РПМ. Якщо A проста, то за теоремою 2 A  R є нескінченною РПМ. Звідси ( A  B )  R = B  ( A  R )   за простотою B.  A та  B нескінченні, звідки N \( A  B )       A нескінченна. Тому A  B проста.

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

Слайд 20

20 Теорема 4. Існують прості множини A та B такі: A  B = N. Задамо f ( x ) =   x (  z (  x ( z )   >   4 x )). За доведенням теореми 1 Е f проста. Розглянемо A  =  E f  N 2 x та B  =  E f  N 2 x +1. Зрозуміло, що A  B = N. Покажемо, що A та B прості.  n  N множина {0,  ..., 4 n } містить  n елементів E f. Крім того, {0,..., 4 n } містить 2 n +1 парних і 2 n непарних чисел. Отже, {0,..., 4 n } містить  3 n +1 елементів A та  3 n елементів B. Тому для  n  N множина {0,  ...,   4 n } містить  n елементів  A та > n  елементів   B, звідки  A та  B нескінченні. Нехай R – довільна нескінченна РПМ. Тоді R   =   E k, де k – індекс деякої РФ  k. Значення f ( x ) =  x (  z (  x ( z )>4 x )) визначене, тому що  k є РФ та E k нескінченна. Отже, f ( k )  E k  E f = R  E f, тому R  E f  . Звідси R  ( E f  N 2 x ) = R  A   та R  ( E f  N 2 x +1 ) = R  B  . Таким чином, A та B – прості множини, для яких A  B = N. Наслідок. Клас простих множин незамкнений відносно  та доповнення.

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

Слайд 21

21 Теорема 5. Якщо множини A та B прості, то A  B проста. Теорема 6. Якщо A проста, то A  B та B  A не є простими. Візьмемо довільний d   A. Тоді L = { d }  N та M = N  { d } – нескінченні РПМ. Однак L  ( A  B ) =  та M  ( B  A ) = , тому A  B та B  A не прості. Наслідок. Якщо множини A та B прості, то A  B не проста.

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

Слайд 22

22 Посилення властивостей імунності й простоти веде до понять гіперімунної та гіперпростої множин. Нехай A = { z 0 < z 1 <... < z n <...}. Функція f мажорує A, якщо f ( n )> z n для всіх n. Множина A гіперімунна, якщо A нескінченна та не існує РФ, яка мажорує A. Множина A гіперпроста, якщо A є РПМ та  A гіперімунна. Теорема 7. Гіперімунні множини існують. Нехай f 0, f 1,..., f n,... – деяка послідовність тотальних функцій на N, яка включає всі РФ 1. Задамо функцію g : g (0) = f 0 (0); g ( n +1) =  z ( z > g ( n ) та z > f n +1 ( n +1)). Звідси Е g не мажорується жодною РФ, тому Е g гіперімунна.

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

Слайд 23

23 Теорема 8. Якщо A гіперімунна, то A імунна. Нехай нескінченна множина A не імунна. Тоді A не гіперімунна. Якщо A не імунна, то A  нескінченну РПМ, звідки існує нескінченна РМ R  A. Нехай f – строго монотонна РФ така, що R  =  E f. Тоді R = { f (0)< f (1)<...< f ( n )<...}. Нехай A = { z 0 < z 1 <...< z n <...}. Тоді R = { z i 0 <   z i 1 <...<   z i n <...} згідно з R  A.  n  N маємо z i n    z n та f ( n )   =   z i n. Задамо РФ g ( x ) = f ( x )+1. Тоді  n  N g ( n )   = f ( n )+1 = z i n +1   >   z i n      z n. Отже, РФ g мажорує A, тому A не гіперімунна. Наслідок. Якщо A гіперпроста, то A проста.

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

Слайд 24

24 Рекурсивна та ефективна нероздільність. m- повнота Множини A і B ефективно нероздільні якщо A  B  =   та існує РФ f ( x,   y ) така: D a  A, D b  B та D a  D b =   f ( а, b )  D a  D b Така f – продуктивна функція пари нероздільних множин A та B. Множини A і B рекурсивно нероздільні, якщо A  B  =   і не існує РМ R такої, що R  A та R  B = . Теорема 1. Якщо A і B ефективно нероздільні, то A і B рекурсивно-нероздільні. Нехай A і B – ефективно нероздільні з продуктивною функцією f. Припустимо, що A і B не є рекурсивно-нероздільними, тобто існує РМ R : R  A та R  B = . Нехай R = D a та  R = D b. Тоді R  =  D a  A,  R  = D b  B, D a  D b = R  R = . Однак D a  D b =  R  R = N, що суперечить ефективній нероздільності A і B.

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

Слайд 25

25 Теорема 2. C 0 = { x |  x ( x )=0} та C 1 = { x |  x ( x )=1} – ефективно нероздільні РПМ. Задамо функцію h, яка за тезою Чорча є ЧРФ. За s - m - n існує РФ u така: h ( x, y, z ) =  u ( x, y ) ( z )  x, y, z. Покажемо, що u – продуктивна функція для пари нероздільних C 0 та C 1. Нехай a і b такі, що D a  C 0, D b  C 1 та D a  D b = . u ( a, b )  D a   u ( a, b ) ( u ( a, b )) = h ( a, b, u ( a, b )) = 1  u ( a,  b )  C 1  D b – суп-ть. u ( a, b )  D b   u ( a, b ) ( u ( a, b )) = h ( a, b, u ( a, b )) = 0  u ( a,  b )  C 0  D a – суп-ть. Отже, u ( a, b )  D a  D b  u – продуктивна для пари ефективно нероздільних C 0 і C 1

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

Слайд 26

26 Теорема 3. Нехай A і B – ефективно нероздільні РПМ. Тоді A і B креативні. Нехай A = D a та B = D b. Нехай f – продуктивна функція для пари множин A та B. Візьмемо РФ u : D u ( x, y ) = D x  D y для всіх x, y. Візьмемо довільну D х       A. Тоді D x  B = D x  D b   =   D u ( x, b ). Маємо D u ( x, b )  B, D a = A. Звідси f ( а, u ( x, b ))  D a  D u ( x, b ) = A  B  D x. Тому f ( а, u ( x, b ))  A \ D x. Отже, g ( x ) =  f ( а,  u ( x,  b )) є продуктивною функцією для  A, звідки A креативна. Аналогічно p ( x ) = f ( u ( x, а )), b ) – продуктивна для  B, звідки B креативна.

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

Слайд 27

27 РПМ L m - повна, якщо A  m L для кожної РПМ A. РПМ L 1 -повна, якщо A  1 L для кожної РПМ A. Теорема 4. A є РПМ  A  m D. D є РПМ, тому A  m D  A є РПМ. Якщо A є РПМ, то f ( x,   y )   =   ч А ( x )   +   0  y є ЧРФ. За s - m - n існує РФ s ( x ): f ( x, y ) =  s ( x ) ( y )  x, y. Маємо x  A   s ( x ) ( y ) = 1  y   s ( x ) ( s ( x ))   s ( x )  D. Тому s  :  A  m D Наслідок 1. Множина D m-повна. Наслідок 2. Множина L m-повна  L  m D. Наслідок 3. m - степінь 0' m складається з m-повних множин. Наслідок 4. Кожна m-повна множина креативна. РПМ L m -повна  D  m L  ( D креативна) L креативна.

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

Слайд 28

28 Теорема (Майхілла). Якщо L креативна, то L m-повна. Нехай B – довільна РПМ, p – продуктивна функція  L. Покажемо B  m L. За s - m - n  РФ s ( x, y ): f ( x, y, z )   s ( x, y ) ( z )  За теоремою Cl FP для s ( x,   y ) існує РФ n ( y ) :  y  s ( n ( y ), y )   =    n ( y ) Звідси  y D s ( n ( y ), y ) = D n ( y )  Покажемо y  B  p ( n ( y ))  L. Це означає p ( n ( y )) : B  m L. Нехай y  B, тоді D n ( y ) ={ p ( n ( y ))}. Нехай p ( n ( y ))  L  { p ( n ( y ))} = D n ( y )   L  (  L  продуктивна) p ( n ( y ))  L \ D n ( y ) – суп-ть. Тому p ( n ( y ))  L. Нехай y  B  D n ( y )  =     (  L  продуктивна) p ( n ( y ))  L \    =    L  p ( n ( y ))  L Наслідок 1. L креативна  L m-повна. Наслідок 2. b – m-степінь простої множини  0 m < m b < m 0' m.

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

Слайд 29

29 ВІДНОСНА ОБЧИСЛЮВАНІСТЬ. Т -ЗВІДНІСТЬ Розглядаємо обчислюваність n -арних функцій на N відносно тотальних функцій. Неформально: f обчислювана відносно тотальної функції  (оракула), якщо існує алгоритм для обчислення f, який може брати потрібні значення функції . Формалізація відносної обчислюваності. Релятивізація теорем МНРО додатково використовують команди O ( n ) – звернення до оракула Виконання команди O ( n ) означає: ' R n   :=  (' R n ). Смисл МНРО-програми залежить від конкретного оракула. МНРО-програму P, яка виконується МНРО з оракулом , позначаємо P . МНРО-програма P обчислює f  :  N n  N відносно оракула , або  - обчислює f, якщо f ( a 1, a 2,..., a n ) = b  P  ( a 1, a 2,..., a n )  b. Функція f МНРО-обчислювана відносно , або  - обчислювана, якщо існує МНРО-програма P, яка обчислює f відносно .

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

Слайд 30

30 Функція частково рекурсивна відносно , або  - ЧРФ, якщо вона отримується з о, s, І m n та  за допомогою операцій S n +1, R, M.  -РФ – це тотальна  -ЧРФ Теорема 1. f є  - ЧРФ  f МНРО-обчислювана відносно . Клас усіх  -ЧРФ позначимо ЧРФ . Елементарні властивості  -ЧРФ: о1)  ЧРФ . о2) Для довільного оракула  маємо ЧРФ  ЧРФ . о3) Якщо тотальна функція  є  -ЧРФ, то ЧРФ   ЧРФ . о4) Якщо  рекурсивна, то ЧРФ  = ЧРФ. Релятивний аналог тези Чорча: Теза Тьюрінга. Клас  -ЧРФ збігається з класом n -арних функцій на N, алгоритмічно обчислюваних відносно .

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

Слайд 31

31 Ефективна нумерація n -арних  -ЧРФ – на основі кодування МНРО-програм. Кодування команд МНРО:  ( Z ( n )) = 5  n ;  ( S ( n )) = 5  n +1;  ( T ( m, n )) = 5  С ( m, n )+2;  ( J ( m, n, q +1)) = 5  С ( С ( m, n ), q )+3;  ( O ( n )) = 5  n +4. Позначення :  m , n D m , n E m , n Якщо n =1, то позначення  m  D m  E m  L назвемо  -РМ, якщо  L є  -РФ. L назвемо  -РПМ, якщо L  =   або L  =  E f для деякої  -РФ f. Предикат P назвемо  -РП, якщо  P є  -РФ. Предикат P назвемо  -ЧРП, якщо  ч Р є  -ЧРФ.

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

Слайд 32

32 Релятивні варіанти теорем R 1) Релятивна s - m - n -теорема.  m,   n >1  РФ m +1 s m n ( z,   x 1,...,   x m ) :  z, x 1,..., x m, y 1,..., y n Релятивна s - m - n (спрощена ).   -ЧРФ f ( x,   y )  РФ s ( x ) :  x,   y f ( x, y ) =  s ( x )  ( y ). R 2 ) Функція, універсальна для класу n -арних  -РФ, не є  -ЧРФ. R 3 ) Існує  -ЧРФ, універсальна для класу n -арних  -ЧРФ. R 4 ) Релятивна теорема Кліні про НТ. R 5 ) Релятивна теорема Поста. Якщо L та  L є  -РПМ, то L та  L є  -РМ. R 6 ) Такі визначення  -РПМ еквівалентні: df 1) L =  або L є областю значень деякої  -РФ; df 2) L є областю значень деякої  -ЧРФ; df 3) L є областю визначення деякої  -ЧРФ; df 4) часткова характеристична функція множини L є  -ЧРФ.

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

Слайд 33

33 R 7 ) Q ( x 1,..., x n ) є  -ЧРП тоді й тільки тоді, коли існує  -РП R ( x 1,..., x n, y ) : Q ( x 1,..., x n )   yR ( x 1,..., x n, y ). R 8 ) Якщо Q ( x 1,...,  x n,  y ) є  -ЧРП, то  y 1...  y k Q ( x 1,..., x n, y 1,..., y k ) теж є  -ЧРП. R 9 ) D  = { x |  х  ( x ) визначене} є  -РПМ і не є  -РМ. R 1 0 )  D  = { x |  х  ( x ) невизначене} не є  -РПМ. Обчислюваність відносно множини B – це обчислюваність відносно  B. Функцію називають B -РФ / B -ЧРФ, якщо вона  B -РФ /  B -ЧРФ. Множину A називають B -рекурсивною, якщо  A є  B -РФ. Множину A називають B-РПМ, якщо  ч A є  B -ЧРФ. Предикат P називають B -рекурсивним, якщо  P є  B -РФ. Предикат P називають B -ЧРП, якщо  ч P є  B -ЧРФ. Позначення :  m B, n D m B,, n E m B, n  m B D m B E m B ЧРФ B РФ B

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

Слайд 34

34 Теорема 3. 1) Множина A є  A-РМ. 2) Якщо A є B-РМ і B є C-РМ, то A є C-РМ. 3) Якщо A є B-РПМ і B є C-РМ, то A є C-РПМ. 4) Якщо A є B-РМ і B є C-РПМ, то не завжди A є C-РПМ. Доводимо 1). Маємо   A ( x ) = nsg (  A ( x )), тому  A є A -РМ. Доводимо 2). B є C -РМ   B є  C -РФ  ЧРФ B  ЧРФ C. Але A є B -РМ, тобто  A  ЧРФ B, звідки  A  ЧРФ C. Доводимо 3). B є C -РМ  ЧРФ B  ЧРФ C. Але A є B -РПМ   ч A  ЧРФ B  ЧРФ C. Доводимо 4). Візьмемо A =  D C і B = D C. Тоді  D C є D C -РМ згідно 1) та D C є C -РПМ, але  D C не є C -РПМ.

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

Слайд 35

35 T -звідність Патологічні властивості m -звідності: – специфічна поведінка  та N, – не завжди A  m  A. Така неприємна ситуація – внаслідок обмеженості природи m -звідності: g  :  A  m B, якщо для розв'язання питання " x  A " треба задати єдине питання до B, причому заздалегідь указаним способом " g ( x )  B ". Загальніші: таблична та обмежено-таблична звідності  tt та  btt, q -звідність  q Найадекватніше інтуїтивне поняття звідності – Тьюрінгова звідність Неформально A  T  B, якщо для розв'язання " x  A " необхідно відповісти на скінченну кількість питань про B, але їх кількість і природа заздалегідь невідомі. A T-зводиться до B, якщо A є B -рекурсивною. A  T B, якщо A  T B та B  T A. A < T B : A  T B та невірно B  T A. A  | T B : невірно A  T B та невірно B  T A.

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

Слайд 36

36 Властивості T -звідності t1) A  T A. t2) Якщо A  T B та B  T C, то A  T C. Випливає з п. 2 теореми 3. t3) Для кожної A маємо A  T   A та  A  T A. Випл. з п. 1 теор. 3. t4) A  T  A для кожної множини A. Випливає з t3). t5) Якщо A  m B, то A  T B. Нехай РФ g : A  m B. Тоді  A ( x ) =  В ( g ( x )), звідки  A є  B -РФ. t6) Якщо B є РМ і A  T B, то A є РМ.  B є РФ, тому ЧРФ B = ЧРФ та РФ B = РФ. Якщо A  T B, то  A  РФ B = РФ. t7) Якщо A є РМ, то A  T B для кожної множини B.  A  РФ  ЧРФ  ЧРФ B, звідки A є B -рекурсивною. t8) Якщо A є РПМ, то A  T D. За r15) A  m D для кожної РПМ A, звідки за t5) A  T D.

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

Слайд 37

37 Теорема 1. B є A-РПМ  B  m D A. B є A -РПМ   ч B є A -ЧРФ  f ( x,   y ) =  ч B ( x )+ o ( y ) є A- ЧРФ. За релятивною s-m-n -теоремою існує РФ s така: f ( x,   y ) =   А s ( x ) ( у ) для всіх x,   y. При x  B маємо  А s ( x ) ( у ) = 1 для всіх y, звідки  А s ( x ) ( s ( x )) , тому s ( x )  D A. При x  B маємо  А s ( x ) ( у )  для всіх y, тому  А s ( x ) ( s ( x )) , звідки s ( x )  D A. Отже, x  B  s ( x )  D A, тому B  m D A. Нехай РФ f   :  B  m D A. Тоді x  B  s ( x )  D A. Але D A є A -РПМ, f є РФ  " x  B " є A -ЧРП  B є A -РПМ. Наслідок 1. Якщо B є A-РПМ, то B  T D A. Наслідок 2. A < T D А для кожної множини A. A є A -РПМ  A  T D A. За R10 D A не є A -РМ, тому невірно D A  T A.

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

Слайд 38

38 Приклад 1. Існують множини А та В такі: А < T А  В та В  т А  В. Наприклад, візьмемо А = N та B = D. Приклад 2. А  В  T А  В. х  А  В  l ( х )  А & r ( х )  В  2 l ( х )  А  В & 2 r ( х )+1  А  В. Отже,  А  В ( х ) =  А  В (2 l ( х ))  А  В (2 r ( х )+1). Тому  А  В є  А  В -РФ. Приклад 3. D  T  D  T D  D  T D  D За t4 D    T   D. За r 13 та r 14 D  m  D    D та D  m D  D, тому D  T   D  D та D  T D  D. Згідно з t2 достатньо D  D  T D та D  D  T D. х  D  D  ( х парне & х/ 2  D )  ( х непарне & ( х –1) / 2  D )  " х  D  D " є D -РП   D  D є  D -РФ. х  D  D  l ( х )  D & r ( х )  D  " х  D  D " є D -РП   D  D є  D -РФ.

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

Слайд 39

39 Вводимо класи еквівалентності відносно  T d T ( A ) = { B | A  T B } Такі класи назвемо T-степенями, або степенями нерозв'язності. T -степінь рекурсивний, якщо він містить РМ. T -степінь рекурсивно-перелічний, якщо він містить РПМ. На множині T -степенів введемо відношення  часткового порядку: a  b, якщо A  T B для деяких A  a, B  b. Зрозуміло, що a  b  A  T B для всіх A  a, B  b. Будемо писати a < b, якщо a  b та a  b. a | b, якщо невірно a < b та невірно b  a.

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

Слайд 40

40 Властивості T -степенів s1 ) Існує єдиний рекурсивний T -степінь 0, який складається з усіх РМ. 0 є найменшим T -степенем: 0 < b для кожного T -степеня b  0. s2 ) Існує найбільший рекурсивно-перелічний T -степінь 0 ' =  d T ( D ): b  0 ' для кожного рекурсивно-перелічного T- степеня b. s3 ) Кожний нерекурсивний РП Т -степінь містить множини, які не є РПМ. s4 ) Якщо d m ( A )  m d m ( В ), то d Т ( A )  Т d Т ( В ). s5 ) d m ( A )  d Т ( A ) для довільної множини A. Теорема 2.  пари T-степенів a та b існує єдина точна верхня грань a  b = d T ( A  B ), де A  a, B  b. A  m   A  B та B  m   A  B  A  T   A  B та B  T   A  B  a     a  b та b  a  b. Нехай d – довільний T -степінь такий, що a  d та b  d.  A  a, B  b та L  d маємо, що A та B є L -РМ. Однак x  A  B  x парне та x /2  A або x непарне та ( x– 1)/2  B, тому функція  A  B є L -РФ. Звідси a  b  d.

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

Слайд 41

41 Т -повні множини A -РПМ B T - повнa, якщо L  T B для кожної A -РПМ L. D А   =   { x |  x А ( x )  } – T -повна A -РПМ для кожної A  N. Зокрема, D є T -повною РПМ. Це випливає з теореми 1: В є A -РПМ  B  m D A. Звідси: якщо B є A -РПМ, то B  T D A. Існують T -повні прості й навіть гіперпрості множини. Теорема (Деккер). Нехай A – нерекурсивна РПМ. Тоді існує гіперпроста множина B така, що A    Т  B. Нехай f – ін’єктивна РФ така: A = E f Задамо B = { x |  y ( y > x & f ( у )    f ( x ))}. Тоді B є РПМ за ТЧ.  B = { x |  y ( y > x  f ( y )> f ( x ))} – гіперімунна та A    Т  B. Наслідок. Кожний нерекурсивний РП T-степінь містить гіперпросту множину.

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

Слайд 42

42 У 1944 р. Е. Пост поставив проблему: чи існує РП T -степінь b : 0   <   b   <   0 '? Теорема (Мучника–Фрідберга, 1956). Існують РПМ A та B : A | T B. Наслідок. Існують РП T-степені a та b : 0   <   a   < 0', 0 < b < 0' та a | b. Структура T -степенів, зокрема, РП T -степенів, дуже складна. Деякі результати Теорема.  РП T-степеня a такого: 0   <   a   <   0'  РП T-степінь b : a | b. Теорема (щільності Сакса).  пари РП T-степенів a та b таких, що a   <    b, існує РП T-степінь c такий, що a   <   c   <   b. T -степінь m мінімальний, якщо 0 < m та не існує T -степеня a : 0 < a < m. Теорема. Існує мінімальний степінь m такий, що m < 0 '. За теоремою щільності, такий мінімальний T -степінь не може бути РП! Теорема (про розбиття).  РП T-степеня c  РП T-степені a   <   c, b   <   c : c = a  b. Теорема Існують РП T-степені a   >   0 та b   >   0 такі, що 0 = inf( a, b ); 2) Існують РП T-степені a та b такі, які взагалі не мають найбільшої нижньої грані ( навіть серед T-степенів, які не є РП ).

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

Слайд 43

43 Операція стрибка За наслідком 2 теореми 1 A < T D А для кожної множини A. Неформально A < T  D A означає, що при переході від A до D A складність множини стрибкоподібно зростає, тому D A називають стрибком множини A. Операція стрибка кожній A  N зіставляє множину D A. Теорема. A  T B  D A  m D B. Нехай A    T   B. Тоді A є B -РМ. Але D A є A -РПМ, тому D A є B -РПМ  D A  m D B. Нехай D A  m D B. Позаяк A та  A є A -РПМ, то A  m D A та  A  m D A. Але D A  m D B, тому A  m D B та  A  m D B  (теорема 1) A та  A є B -РПМ  (релятивна т. Поста) A та  A є B -РМ  A  T B Наслідок 1. A  T B  D  m D B. Наслідок 2. Якщо A  T B, то D A  T D B. Можливі випадки A < T B та A | T B, для яких теж вірно D A  T D B.

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

Слайд 44

44 Стрибком T-степеня b називають b ' = d T ( D B ), де B  b. Коректність: за наслідком 2 b ' не залежить від вибору конкретного B  b. Властивості операції стрибка jm 1) b < b ' для довільного T -степеня b. jm 2) Якщо a  b, то a '  b '. jm 3) 0 < b ' для довільного T -степеня b. jm 4) Якщо a = b, то a ' = b '. jm 5) Якщо A  a, B  b та B є A -РПМ, то b  a '. T -степінь b повний, якщо b = a ' для деякого T -степеня a. Повний T -степінь складається тільки з Т -повних множин. Множина всіх повних T -степенів є множиною значень операції стрибка.

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

Слайд 45

45 Введемо операцію n - кратного стрибка, або n - стрибка. Для довільної A  N покладемо A (0) = A, Для довільного T -степеня a покладемо a (0) = a, a ( k +1) = ( a ( k ) )'. Властивості операції n-кратного стрибка Ураховуючи A < T D A та a < a ', дістаємо: jn 1) A (0) < T A (1) < T... < T A ( k ) < T A ( k +1) < T... для довільної A  N. jn 2) a (0) < a (1) <... < a ( k ) < a ( k +1) <... для довільного T -степеня a. jn 3) Якщо A  T B, то A ( n )  m B ( n ) для всіх n  1. Теорема. Існує РФ g така:  A, B, z, x якщо  z :   A  m B, то  g ( z, x ) : A ( x )  m B ( x ).

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

Слайд 46

46  - стрибком множини A  N назвемо множину A (  )   =   { C ( x, y ) | x  A ( y ) }.  - стрибком T-степеня a назвемо T -степінь a   (  )   =   d T ( A (  ) ), де A  a. Теорема. A ( n ) < T A (  ) для всіх A, n. Маємо C ( x,  y )  A (  )  x  A ( y )   n  N C ( x,   n )   :   A ( n )   1  A (  )   n A ( n )   T  A (  ). Неможливо A (  )  T  A ( k ) для деякого  k : тоді A (  )  T   A ( k ) < T   A ( k +1)  T   A (  ) – суп-ть. Отже, A ( n )   T  A (  ) для всіх A, n. Теорема. Якщо A  T B, то A (  )  m B (  ). Теорема. Існують множини A і B такі: A (  )  m B (  ) та B < T   A. Візьмемо довільні B  N та n > 0. Покладемо A = B ( n ). Тоді A ( x ) = B ( x + n ) для всіх   x. Звідси u  A (  )  l ( u )  A ( r ( u ))  l ( u )  B ( r ( u )+ n )  C ( l ( u ), r ( u ) + n )  B (  ). Отже, A (  )  m B (  ). Згідно jn 1, маємо B < T B ( n ), тобто B < T A.

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

Последний слайд презентации: 1 ЗВІДНОСТІ Проблема  зводиться до проблеми  : з розв’язності  випливає

47 Упорядкування Т- степенів досить нетривіальне. Теорема (Кліні, Пост). Існує зліченна сукупність Т-степенів, розташованих між 0 та 0 ', лінійно впорядкована за типом раціональних чисел. Теорема. Існують Т-степені а та b такі : 1) a < 0 (  ), b < 0 (  ) та a | b ; 2) 0 ( n ) < a та 0 ( n ) < b для кожного n  N ; 3)  Т-степеня d такого, що d  a та d  b, існує n  N : d    0 ( n ). Наслідок. 1) Т-степені a і b не мають найбільшої нижньої грані ; 2) 0 (  ) не є найменшою верхньою гранню Т-степенів 0, 0 ',..., 0 ( n ),... П.1 наслідку випливає з п.3 теореми. Згідно п.1 теореми a < 0 (  ) та b < 0 (  ). Згідно п. 2 a та b є верхніми гранями Т -степенів 0, 0 ',..., 0 ( n ), …. Звідси п.2 наслідку Теорема (С.   Купер).  Т-степеня b      0 ' існує мінімальний степінь m такий, що m ' = m  0' = b.

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