Задача розв'язності

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

У математиці пробле́мою розв'я́зності (нім. Entscheidungsproblem) називається проблема, сформульована Давидом Гільбертом у 1928 році: знайти алгоритм, який би брав як вхідні дані опис формальної мови та математичного твердження  S на цій мові, і після скінченного числа кроків зупинявся би і видавав одну з двох відповідей: «Істина» або «Хибність», у залежності від того, істинне або хибне твердження  S. Не потрібно, щоб алгоритм давав якесь обґрунтування своєї відповіді, проте відповідь завжди має бути вірною. Такий алгоритм міг би, наприклад, визначити, чи правдиві такі твердження, як гіпотеза Гольдбаха або гіпотеза Рімана, попри те, що ніякого доказу (або спростування) цих тверджень поки не відомо.

У 1936 — Алонзо Черч, а в 1937 — Алан Тюринг опублікували роботи, в яких показали, що не існує алгоритму для визначення істинності тверджень арифметики, а відтак і загальніша проблема розв'язання також не має розв'язку. Цей результат отримав назву теорема Черча-Тюринга.

Див. також[ред.ред. код]