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

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

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

Див. також

• Пророча машина

Джерела