8.5 Алгоритмічно нерозв’язні проблеми.
Далеко не всі завдання вирішуються алгоритмічно або, як кажуть у математиці, конструктивно.
Обговоримо тепер проблему розв'язання і нерозв'язності з погляду машин Тьюринга, т. е. точного поняття алгоритму. Машина Тьюринга обчислює значення деякої функції натуральних аргументів, інакше кажучи кожна машина представляє деяку функцію. Чи правильно протилежне: кожна функція може бути представлена деякою машиною? Відповісти це питання дуже легко. Оскільки кожна машина однозначно задається своєю програмою, а програму можна записати як послідовність команд - рядок кінцевої довжини в кінцевому алфавіті маємо лічильну кількість рядків, тобто безліч всіх машин Тьюринга рахунково. У той же час безліч усіх функцій натуральних аргументів, що дають як результат натуральні числа - незліченна!
Отже, існують функції, які не обчислюються жодною машиною Тьюринга. Такі функції називаються необчислюваними. Якщо тепер сказати, що обчислення функції — це розв'язання задачі, а програма машини Тьюринга — алгоритм, ми робимо висновок про існуванняалгоритмически нерозв'язних задач.
Теоретично алгоритмів відомо багато таких завдань. Перерахуємо найважливіші їх.
1. Проблемазупинки.Під час обговорення машин Тьюринга було сказано, що у деяких вихідних даних машина може зупинятися, т. е. не давати результату. Будь-яка машина Тьюринга може бути представлена деяким кодом (номером), що відрізняється від інших. Наприклад, кожен стан можна закодувати числом, символи руху за кодувати різними числами. Тоді кожна команда є рядком чисел, який можна інтерпретувати як одне велике число, а послідовність усіх команд — як ще більше.N.Ця чи інша процедура встановлює однозначне відповідність між безліччю натуральних чисел і безліччю алгоритмів. Функція :Natur->Algorithmus,називаєтьсянумерацієюалгоритмів, а її аргументN— номером алгоритму при нумерації . Функція за номеромNвідновлює опис алгоритму, (N)=а. Зворотна функція опису алгоритму визначає його номер. Введення нумерацій дозволяє працювати з алгоритмами як з натуральними числами, що особливо зручно для дослідження алгоритмів над алгоритмами: алгоритм, закодований числом, може розглядатися як вхідні дані іншого алгоритму.Проблема зупинкиполягає у побудові машини Тьюринга М, яка отримуючи на вході код (номер)Nдовільної машини Т і вхідні дані цієї машиниX,визначає, чи зупиниться машина Т на данихX.Інакше кажучи,
M(N,X)= 1, якщо Т зупиняється наX,
M(N,X)=О, якщо Т не зупиняється наX.
Доведено, що машину М побудувати не можна, т. е. проблема зупинки алгоритмічно нерозв'язна.
2.Проблема еквівалентності.Для обчислення однієї й тієї функції можна побудувати дві різні машини Тьюринга, які відрізняються набором команд, отже, і послідовністю дій. Проте для будь-яких вихідних даних обидві машини обчислюватимуть однакові результати. Такі машини звичайно вважати еквівалентними.Проблема еквівалентностіполягає в побудові машини Тьюринга, що отримує на вході описи (коди) двох машин Т1 і Т2 і визначає, чи еквівалентні Т1 і Т2. З практичної точки зору можна поставити аналогічне питання: чи можна написати програму, яка за текстами двох програм наПаскале визначає, чи закінчаться вони однаковими результатами.
Відповідь негативна — проблема еквівалентності алгоритмічно нерозв'язна. Це не означає, що для двох конкретних програм не можна з'ясувати, чи вони еквівалентні. Просто немаєзагальногометоду. Для кожної пари програм доведеться застосовувати власні методи, що залежать від створення цих програм.
Поняття обчислюваної функції (т. е. тієї, на яку існує машина Тьюринга, що її обчислює, — алгоритм) і власне алгоритму не слід змішувати. Відмінність між функцією, що обчислюється, і алгоритмом — це різниця між функцією і способом її завдання. Для однієї й тієї функції може існувати нескінченна кількість способів завдання — текстів алгоритмів. Тривіальний приклад: до тексту алгоритму, що обчислює функцію, припишемо текст тотожного алгоритму (результат якого завжди дорівнює його вхідним даним); новий алгоритм представляє ту саму функцію; тепер припишемо текст тотожного алгоритму ще раз, потім ще раз; отримаємо нескінченну послідовність алгоритмів, що розрізняються, що представляють одну функцію. Подібні факти і породжують безліч проблем теорії алгоритмів, пов'язаних з розв'язністю. Існує навіть теорема Раїса, яка стверджує, що «ніяка нетривіальна властивість обчислюваних функцій не є алгоритмічно розв'язною».
Тривіальне властивість означає належність функції або безлічі всіх функцій, або порожній множині. Нетривіальна властивість - «функціяfналежить класу C», де С - такий непустий клас, що існують функції, що не належать йому. Нумерація всіх алгоритмів є одночасно і нумерацією всіх обчислюваних функцій: функції можна приписати номер одного з алгоритмів, що її обчислюють. Тепер теорему Раїсаможна сформулювати інакше:«Не існує алгоритму, який за номером функціїfвизначав би, чи належить ця функція заданому класу С чи ні».
Зі викладеного видно, що проблема алгоритмічної нерозв'язності досить серйозна. Насправді це означає, що й ставиться проблема побудови алгоритму, що має загальний (універсальний) характер, наприклад, автоматичного синтезу програм з описудовільноїзавдання, то швидше за все така проблема не може бути вирішена. Але якщо проблему обмежити, не орієнтуючись на синтез програм для довільних завдань, а окреслити вужче коло завдань і задати прості правила опису таких завдань, то, ймовірно, проблема може бути вирішена.