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