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

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

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

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

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

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


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