Задача розв'язності
Ця стаття не містить посилань на джерела. (травень 2020) |
В математиці пробле́ма розв'я́зності (нім. Entscheidungsproblem) — проблема, сформульована Давидом Гільбертом 1928 року: знайти алгоритм, який би брав як вхідні дані опис формальної мови та математичного твердження цією мовою, і після скінченного числа кроків зупинявся би й видавав одну з двох відповідей: «Істина» або «Хиба», залежно від того, чи є твердження істинним, чи хибним. Не потрібно, щоб алгоритм давав якесь обґрунтування своєї відповіді, проте відповідь завжди має бути вірною. Такий алгоритм міг би, наприклад, визначити, чи є правдивими такі твердження, як гіпотеза Гольдбаха або гіпотеза Рімана, попри те, що жодного доведення (або спростування) цих тверджень поки не відомо.
1936 року Алонзо Черч та Алан Тюринг опублікували праці, в яких показали, що не існує алгоритму для визначення істинності тверджень арифметики, а відтак і загальніша проблема розв'язання також не має розв'язку. Цей результат отримав назву теза Черча — Тюрінга.
![]() |
Це незавершена стаття з логіки. Ви можете допомогти проєкту, виправивши або дописавши її. |