Проблема зупинки

В теорії обчислюваності, проблема зупинки є проблемою розв'язності, що може бути сформульована так:

Дано опис алгоритму та скінченну множину вхідних даних. Треба вирішити, чи виконання алгоритму завершиться, чи він буде виконуватись нескінченно

Огляд

В 1936 році, Алан Тюринг довів, що не може існувати загального алгоритму для розв'язання проблеми зупинки для всіх пар програма-вхідні дані. Тепер проблема зупинки називається нерозв'язною на множині машин Тюринга.

В теорії обчислюваності проблема зупинки — це проблема можливості розв'язання, яка може неформально бути поставлена у вигляді: Дано опис алгоритму і його початкові вхідні дані. Потрібно визначити, чи зможе виконання алгоритму з цими даними завершитися будь-коли. Альтернативою цьому є те, що він працює постійно без зупинки.

Алан Тьюринг довів у 1936, що загальний алгоритм для вирішення проблеми зупинки для будь-яких можливих вхідних даних не може існувати. Ми можемо сказати, що проблема зупинки нерозв'язна на машині Тьюринга.

Розглянемо множину алгоритмів S, які приймають на вхід натуральне число і на виході теж видають натуральне число.

Виберемо якусь повну по Тьюрингу мову програмування. Кожен алгоритм можна записати у вигляді кінцевої послідовності символів на цій мові. Впорядкуємо множину S лексикографічно (в словниковому порядку), при цьому кожен алгоритм отримає свій порядковий номер. Назвемо Аналізатором гіпотетичний алгоритм, який отримує на вхід пару натуральних чисел (N, X), і:

• зупиняється і повертає 1, якщо алгоритм з номером N не зупиняється, отримавши на вхід X
• не зупиняється в іншому випадку (якщо алгоритм з номером N зупиняється, отримавши на вхід X).

Проблему зупинки можна переформулювати наступним чином: чи існує Аналізатор?

Теорема. Аналізатор не існує.

Доведемо - від протилежного.

Припустимо, Аналізатор існує. Напишемо алгоритм Аналізатора Алгоритму Х, який приймає на вхід число N. Аналізатор отримує на вхід пару аргументів (Х, N). Тут є два варіанти. Якщо Алгоритм Х - не зупиняється: Аналізатор зупиняється - ми знайшли такий алгоритм (чудово).

Якщо Алгоритм Х - зупиняється: Аналізатор повертає результат, наприклад Y, і переходить до розгляду наступного алгоритму Х+1 з нескінченної множини алгоритмів.

Доведення.

Виникає суперечність , або зупиняється Алгоритм Х, або Х+1 з числом N. Або зупиняється сам Аналізатор. З цієї суперечності випливає, що наше припущення невірно: Аналізатор не існує, q.e.d. (що було доведено).

Формалізація поняття алгоритму дозволила дослідити існування задач, для яких не існує алгоритмів пошуку розв'язків. Згодом було доведено неможливість алгоритмічного обчислення розв'язків ряду задач, що робить неможливим їхнє розв'язання на будь-якому обчислювальному пристрої.

Функцію f називають обчислюваною (англ. computable), якщо існує машина Тюринга, яка обчислює значення f для всіх елементів множини визначення функції. Якщо такої машини не існує, функцію f називають необчислюваною. Функція вважатиметься необчислюваною навіть, якщо існують машини Тюринга, здатні обчислити значення для підмножини з усієї множини вхідних даних.

Випадок, коли результатом обчислення функції f є булеве значення істина або неправда (або множина {0, 1}) називають задачею, яка може бути розв'язною, або нерозв'язною в залежності від обчислюваності функції f.

Важливо точно вказувати припустиму множину вхідних даних, оскільки задача може бути розв'язною для однієї множини та нерозв'язною для іншої.

Однією з перших задач, для якої було доведено нерозв'язність є проблема зупинки. Формулюється вона наступним чином: Маючи опис програми для машини Тюринга, визначити, чи завершить роботу програма за скінченний час, чи працюватиме нескінченно, отримавши будь-які вхідні дані.

Доведення нерозв'язності проблеми зупинки важливе тим, що до неї можна звести інші задачі. Наприклад, проблему зупинки на порожній стрічці (визначити для заданої машини Тюринга чи зупиниться вона, будучи запущена на порожній стрічці) можна звести до простої задачі зупинки, довівши, тим самим, її нерозв'язність

Нерозв'язність

Існують задачі, що неможливо розв'язати, використовуючи комп'ютер.

Якщо проблема має алгоритм, що на будь-якому екземплярі проблеми правильно відповідає «так» або «ні», то така проблема називається розв'язною. У протилежному разі проблема нерозв'язна.

Питання про пошуки алгоритму, що визначав би істинність або хибність будь-якого математичного твердження, було поставлене ще Гільбертом.

У 1931 Курт Гедель довів теорему про неповноту. Він показав, що існує істинна формула першого порядку з цілими змінними, яку не можна ні довести, ні спростувати у вирахуванні предикатів першого порядку над цілими.

Строге доведення базується на теорії частково рекурсивних функцій і рекурсивно-перелічуваних предикатів.

Ідея доведення

