Розвʼязні, напіврозвʼязні та нерозвʼязні проблеми; проблема зупинки

📌 Про що ця тема

Тут перевіряють розуміння меж можливостей алгоритмів: чи для будь-якої задачі взагалі існує алгоритм її розвʼязання. Ключові поняття — алгоритмічна розвʼязність і класична проблема зупинки (halting problem), що доводить: є задачі, які неможливо розвʼязати жодним алгоритмом.

📖 Головне

• Алгоритмічна проблема — це задача з нескінченною множиною вхідних даних, на яку потрібна відповідь «так/ні» або точний результат.

• Розвʼязна (вирішувана) проблема — існує алгоритм, який для БУДЬ-ЯКИХ вхідних даних за скінченну кількість кроків дає правильну відповідь і завжди зупиняється. Приклади: чи є число простим, чи належить елемент списку, сортування.

• Напіврозвʼязна (частково розвʼязна) проблема — алгоритм дає правильну відповідь «так» за скінченний час, якщо відповідь «так». Але якщо відповідь «ні», він може працювати нескінченно й не дати відповіді. Тобто гарантована лише одна сторона.

• Нерозвʼязна проблема — алгоритму, який правильно відповідає для всіх випадків, НЕ існує в принципі. Це не питання потужності компʼютера чи часу — рішення неможливе теоретично.

• Проблема зупинки: чи можна побудувати універсальний алгоритм H, який за текстом будь-якої програми P та її вхідними даними визначає, чи зупиниться P, чи зациклиться? Відповідь: такого H не існує. Проблема зупинки нерозвʼязна.

• Ідея доведення (від супротивного): припустимо, H існує. Тоді будуємо програму, яка «робить навпаки» того, що передбачає H про саму себе, — виникає суперечність. Отже, H неможливий.

• Проблема зупинки є напіврозвʼязною: якщо програма ЗУПИНЯЄТЬСЯ, це можна встановити (просто її запустивши). А ось факт зациклення в загальному випадку встановити не можна.

• Співвідношення: усі розвʼязні проблеми є напіврозвʼязними, але не навпаки.

🔢 Як це працює на прикладі

Задача: «Чи зупиниться програма P на вхідних даних D?»

• Спроба наївного рішення: просто запустити P на D. Якщо вона зупинилась — відповідь «так». Але якщо P працює вже годину — ми не знаємо, зупиниться вона за мить чи ніколи. Чекати нескінченно не можна.

• Саме тому задача лише напіврозвʼязна: «так» виявляємо, «ні» — ні.

Інший приклад розвʼязної задачі: «Чи ділиться n на 3?» — алгоритм завжди дає відповідь за скінченний час → повністю розвʼязна.

⚠️ Типові помилки

• Плутають «нерозвʼязна» з «складна/довга». Нерозвʼязність — це принципова неможливість, а не велика складність O.

• Думають, що потужніший компʼютер «розвʼяже» проблему зупинки. Ні — обмеження математичне, а не технічне.

• Вважають напіврозвʼязну проблему розвʼязною, забуваючи про випадок, коли алгоритм не зупиняється.

• Плутають, яка сторона гарантована: у проблемі зупинки надійно виявляється саме «зупиниться», а не «зациклиться».

• Гадають, ніби доведення просто «не знайшли алгоритм». Насправді доведено, що його не існує.

🎯 Що завчити напамʼять

• Розвʼязна = завжди зупиняється з правильною відповіддю.

• Напіврозвʼязна = гарантована лише відповідь «так».

• Нерозвʼязна = алгоритму не існує в принципі.

• Проблема зупинки — нерозвʼязна, але напіврозвʼязна.

• Доведення — від супротивного (самозастосування програми).

🧠 Перевір себе

1. Чим нерозвʼязна проблема відрізняється від обчислювально складної?

2. Чому проблема зупинки вважається напіврозвʼязною?

3. Наведи приклад повністю розвʼязної задачі.

4. Чи допоможе розвʼязати проблему зупинки швидший процесор?

Відповіді: 1 — нерозвʼязна не має алгоритму взагалі, складна має алгоритм, але повільний; 2 — зупинку програми можна виявити запуском, а зациклення в загальному випадку ні; 3 — перевірка подільності/простоти числа, пошук у списку; 4 — ні, обмеження теоретичне, не технічне.