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