n 2 3 4 5 6 7 .. . Σ(n) 4 6 13 2↑↑↑5 Функція зайнятого бобра Σ(n) зростає швидше ніж будь-яка обчислювана функція
Таким чином можна судити про її необчислюваність; вона розрахована лише частково.
Теорія обчислюваності, також відома як теорія рекурсії, є розділом математичної логіки, інформатики та теорії обчислень, що виникла в 1930-х роках з вивчення обчислюваних функцій і ступенів Тюрінга. З тих пір ця сфера розширилася, включивши в себе вивчення узагальненої обчислюваності та . У цих областях теорія обчислюваності перетинається з теорією доказів та .
Основні питання, які вирішує теорія обчислюваності, включають:
Що означає обчислюваність функції над натуральними числами? Як можна класифікувати необчислювані функції в ієрархію на основі їхнього рівня необчислюваності?
Теоретики математичної обчислюваності вивчають теорію відносної обчислюваності, поняття зводимості та структури ступенів;
В свою чергу, в фокусі інформатики знаходяться теорія субрекурсивних ієрархій, формальні методи і формальні мови.
Обчислювані та необчислювані множини Теорія обчислюваності виникла в 1930-х роках завдяки роботам Курта Геделя, Алонзо Черча, Рози Петер, Алана Тюрінга, Стівена Кліні та Еміля Поста.Many of these foundational papers are collected in The Undecidable (1965) edited by Martin Davis.
Фундаментальні результати, отримані дослідниками, встановили обчислюваність за Тюрінгом як правильну формалізацію неформальної ідеї ефективного обчислення. Ці результати спонукали Стівена Кліні (1952) створити дві назви «теза Черча» і «теза Тюрінга». Нині їх часто розглядають як одну гіпотезу, тезу Черча-Тюрінга, яка стверджує, що будь-яка функція, обчислювана за допомогою алгоритму, є обчислюваною функцією. Хоча спочатку скептично налаштований, до 1946 року Гедель стверджував на користь цієї тези:
«Тарський підкреслив у своїй лекції (і я вважаю справедливо) велике значення концепції загальної рекурсивності (або обчислюваності за Тюрінгом). Мені здається, що ця важливість значною мірою пояснюється тим, що за допомогою цієї концепції вперше вдалося дати абсолютне поняття цікавому гносеологічному поняттю, тобто не залежному від обраного формалізму.*»(Gödel 1946 у Davis 1965:84).The full paper can also be found at pages 150ff (with commentary by Charles Parsons at 144ff) in Feferman et al. editors 1990 Kurt Gödel Volume II Publications 1938—1974, Oxford University Press, New York, . Both reprintings have the following footnote * added to the Davis volume by Gödel in 1965: "To be more precise: a function of integers is computable in any formal system containing arithmetic if and only if it is computable in arithmetic, where a function f is called computable in S if there is in S a computable term representing f (p. 150).
З визначенням ефективного обчислення з'явилися перші докази того, що в математиці є задачі, які неможливо ефективно розв'язати. Черч і Тюрінг, натхненні прийомами, використаними Геделем для доведення його теорем про неповноту, незалежно продемонстрували, що задача Entscheidungs не є ефективно розв'язною. Цей результат показав, що не існує жодної алгоритмічної процедури, яка могла б правильно вирішити, є довільні математичні твердження істинними чи хибними.
Виявилося, що багато задач у математиці не можна вирішити після того, як були встановлені ці початкові приклади. У 1947 році Марков і Пост опублікували незалежні статті, які показали, що неможливо ефективно розв'язати. Розширюючи цей результат, та незалежно показали в 1950-х роках, що не є ефективно розв'язною: не існує ефективної процедури, яка б, задавши слово в скінченно представленій групі, вирішила, чи елемент, представлений словом, є нейтральним елементом групи. У 1970 році Юрій Матіясевич довів (за допомогою результатів Джулії Робінсон) , з якої випливає, що не має ефективного розв'язку; ця задача ставила питання про існування ефективної процедури, яка з'ясовує, чи має діофантове рівняння над цілими числами розв'язок у цілих числах. надає додаткові приклади задач без обчислювального розв'язку.
Вивчення того, які математичні конструкції можна ефективно виконувати, іноді називають рекурсивною математикою; Довідник з рекурсивної математики (Ershov et al. 1998) охоплює багато відомих результатів у цій галузі.
Обчислюваність за Тюрінгом Основна форма обчислюваності, що вивчається в теорії обчислюваності, була введена Тюрінгом (1936). Множина натуральних чисел називається обчислюваною множиною (також званою розв'язуваною, рекурсивною або обчислюваною множиною за Тюрінгом), якщо існує машина Тюрінга, яка приймаючи число n зупиняється з виходом 1, якщо n знаходиться в множині, і зупиняється з виходом 0, якщо n не входить у множину. Функція f від натуральних чисел до натуральних чисел є обчислюваною (за Тюрінгом) або обчислюваною функцією, якщо існує машина Тюрінга, яка прийнявши на вхід n зупиняється та повертає f(n). Використання машин Тюрінга тут не є необхідним; є багато інших моделей обчислень, які мають таку ж обчислювальну потужність, що й машини Тюрінга; наприклад, µ-рекурсивні функції, отримані з примітивної рекурсії та µ-оператора.
Термінологія обчислюваних функцій і множин не повністю стандартизована. Визначення в термінах μ-рекурсивних функцій, а також інше визначення обчислюваних функцій Геделем привели до традиційної назви рекурсивних для множин і функцій, обчислюваних машиною Тюрінга. Слово розв'язувана походить від німецького слова Entscheidungsproblem, яке використовувалося в оригінальних роботах Тюрінга та інших. У сучасному вживанні термін «обчислювана функція» має різні визначення: згідно з Катлендом (1980), це часткова рекурсивна функція (яка може бути невизначеною для деяких вхідних даних), тоді як відповідно до Соаре (1987) вона є повністю рекурсивною (еквівалентно, загальною рекурсивною) функцією. Ця стаття відповідає другому з цих визначень. Соаре (1996) дає додаткові коментарі щодо термінології.
Не кожен набір натуральних чисел є обчислюваним. Задача зупинки, яка являє собою множину (описів) машин Тюрінга, що зупиняються на вході 0, є добре відомим прикладом необчислюваної множини. Існування багатьох необчислюваних множин випливає з того факту, що існує лише зліченна кількість машин Тюрінга, а отже, лише зліченна кількість обчислюваних множин, але згідно з теоремою Кантора існує незліченна кількість множин натуральних чисел.
Хоча задача зупинки не є обчислюваною, можна змоделювати виконання програми та створити нескінченний список програм, які зупиняються. Таким чином, задача зупинки є прикладом , яка являє собою множину, яку можна перелічити машиною Тюрінга (інші терміни для обчислювано перелічуваної множини включають рекурсивно перелічувана та напіврозв'язувана). Еквівалентно, множина є обчислювано перелічуваною тоді і тільки тоді, коли вона є областю значень деякої обчислюваної функції. Обчислювано перелічувані множини, хоча і не розв'язні в цілому, були детально вивчені в теорії обчислюваності.
Напрями досліджень Починаючи з теорії обчислюваних множин і функцій, описаної вище, область теорії обчислюваності розширилася до вивчення багатьох тісно пов'язаних тем. Це не самостійні галузі дослідження: кожна з цих областей черпає ідеї та результати з інших, і більшість теоретиків обчислюваності знайомі з більшістю з них.
Відносна обчислюваність і ступені Тюрінга Теорія обчислюваності в математичній логіці традиційно зосереджується на відносній обчислюваності, узагальненні обчислюваності за Тюрінгом, визначеній за допомогою машин Тюрінга з оракулом, введених Тюрінгом (1939). Машина Тюрінга з оракулом — це гіпотетичний пристрій, який, крім виконання дій звичайної машини Тюрінга, здатний задавати запити оракулу, який є певною множиною натуральних чисел. Машина з оракулом може задавати лише запити виду «Чи є n у множині оракула?». На кожен запит буде негайно дано правильну відповідь, навіть якщо множина оракула не є обчислюваною. Таким чином, машина з оракулом, що має необчислюваний оракул, зможе обчислювати множини, які машина Тюрінга без оракула не може.
Неофіційно, множина натуральних чисел A зводиться за Тюрінгом до множини B, якщо існує машина з оракулом, яка правильно повідомляє, чи є числа в A, коли виконується з B як множиною оракула (у цьому випадку множина A також називається (відносно) обчислюваною з B і рекурсивною в B). Якщо множина A зводиться за Тюрінгом до множини B, а B зводиться за Тюрінгом до A, тоді кажуть, що множини мають однаковий ступінь Тюрінга (також званий ступенем нерозв'язності). Ступінь Тюрінга множини дає точну міру того, наскільки множина є необчислюваною.
Природні приклади необчислюваних множин, включаючи безліч різних множин, які кодують варіанти задачі зупинки, мають дві спільні властивості:
Вони є обчислювано перелічуваними, і Кожна з них може бути зведена до будь-якої іншої за допомогою зводимості багато-до-одного. Тобто для таких множин A і B існує тотальна обчислювана функція f така, що A = {x: f(x) ∈ B}. Ці множини називаються еквівалентними за зводимістю багато-до-одного (або m-еквівалентними).
Зводимість багато-до-одного є «сильнішою», ніж зводимість за Тюрінгом: якщо множина A зводиться до множини B за зводимістю багато-до-одного, то A є зведеною за Тюрінгом до B, але зворотне не завжди виконується. Хоча природні приклади необчислюваних множин є еквівалентними за зводимістю багато-до-одного, можна побудувати обчислювано перелічувані множини A і B так, що A зводиться за Тюрінгом до B, але не зводиться за зводимістю багато-до-одного до B. Можна показати, що кожна обчислювано перелічувана множина зводиться за зводимістю багато-до-одного до задачі зупинки, отже, задача зупинки є найскладнішою обчислювано перелічуваною множиною щодо зводимості багато-до-одного та зводимості за Тюрінгом. Пост (1944) запитав, чи кожна обчислювано перелічувана множина є обчислюваною або еквівалентною за Тюрінгом до задачі зупинки, тобто чи не існує обчислювано перелічуваної множини з проміжним ступенем Тюрінга між цими двома.
Як проміжні результати Пост визначив природні типи обчислювано перелічуваних множин, таких як прості, гіперпрості та гіпергіперпрості множини. Пост показав, що ці множини знаходяться строго між обчислюваними множинами і задачею зупинки щодо зводимості багато-до-одного. Пост також показав, що деякі з них є строго проміжними за іншими поняттями зводимості, більш сильними, ніж зводимість за Тюрінгом. Але Пост залишив відкритою головну задачу існування обчислювано перелічуваних множин проміжного ступеня Тюрінга; ця задача стала відома як задача Поста. Через десять років (в 1954 році) Кліні і Пост показали, що існують проміжні ступені Тюрінга між обчислюваними множинами і задачею зупинки, але їм не вдалося показати, що жоден із цих ступенів містить обчислювано перелічувану множину. Дуже скоро після цього Фрідберг і Мухнік незалежно розв'язали задачу Поста, встановивши існування обчислювано перелічуваних множин проміжного ступеня. Цей новаторський результат відкрив широке вивчення ступенів Тюрінга обчислювано перелічуваних множин, які, як виявилося, мають дуже складну і нетривіальну структуру.
Існує незліченно багато множин, які не є обчислювано перелічуваними, і дослідження ступенів Тюрінга всіх множин є таким же центральним у теорії обчислюваності, як дослідження обчислювано перелічуваних ступенів Тюрінга. Було побудовано багато ступенів зі спеціальними властивостями: гіперімунні ступені, де кожна функція, обчислювана відносно цього ступеня, мажорується (нерелятивізованою) обчислюваною функцією; високі ступені, відносно яких можна обчислити функцію f, яка домінує над кожною обчислюваною функцією g у тому сенсі, що існує константа c, що залежить від g, така, що g(x) < f(x) для всіх x > c; випадкові ступені, що містять ; 1-родові ступені 1-родових множин; і ступені нижче задачі зупинки множин.