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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

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

Огляд[ред.ред. код]

В 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.

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

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

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

Дивіться також[ред.ред. код]


Комп'ютер Це незавершена стаття про комп'ютери.
Ви можете допомогти проекту, виправивши або дописавши її.