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

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

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

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

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

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

Див. також

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

Джерела

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