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

Матеріал з Вікіпедії — вільної енциклопедії.

Перейти до: навігація, пошук

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

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

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

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


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


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