Ідея доведення полягає у тому, щоб побудувати приклад формули, яка була б недовідна і разом з тим змістовно істинна. Для побудови такої формули Гедель запропонував спосіб нумерації виразів формальної системи, який дозволив приписати унікальний номер кожному елементарному символу, формулі або доведенню даної формальної системи. Використовуючи геделівську нумерацію, можна побудувати формулу, яка стверджує недовідність формули з номером n, де n - номер самої цієї формули.

Існування алгоритмічно нерозв'язних проблем

Існування алгоритмічно нерозв'язних проблем випливає вже з теореми Геделя про неповноту формальних систем. Справа у тому, що існує тісний зв'язок між алгоритмами і вирахуваннями. Власне кажучи, і алгоритми, і вирахування – це сукупності чітких, однозначно заданих скінченних інструкцій, що описують якісь дії із символічними об'єктами. Однак у випадку алгоритму ці інструкції мають характер розпоряджень, що задають однозначний порядок виконання операцій над символічними об'єктами, тоді як у випадку вирахувань – інструкції не визначать черговості їх виконання.

Приклади алгоритмічної нерозв’язності

Прикладом алгоритмічної нерозв’язності може бути нерозв’язність “проблеми зупинки”. “Проблема зупинки” – це проблема пошуку універсальної програми, що дозволяє за записом довільної програми (наприклад, функціональної таблиці машини Тюринга), а також за записом довільних вхідних даних установити, чи зупиниться обчислювальний пристрій, що діє відповідно до даної програми і обробляє вхідні дані, або ж він буде працювати нескінченно довго.

Теорема про "зупинку"

Програма називається застосовною до вхідних даних, якщо вона рано чи пізно зупиниться і видасть деякий результат. У протилежному разі говорять, що програма незастосовна до вхідних даних. Теорема про “зупинку” стверджує, що проблема застосовності довільної програми до довільних вхідних даних алгоритмічно нерозв'язна.

Ця теорема доводиться досить просто. Перший крок полягає у тому, що вводиться поняття самозастосовності програми. Програма називається самозастосовною, якщо вона ефективно переробляє текст, що відповідає її власному запису, у деякий результат за скінченне число кроків. У протилежному разі якщо програма не зупиняється і продовжує працювати нескінченно довго, то вона називається не самозастосовною.

Спочатку доводиться таке твердження: не існує програми, застосовної до всіх несамозастосовних програм і тільки до них. Доведення полягає у вказівці на суперечливість поняття про таку програму. Задамося питанням: чи є дана програм самозастосовною? Якщо вона самозастосовна, то вона несамозастосовна (оскільки застосовна лише до несамозастосовних програм). Якщо ж вона несамозастосовна, то вона самозастосовна (оскільки застосовна до всіх несамозастосовних програм).

Виходячи з цього результату, можна також довести неіснування програми, здатної універсальним способом розпізнавати не самозастосовність довільних програм. Дійсно, якщо така програма існує, то можна побудувати й програму, застосовну до всіх не самозастосовних програм і тільки до них.

Розпізнавання несамозастосовності

Позначимо буквою В програму, здатну розпізнавати несамозастосовність. Тоді наступна програма буде програмою, застосовною до всіх несамозастосовних програм і тільки до них.

1. Виконати послідовність команд В, перейти до кроку 2.
2. Якщо отримана відповідь “так”, то перейти до кроку 3, у протилежному разі перейти до кроку 4.
3. Закінчити процес.
4. Перейти до кроку 4.

Ця програма зупиняється, якщо розглянута як вхідні дані програма є несамозастосовною, і не зупиняється (зациклюється на кроці 4) у протилежному разі.

Використовуючи даний результат можна також показати, що не існує й програми, що розпізнає універсальним способом самозастосовність (оскільки у протилежному разі можна побудувати алгоритм, що розпізнає несамозастосовність).

І нарешті, можна показати, що алгоритмічно нерозв'язною є проблема розпізнавання застосовності довільної програми до довільних вхідних даних. Припустимо зворотне. Нехай Е – програма, що за заданою довільною програмою і заданим на вході словом розпізнає застосовність даної програми до даного слова. Неважко побудувати програму, що дозволяє установити, чи є задане слово кодом даної програми. Позначимо таку програму буквою Р.

Тоді можна побудувати програму Н.

1. Застосувати послідовність команд Р. Перейти до кроку 2.
2. Якщо послідовність команд Р дала відповідь “так”, перейти до кроку 3, інакше – до кроку 4.
3. Виконати послідовність команд Е. Кінець.
4. Перейти до кроку 4.

Висновок

Програма Н є програмою, що розпізнає самозастосовність довільних програм. Така програма неможлива, а отже, неможлива і програма Е.

Чому існують нерозв'язні проблеми. Проблема – це питання про приналежність ланцюжка мові. Множина мов над будь-яким алфавітом, де більше одного символу, незліченна. Програми, будучи скінченними ланцюжками у скінченному алфавіті, утворять зліченну множину. Іншими словами, проблем нескінченно більше, ніж програм.

Див. також

• Машина Тюринга
• Зависання
• Теорія алгоритмів
• Список алгоритмів
• Структури даних
• Програмування
• Хвильовий алгоритм

Джерела

• Роджерс Х. Теория рекурсивных функций и эффективная вычислимость. — М. : Мир, 1972. — 416 с.(рос.)
• Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Вычислимые функции. — 4-е. — М : МЦНМО, 2012. — Т. 3. — 160 с.(рос.)