Проблема збіжності Поста

Ця проблема, відома тепер під назвою проблеми збіжності, була разом з відповідним уточненим запропонована Постом в 1944 р. в доповіді. У тій же доповіді Пост вказав нерозв'язні породжуючі множини, для яких природний спосіб доказу їх нерозв'язності не вимагає звернення до еталонної проблеми (це були перші приклади подібних незвичайних доказів нерозв'язності множин). Зрозуміло, це не вирішувало проблему збіжності — тим паче, що для багатьох з вказаних Постом множин самому Посту і його послідовникам вдалося знайти традиційні докази їх нерозв'язності, спираються на відсутність рішення у еталонній проблемі.

Проблема збіжності Поста отримала негативне рішення в роботах Мучника і Фрідберга: були побудовані нерозв'язні породжуючі множини з нееквівалентними проблемами розв'язку (і тим самим — породжуюча множина, нерозв'язність якої може бути встановлена лише методами, відмінними від діагонального).

Уточнення поняття збіжності для проблем розв'язності є самостійним завданням(яка є передумовою для формальної постановки проблеми Поста), вирішеним Постом. Для довільних проблем А і В збіжність В до А означає щось більше, ніж просто імплікацію «A має рішення» → «B має рішення» (ця імплікація тривіально істинна, коли обидві проблеми одночасно розв'язні або нерозв'язні). Якщо А і В — проблеми, то зведення В до А утворює нову, самостійну проблему; на цю обставину уперше було вказано Колмогоровим. У разі, коли А і В суть проблеми розв'язку, здається природним наступне розуміння — воно було запропоноване Постом. Нехай X і Y — ансамблі, Р с Х, Q c Y, а А і В — проблеми розв'язку для відповідно Р і Q.

Збіжність проблеми В до проблеми А або, іншими словами, збіжність по розв'язності множини Q до множини Р означає, згідно з Постом, наявність деякого єдиного способу перетворення інформації про приналежність або неприналежність до Р всіляких елементів X в інформацію про приналежність або неприналежність до Q заданого довільним чином елементу Y. Наявність такого способу дозволяє ефективно давати відповідь на будь-яке питання виду «Y Є Q?», користуючись готовими відповідями на усі питання виду «X Є P?». Збіжність по розв'язку Пост конкретизував у вигляді так званої тюрінгової збіжності, або збіжності по Тюрінгу.

Проблема Поста стимулювала два великі напрями досліджень. Перше з них намагається відповісти на наступне питання: «Чи може проблема Поста бути вирішена методами Поста(викладеними в його доповіді)?» чи, більш технічно, «чи можна методами Поста побудувати неповну зліченну нерозв'язну множину?» (Множина називається повною, якщо воно злічена і до неї тюрінгово зводиться будь-яка злічена множина; так, усі «діагональні» множини повні). Оскільки «методи Поста» можуть розумітися як у вузькому, так і в ширшому сенсі, в результаті уточнення виникають два різні питання:

1. Чи існує така не порожня властивість нерозв'язної множини типу невеликого доповнення, що перераховує, що будь-яке, задовольняюча цій властивості множина неповна?
2. Чи можна сформулювати, і притому без використання поняття «тюрінгова збіжність», таку не порожню властивість злічених нерозв'язних множин, що будь-яка задовільняюча цій властивості множина неповна?

Сам Пост розглядав різні поняття типу майже-скінченності доповнення (простоту, гіперпростоту, гіпергіперпростоту), але жодне з них (і навіть сильніше поняття максимальності, введене згодом Фрідбергом) не виявилося придатним для ствердної відповіді на перше питання.

Позитивну відповідь на друге питання дав Марченков, довівши, що нерозв'язні множини, що перераховують, з деякою властивістю (а саме що є одночасно напіврекурсивними і α-гіпергіперпростими для деякої позитивної еквівалентності α) не можуть бути повними; існування таких великих кількостей було раніше встановлене Дегтєвим.

Перший напрям тісно пов'язаний з вивченням того, як взагалі може бути влаштована породжена (зліченна) множина, розташована в будь-якому фіксованому ансамблі (наприклад, наскільки «щільно» воно може заповнювати охоплюючий простір і який запас великих кількостей, що перераховують, містяться в його доповненні). Відповідно до свого пристрою зліченна множина, може бути віднесена до того або іншого класу. Зліченна множина, може бути розв'язною (якщо її доповнення зліченне), або простою (якщо її доповнення хоча і нескінченне, але не містить нескінченних зліченних підмножин), або креативною (якщо будь-яка програма, будь-якої зліченної підмножини, її доповнення може бути ефективно перетворена в елемент, що належить доповненню, але не цій підмножині) і т. д. Одним з центральних результатів є теорема Майхілла, що стверджує, що будь-які дві креативні множини можуть бути отримані одна з іншої обчислюваною перестановкою охоплюючого ансамблю .

Другий напрям займається так званими мірами нерозв'язності. На сукупності усіх множин, розташованих в цьому ансамблі (або навіть в різних таких ансамблях), задається перед порядок, а саме P≥Q, якщо проблема розв'язку для множини Q зводиться до проблеми розв'язку для множини Р(тобто Q тюрінгово зводиться до Р). Класи еквівалентності цього перед порядку називаються тюрінговими мірами нерозв'язності (коротше — мірами нерозв'язності, або тюрінговими мірами, або Т-мірами). Усі вирішувані множини утворюють одну тюрінгову міру, вона позначається 0 і називається нульовий. Тюрінгова міра називається зліченою, якщо вона містить хоча б одну злічену множину. Існування нерозв'язної зліченої множини, означає, що існує принаймні одна ненульова злічена міра; питання про те, чи існують принаймні дві такі міри, утворює проблему збіжності Поста. Насправді множина всіх злічених мір нескінчена.

На тюрінгових мірах виникає природний частковий порядок, відносно якого безліч цих мір утворює верхню напіврешітку (потужності континууму). Пристрою цієї напівришітки присвячена велика кількість досліджень. Початок був покладений спільною статтею Кліні і Поста. Другим важливим етапом були згадувані вище роботи Мучника і Фрідберга. Зараз проблематика, пов'язана з верхніми напіврешітками Т-мір, міцно увійшла до монографічної і оглядової літератури.

Ось два результати з обговорюваної області, що здаються авторам принциповими : 1) серед ненульових Т-мір існують мінімальні; 2) в частково впорядкованій підмножині ненульових злічених Т- степенів, немає мінімальних елементів. При вивченні верхньої напіврешітки Т-степенів розрізняють глобальну теорію, і вивчаючу загальні властивості Т-степенів, і локальну теорію, яка вивчає Т-мірі, розташовані нижче 0' (так позначається Т-міра креативної великої кількості). Локальна теорія представляє особливий інтерес тому, що вона охоплюючи теорію злічених Т-мір, по суті включає і усю теорію злічених множин. Методи доказу в локальній теорії досить складні. Так, Саксу довелося використати метод пріоритету, щоб отримати мінімальну T — міру, розташовану нижче 0', а Куперу — винайти так званий метод повної апроксимації, щоб для будь-якої ненульової зліченої Т — міри а побудувати мінімальну ненульову Т — міру, розташовану нижче а.

Відмітимо на закінчення, що разом з T- збіжністю Пост ввів і інші види збіжності.

• Успенский В. Д., Семенов А. Л. Теория алгоритмов; основные открытия и приложения. — М.: Наука. Гл. ред. физ.-мат. лит., 1987. — (Б-чка программиста). — 288 с. (93 с.)