m-повнота і ефективна неперечіслімость
Теорія алгоритмів дозволяє, як кажуть, "конструктівізіровать" різні визначення. Як приклад візьмемо визначення нескінченної кількості. Що таке безліч. Це безліч, яке містить не менше n елементів для будь-якого натурального n. Тепер можна сказати так: безліч називається "ефективно нескінченним", якщо існує алгоритм. який з будь-якого n вказує n різних елементів цієї множини.
48. Покажіть, що довільне безліч A є ефективно нескінченним тоді і тільки тоді, коли воно містить нескінченне перелічуваних безліч (е нескінченно, але не є імунним).
Зараз нас буде цікавити ефективний варіант поняття неперечіслімості. Що значить, що множина A неперечіслімо? Це означає (трюїзм), що A відрізняється від будь-якого рахункового безлічі. Природно називати безліч A ефективно неперечіслімим, якщо з будь-якого перелічуваних безлічі можна вказати місце. де воно відрізняється від A.
Більш формально, зафіксуємо деяке головне універсальне перелічуваних безліч W (і тим самим нумерацію перелічуваних множин: число n ми вважаємо номером безлічі Wn). Будемо говорити, що множина A є ефективно неперечіслімим. якщо існує така всюди певна обчислювана функція f. що Wz при всіх z. (Тут означає симметрическую різниця, інакше кажучи, f (z) є точкою, де A відрізняється від Wz.)
Зауважимо, що це властивість не залежить від вибору головного універсальної множини. так як від номерів щодо одного такого безлічі можна ефективно переходити до номерів щодо іншого.
Властивість ефективної неперечіслімості допускає просту характеризацію в термінах m -сводімості. Почнемо з такого простого спостереження.
Теорема 34. Якщо A <=m B и A эффективно неперечислимо, то и B эффективно неперечислимо.
Ця теорема є "ефективним варіантом" теореми 31, частина (б). Те ж саме можна сказати і про її доказі. Нехай ми хочемо знайти точку, в якій B відрізняється від деякого перечислимого безлічі X. Розглянемо функцію f. яка m -сводіт A до B. Прообраз f -1 (X) перечислимого безлічі X при обчислюваності відображенні буде перерахуємо, тому можна знайти точку m. в якій він відрізняється від A. Тоді B відрізняється від X в точці f (m).
Щоб зробити це міркування точним, нам потрібно лише довести, що номер перечислимого безлічі f-1 (X) може бути ефективно отриманий за номером перечислимого безлічі X. Для цього ми повинні скористатися тим, що нумерація є головною схема тут та сама, що і при обчисленні номера композиції двох обчислюваних функцій, заданих своїми номерами (теорема 16). Проведемо це міркування докладно.
Розглянемо перелічуваних безліч
(Воно перелічуваних, оскільки є прообразом перечислимого безлічі W при обчислюваності відображенні). Легко бачити, що Vn = f -1 (Wn). Так як безліч W є головним універсальним безліччю. то існує обчислювана всюди певна функція s. для якої Ws (n) = Vn = f -1 (Wn) при всіх n. Іншими словами, функція s по W-номер будь-якого рахункового безлічі дає W-номер його прообразу при відображенні f. що і було потрібно.
Теорема 35. Існують перелічуваних безлічі з ефективно неперечіслімимі доповненнями.
Знову розглянемо діагональне безліч. Його доповнення буде ефективно неперечіслімим. Справді, безлічі Wn і D однаково поводяться в точці n. тому Wn відрізняється від доповнення до D в цій точці. Таким чином, додаток до D ефективно неперечіслімо, причому в якості опції f з визначення ефективної неперечіслімості можна взяти тотожну функцію.
З двох попередніх теорем очевидно слід таке твердження:
Теорема 36. Будь-яке m-повне перелічуваних безліч має ефективно неперечіслімое доповнення.
Насправді вірно і зворотне. Щоб переконатися в цьому, доведемо такий факт:
Теорема 37. Нехай K перелічуваних безліч, а A ефективно неперечіслімо. Тоді N \ K <=m A (или, что эквивалентно, K <=m N \ A ).
Насправді нам важливо вміння ефективно відрізняти A лише від двох перелічуваних множин від порожнього і від усього натурального ряду. Відрізнити A від порожнього безлічі означає вказати елемент в A; відрізнити від усього натурального ряду означає вказати елемент поза A. Саме ці дві речі використовуються при зведенні. Більш формально, розглянемо безліч V = K x N. Його перетину Vn або порожні (при), або збігаються з усім натуральним поруч (за наявності). Користуючись тим, що безліч W є головним, ми знаходимо усюди певну функцію s. для якої при і Ws (n) = N прі. Нехай f функція. забезпечує ефективну неперечіслімость безлічі A. Тоді при і при. Іншими словами, композиція функцій f і s зводить N \ K до безлічі A. що і було потрібно.
Звідси очевидно випливають такі твердження:
Теорема 38. перелічуваних безліч є m-повний тоді і тільки тоді, коли його доповнення ефективно неперечіслімо.
Теорема 39. Безліч ефективно неперечіслімо тоді і тільки тоді, коли до нього m -сводітся додаток деякого (варіант: будь-якого) m-повний безлічі.
Відзначимо, що не всяке неперечіслімое безліч ефективно неперечіслімо. Це видно, наприклад, з такого факту:
Теорема 40. Будь-яке ефективно неперечіслімое безліч містить нескінченне перелічуваних підмножина (е не є імунним).
Справді, нехай безліч A ефективно неперечіслімо. Тоді відрізнити його від порожньої множини тобто знайдемо в ньому елемент. Після цього відрізнити його від одноелементна безлічі. яке складається з цього елемента і знайдемо інший елемент. Діючи так, ми може алгоритмічно знайти скільки завгодно багато різних елементів.
У цьому міркуванні ми використовували такий факт: за кінцевим безлічі, заданому списком його елементів, можна отримати його номер (точніше, один з номерів) в головній нумерації перелічуваних множин. Чому це так? Нехай фіксована деяка обчислювана нумерація кінцевих множин. Будемо позначати n -е кінцеве безліч в цій нумерації через Dn. Тоді Dn буде n -им перетином перечислимого (і навіть можливості розв'язання) безлічі
Залишається скористатися визначенням головної нумерації перелічуваних множин.
Прості безлічі. які, як ми знаємо, існують (теорема 14), є прикладами перелічуваних множин, які не є m-повний. Саме так і виникло поняття простого безлічі. Пост шукав приклад перечислимого нерозв'язного безлічі. яке не було б m-повний.