1.3.2. Розв'язні, напіврозв'язні та нерозв'язні проблеми. Проблема зупинки
Алгоритмічна розв'язність — властивість формальної теорії володіти алгоритмом, який визначає за даною формулою, виводиться вона з множини аксіом даної теорії чи ні. Теорія називається розв'язною, якщо такий алгоритм існує, і нерозв'язною, в іншому випадку. Питання про виводимість у формальній теорії є частковим, але разом з тим найважливішим випадком більш загальної проблеми розв'язності.
Розв'язність — дуже сильна властивість, і більшість корисних і використовуваних на практиці теорій нею не володіють. У зв'язку з цим було введено слабше поняття напіврозв'язності. Напіврозв'язність означає наявність алгоритму, який за скінченний час завжди підтвердить, що речення істинне, якщо це дійсно так, але якщо ні — може працювати нескінченно.
Вимога напіврозв'язності еквівалентна можливості ефективно перелічити всі теореми даної теорії. Іншими словами, множина теорем повинна бути рекурсивно-зліченною. Більшість використовуваних на практиці теорій задовольняють цій вимозі.
Велике практичне значення мають ефективні напіврозв'язувальні процедури для логіки першого порядку, оскільки вони дозволяють (напів)автоматично доводити формалізовані твердження дуже широкого класу. Проривом у цій галузі було відкриття Робінсоном у 1965 році методу резолюцій.
Алгоритмічна нерозв'язність - найважливіша властивість деяких класів коректно поставлених завдань, що допускають застосування алгоритмів, яка полягає в тому, що задача кожного з цих класів у принципі не має загального, універсального алгоритму розв’язання, що об'єднує цей клас.
Алгоритмічна нерозв'язність не є проблемою теорії алгоритмів або невдачею, вона є науковим фактом. Популярність досліджень алгоритмічної нерозв'язності не поступається будь-яким іншим дослідженням у теорії алгоритмів і потребує іноді значних зусиль. Наприклад, доведення алгоритмічної нерозв'язності 10-ї проблеми Гільберта, одержане Ю. В. Матіясевичем, відносять до видатних наукових досягнень XX століття.
Знання можливої алгоритмічної нерозв’язності має в галузі комп’ютерних технологій таке саме значення, як для фізика знання про неможливість створення вічного двигуна. Припустимо, що до Білла Гейтса приходить винахідник з пропозицією надати йому грант (грошові інвестиції) для написання програми, яка приймає на вхід будь-яку програму і видає відповідь, потрапить ця програма в нескінченний цикл чи ні за будь-яких вхідних даних. Б. Гейтс йому, звісно, відповідь, оскільки знає, що ця задача є алгоритмічно нерозв'язною.
В теорії обчислюваності алгоритмічно нерозв'язною задачею називається задача, що має відповідь так чи ні для кожного об'єкта з деякої множини вхідних даних, для якої (принципово) не існує алгоритму, який би, отримавши будь-який можливий як вхідні дані об'єкт, зупинявся і давав правильну відповідь після скінченного числа кроків.
Існують задачі, що неможливо розв'язати, використовуючи комп'ютер.
Якщо проблема має алгоритм, що на будь-якому екземплярі проблеми правильно відповідає «так» або «ні», то така проблема називається розв'язною. У протилежному разі проблема нерозв'язна.
Питання про пошуки алгоритму, що визначав би істинність або хибність будь-якого математичного твердження, було поставлене ще Гільбертом.
У 1931 Курт Гедель довів теорему про неповноту. Він показав, що існує істинна формула першого порядку з цілими змінними, яку не можна ні довести, ні спростувати у вирахуванні предикатів першого порядку над цілими.
Строге доведення базується на теорії частково рекурсивних функцій і рекурсивно-перелічуваних предикатів.
Існують задачі, що неможливо розв'язати, використовуючи комп'ютер.
Якщо проблема має алгоритм, що на будь-якому екземплярі проблеми правильно відповідає «так» або «ні», то така проблема називається розв'язною. У протилежному разі проблема нерозв'язна.
Масову проблему називають алгоритмічно розв’язною, або розв’язною, якщо предикат, який її визначає, є рекурсивний, інакше проблему називають алгоритмічно нерозв’язною, або нерозв’язною.
Масову проблему називають частково алгоритмічно розв’язною, або частково розв’язною, або напіврозв’язною, якщо предикат, який її визначає, є частково рекурсивний.
В теорії обчислюваності та складності обчислень проблема зупинки є проблемою визначення чи завершиться дана комп'ютерна програма отримавши певні вхідні дані за скінченний час чи буде працювати нескінченно. Проблема зупинки - алгоритмічно нерозв'язна задача, тобто не існує алгоритму (програми) який би розв'язував проблему зупинки для всіх можливих пар програма-вхідні дані.
Кристофер Стречи описав коротке доведенння від протилежного того факту що проблема зупинки нерозв'язна. Спершу припустимо що проблема розв'язна, і існує функція зупиняється(f), яка повертає true, якщо програма f зупиняється і false - якщо ні. Тоді, маючи функцію:
def парадокс():
if зупиняється(парадокс):
нескінченний_цикл()
return 'зупинилася'
зупиняється(парадокс) згідно початкового припущення має повернути true або false, але у випадку true парадокс увійде у нескінченний цикл і не зупиниться, тому такий результат суперечитиме визначенню функції зупиняється. У випадку false - аналогічно. Маємо суперечність, тому початкове припущення про те що функція зупиняється може існувати - хибне.
В 1936 році, Алан Тюринг довів, що не може існувати загального алгоритму для розв'язання проблеми зупинки для всіх пар програма-вхідні дані. Тепер проблема зупинки називається нерозв'язною на множині машин Тюринга.
Розглянемо множину алгоритмів S, які приймають на вхід натуральне число і на виході теж видають натуральне число.
Виберемо якусь повну за Тюрингом мову програмування. Кожен алгоритм можна записати у вигляді скінченної послідовності символів на цій мові. Впорядкуємо множину S лексикографічно (в словниковому порядку), при цьому кожен алгоритм отримає свій порядковий номер. Назвемо "Аналізатором" гіпотетичний алгоритм, який отримує на вхід пару натуральних чисел (N, X), і:
зупиняється і повертає 1, якщо алгоритм з номером N не зупиняється, отримавши на вхід X
не зупиняється в іншому випадку (якщо алгоритм з номером N зупиняється, отримавши на вхід X).
Проблему зупинки можна переформулювати наступним чином: чи існує Аналізатор?
Теорема. Аналізатор не існує.
Доведемо — від протилежного.
Припустимо, Аналізатор існує. Напишемо алгоритм Аналізатора Алгоритму Х, який приймає на вхід число N. Аналізатор отримує на вхід пару аргументів (Х, N). Тут є два варіанти. Якщо Алгоритм Х — не зупиняється: Аналізатор зупиняється — ми знайшли такий алгоритм (чудово).
Якщо Алгоритм Х — зупиняється: Аналізатор повертає результат, наприклад Y, і переходить до розгляду наступного алгоритму Х+1 з нескінченної множини алгоритмів.
Доведення.
Виникає суперечність, або зупиняється Алгоритм Х, або Х+1 з числом N. Або зупиняється сам Аналізатор. З цієї суперечності випливає, що наше припущення невірно: Аналізатор не існує, що і треба було довести.
Формалізація поняття алгоритму дозволила дослідити існування задач, для яких не існує алгоритмів пошуку розв'язків. Згодом було доведено неможливість алгоритмічного обчислення розв'язків ряду задач, що робить неможливим їхнє розв'язання на будь-якому обчислювальному пристрої.
Функцію f називають обчислюваною (англ. computable), якщо існує машина Тюринга, яка обчислює значення f для всіх елементів множини визначення функції. Якщо такої машини не існує, функцію f називають необчислюваною. Функція вважатиметься необчислюваною навіть, якщо існують машини Тюринга, здатні обчислити значення для підмножини з усієї множини вхідних даних.
Випадок, коли результатом обчислення функції f є булеве значення істина або неправда (або множина {0, 1}) називають задачею, яка може бути розв'язною, або нерозв'язною в залежності від обчислюваності функції f.
Важливо точно вказувати припустиму множину вхідних даних, оскільки задача може бути розв'язною для однієї множини та нерозв'язною для іншої.
Однією з перших задач, для якої було доведено нерозв'язність є проблема зупинки. Формулюється вона наступним чином: Маючи опис програми для машини Тюринга, визначити, чи завершить роботу програма за скінченний час, чи працюватиме нескінченно, отримавши будь-які вхідні дані.
Доведення нерозв'язності проблеми зупинки важливе тим, що до неї можна звести інші задачі. Наприклад, проблему зупинки на порожній стрічці (визначити для заданої машини Тюринга чи зупиниться вона, будучи запущена на порожній стрічці) можна звести до простої задачі зупинки, довівши, тим самим, її нерозв'язність.
