Проблема зупинки та її алгоритмічна нерозв'язність

Маши́на Тю́рінга — математичне поняття, введене для формального уточнення інтуїтивного поняття алгоритму. Названа на честь англійського математика Алана Тюрінга, який запропонував це поняття у 1936. Аналогічну конструкцію машини згодом і незалежно від Тюрінга ввів американський математик Еміль Пост.

Основна ідея, що лежить в основі машини Тюрінга, дуже проста. Машина Тюрінга — це абстрактна машина (автомат), що працює зі стрічкою, що складається із окремих комірок, в яких записано символи. Машина також має голівку для запису та читання символів із комірок і яка може рухатись вздовж стрічки. На кожному кроці машина зчитує символ із комірки, на яку вказує голівка та, на основі зчитаного символу та внутрішнього стану, робиться наступний крок. При цьому, машина може змінити свій стан, записати інший символ в комірку або пересунути голівку на одну комірку ліворуч або праворуч.

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

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

Зависання

Зависання (англ. hang) — комп’ютерне явище, при якому одна чи кілька програм або вся операційна система перестають нормально виконувати свої функції і реагувати на дії користувач|користувача. В цей момент зображення, що виводиться програмою на монітор застигає, на відміну від помилки виконання, при якій на екран видається відповідне повідомлення.

Огляд

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

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

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

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

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

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

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

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

Доведемо це від протилежного. Припустимо, Аналізатор існує. Напишемо алгоритм Діагоналізатор, який приймає на вхід число N , Передає пару аргументів (N, N) Аналізатору і повертає результат його роботи. Іншими словами, Діагоналізатор зупиняється в тому і тільки тому випадку, якщо не зупиняти алгоритм з номером N , Отримавши на вхід число N . Нехай K — Це порядковий номер Діагоналізатора в множині S . Запустимо Діагоналізатор, передавши йому це число K . Діагоналізатор зупиниться в тому і тільки тому випадку, якщо алгоритм з номером K (Тобто, він сам) не зупиняється, отримавши на вхід число K (Яке ми йому і передали). З цієї суперечності випливає, що наше припущення невірно: Аналізатор не існує, що потрібно було довести.

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

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

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

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

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

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

Посилання

• Навчальний проект з курсу "Основи програмування": Машина Тьюринга.