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