Проблема алгоритмічної розв’язності - Студопедія
Будь-якому алгоритму відповідає завдання, на вирішення якої він був побудований. Зворотне твердження у випадку є неправильним з двох причин: по-перше, одне й те завдання може вирішуватися різними алгоритмами; по-друге, можна припустити (поки що), що є завдання, для яких алгоритм взагалі не може бути побудований.
Як уже зазначалося, термін «алгоритм» з'явився в математиці досить давно і використовувався довго - під ним розумілася процедура, що дозволяла шляхом виконання послідовності певних елементарних кроків отримувати однозначний результат, який не залежить від того, хто ці кроки виконував. Таким чином, саме проведене рішення було доказом існування алгоритму. Однак був відомий цілий ряд математичних завдань, вирішити які загалом не вдавалося. Прикладами можуть бути три стародавні геометричні завдання: про трисекції кута, про квадратуру кола і про подвоєння куба - жодна з них не має загального способу розв'язання за допомогою циркуля і лінійки без поділів.
Інтерес математиків до завдань такого роду призвів до постановки питання: чи можливо, не вирішуючи завдання, довести, що вона алгоритмічно нерозв'язна, тобто. що не можна побудувати алгоритм, який би забезпечив її загальне рішення? Відповідь на це питання важлива, в тому числі, і з практичної точки зору, наприклад, безглуздо намагатися вирішувати завдання на комп'ютері і розробляти для неї програму, якщо доведено, що вона алгоритмічно нерозв'язна. Саме для відповіді на це питання і знадобилося спочатку дати строго визначення алгоритму, без чого обговорення його існування просто не мало сенсу. Побудова такого визначення, як ми вже знаємо, призвела до появи формальних алгоритмічних систем, що даломожливістьматематичного доказунерозв'язності низки проблем. Воно зводиться до доказу неможливості побудови рекурсивної функції, що вирішує завдання, або (що еквівалентно) до неможливості побудови машини Тьюринга для неї, або неспроможності будь-якої іншої моделі з представлених на рис. 7.3. Тобто.завдання вважається алгоритмічно нерозв'язним, якщо не існує машини Тьюринга (або рекурсивної функції, або нормального алгоритму Маркова), яка її вирішує.
Перші докази алгоритмічної нерозв'язності стосувалися деяких питань логіки та самої теорії алгоритмів. Виявилося, наприклад, що нерозв'язне завдання встановлення істинності довільної формули обчислення предикатів (тобто. обчислення предикатів нерозв'язно) - ця теорема була доведена в 1936р. Черчемо.
У 1946-47 р.р. А.А. Марковим та Е. Постом незалежно один від одного довели відсутність алгоритму для розпізнавання еквівалентності слів у будь-якому асоціативному обчисленні.
У теорії алгоритмів до алгоритмічно нерозв'язної відноситься«.проблема зупинки»:можна за описом алгоритму (Q) і вхідними даними (х) встановити, чи завершиться виконання алгоритму результативною зупинкою? Ця проблема має прозору програмістську інтерпретацію. Часто помилки розробки програми призводять дозациклювання -ситуації, коли цикл не завершується і не відбувається завершення роботи програми та зупинки. Нерозв'язність проблеми зупинки означає, що не можна створити загальний (тобто придатний для будь-якої програми) алгоритм налагодження програм. Нерозв'язною виявляється і проблема розпізнавання еквівалентності алгоритмів: не можна побудувати алгоритм, який для будь-яких двох алгоритмів (програм) з'ясовував би, чи завжди вони призводять до того самогорезультату чи ні.
Важливість доказу алгоритмічної нерозв'язності в тому, що якщо такий доказ отримано, він має сенс закону-заборони, що дозволяє не витрачати зусилля на пошук рішення, подібно до того, як закони збереження у фізиці роблять безглуздими спроби побудови вічного двигуна. Разом з цим необхідно усвідомлювати, що алгоритмічна нерозв'язність будь-якого завдання у загальній постановці не виключає можливості того, що можна розв'язати якісь її окремі випадки. Справедливе і протилежне твердження: рішення окремого випадку завдання ще дає підстави вважати можливим її вирішення у загальному випадку, тобто. не свідчить про її загальну алгоритмічну розв'язність. Роль абстрактних алгоритмічних систем у цьому, що вони дозволяють оцінити можливість знаходження повного (загального) рішення деякого класу завдань. Для фахівця в галузі інформатики важливо усвідомлювати, що наявність алгоритмічно нерозв'язних проблем призводить до того, що неможливе побудувати універсальний алгоритм, придатний для вирішення будь-якого завдання (і, отже, безглуздо витрачати сили на його створення). До подібних проблем призводять і спроби алгоритмізувати складну інтелектуальну діяльність людини, наприклад, навчання інших людей, твір віршів та ін.