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

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

Кристофер Стречи описав коротке доведення від супротивного того факту, що проблема зупинки нерозв'язна. Спершу припустимо, що проблема розв'язна, і існує функція зупиняється(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.

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

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

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

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

Див. також

• Машина Тюрінга
• Зависання

Джерела

• Безущак О., Ганюшкін О. (2023). Математична логіка : навч. посіб (PDF). Київ: Видавничо-поліграфічний центр "Київський університет". с. 143. ISBN 978-966-933-248-6.
• Нікольський Ю.В., Пасічник В.В., Щербина Ю.М. (2024). Дискретна математика : підручник (вид. 7-ме, випр. та допов.). Львів: ПП "Магнолія 2006". с. 432. ISBN 978-617-574-266-2.
• Навчальний проект з курсу «Основи програмування»: Машина Тьюринга.
• Роджерс Х.. Теория рекурсивных функций и эффективная вычислимость. — М. : Мир, 1972. — 416 с.(рос.)
• Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Вычислимые функции. — 4-е. — М : МЦНМО, 2012. — Т. 3. — 160 с.(рос.)