Теорія обчислюваності

Про Концепт обчислюваності див. Обчислюваність.

n	2	3	4	5	6	7	.. .
Σ(n)	4	6	13	4098 ?	≥ 2↑↑↑5	?	?
Функція зайнятого бобра Σ(n) зростає швидше ніж будь-яка обчислювана функція Таким чином можна судити про її необчислюваність; вона розрахована лише частково.

Теорія обчислюваності, також відома як теорія рекурсії, є розділом математичної логіки, інформатики та теорії обчислень, що виникла в 1930-х роках з вивчення обчислюваних функцій і ступенів Тюрінга. З тих пір ця сфера розширилася, включивши в себе вивчення узагальненої обчислюваності та визначеності. У цих областях теорія обчислюваності перетинається з теорією доведення та ефективною описовою теорією множин.

Основні питання, які вирішує теорія обчислюваності, включають:

• Що означає обчислюваність функції над натуральними числами?
• Як можна класифікувати необчислювані функції в ієрархію на основі їхнього рівня необчислюваності?

Теоретики математичної обчислюваності вивчають теорію відносної обчислюваності, поняття зводимості та структури ступенів;

В свою чергу, в фокусі інформатики знаходяться теорія субрекурсивних ієрархій, формальні методи і формальні мови.

Обчислювані та необчислювані множини

Теорія обчислюваності виникла в 1930-х роках завдяки роботам Курта Геделя, Алонзо Черча, Рози Петер, Алана Тюрінга, Стівена Кліні та Еміля Поста.

Фундаментальні результати, отримані дослідниками, встановили обчислюваність за Тюрінгом як правильну формалізацію неформальної ідеї ефективного обчислення. Ці результати спонукали Стівена Кліні (1952) створити дві назви «теза Черча»^:300 і «теза Тюрінга»^:376. Нині їх часто розглядають як одну гіпотезу, тезу Черча-Тюрінга, яка стверджує, що будь-яка функція, обчислювана за допомогою алгоритму, є обчислюваною функцією. Хоча спочатку скептично налаштований, до 1946 року Гедель стверджував на користь цієї тези:

«Тарський підкреслив у своїй лекції (і я вважаю справедливо) велике значення концепції загальної рекурсивності (або обчислюваності за Тюрінгом). Мені здається, що ця важливість значною мірою пояснюється тим, що за допомогою цієї концепції вперше вдалося дати абсолютне поняття цікавому гносеологічному поняттю, тобто не залежному від обраного формалізму.*»(Gödel 1946 у Davis 1965:84).

З визначенням ефективного обчислення з'явилися перші доведення того, що в математиці є задачі, які неможливо ефективно розв'язати. Черч і Тюрінг, натхненні прийомами, використаними Геделем для доведення його теорем про неповноту, незалежно продемонстрували, що задача 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, тоді кажуть, що множини мають однаковий ступінь Тюрінга (також званий ступенем нерозв'язності). Ступінь Тюрінга множини дає точну міру того, наскільки множина є необчислюваною.

Природні приклади необчислюваних множин, включаючи безліч різних множин, які кодують варіанти задачі зупинки, мають дві спільні властивості:

1. Вони є обчислювано перелічуваними, і
2. Кожна з них може бути зведена до будь-якої іншої за допомогою зводимості багато-до-одного. Тобто для таких множин 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-родових множин; і ступені нижче задачі зупинки гранично обчислюваних множин.

Вивчення довільних (не обов'язково обчислювано перелічуваних) ступенів Тюрінга включає вивчення стрибка Тюрінга. Для множини A стрибок Тюрінга A — це множина натуральних чисел, що кодує розв'язок задачі зупинки для машин Тюрінга з оракулом A. Ступінь Тюрінга стрибка будь-якої множини завжди є вищим, ніж ступінь вихідної множини, і теорема Фрідберга показує, що будь-яку множину, яка обчислює задачу зупинки, можна отримати як стрибок Тюрінга іншої множини. Теорема Поста встановлює тісний зв'язок між операцією стрибка Тюрінга та арифметичною ієрархією, яка є класифікацією певних підмножин натуральних чисел на основі їх визначеності в арифметиці.

Більшість останніх досліджень ступенів Тюрінга зосереджені на загальній структурі множини ступенів Тюрінга та множини ступенів Тюрінга, що містять обчислювано перелічувані множини. Глибока теорема Шора і Сламана (1999) стверджує, що функція, яка відображає ступінь x у ступінь його стрибка Тюрінга, є визначуваною в частковому порядку ступенів Тюрінга. Нещодавнє дослідження, проведене Амбос-Шпієсом і Фейєром (2006), дає огляд цього дослідження та його історичного прогресу.

Інші зводимості

Поточна область досліджень у теорії обчислюваності вивчає відношення зводимості, відмінні від зводимості за Тюрінгом. Пост (1944) ввів кілька сильних зводимостей, названих так тому, що вони передбачають зводимість таблиці істинності. Машина Тюрінга, що реалізує сильну зводимість, обчислює тотальну функцію незалежно від того, який оракул їй представлено. Слабкі зводимості — це ті, де процес зведення може не завершитися для всіх оракулів; зводимість за Тюрінгом є одним із прикладів.

До сильних зводимостей належать:

Зводимість один-до-одного

A є зведеною один-до-одного до B, якщо існує тотальна обчислювана ін'єктивна функція f така, що кожне n знаходиться в A тоді й тільки тоді, коли f(n) знаходиться в B.

Зводимість багато-до-одного

Це, по суті, зводимість один-до-одного без обмеження, що f є ін'єктивною. A є зведеною багато-до-одного (або m-зведеною) до B, якщо існує тотальна обчислювана функція f така, що кожне n знаходиться в A тоді і тільки тоді, коли f(n) знаходиться в B.

Зводимість таблиці істинності

A є зведеною до B за таблицею істинності, якщо A є зведеною за Тюрінгом до B за допомогою машини Тюрінга з оракулом, яка обчислює тотальну функцію незалежно від того, який оракул їй задано. Через компактність простору Кантора це еквівалентно тому, що зведення одночасно представляє оракулу єдиний список запитів (залежно від вхідних даних), а потім, побачивши їх відповіді, може створити вихідні дані, не задаючи додаткових запитів незалежно від відповідей оракула на початкові запити. Зводимість за таблицею істинності також широко досліджена.

Подальші зводимості (позитивна, диз'юнктивна, кон'юнктивна, лінійна та їх слабкі та обмежені варіанти) розглядаються в статті Редукція (теорія обчислюваності).

Основним напрямом дослідження сильних зводимостей було порівняння їхніх теорій, як для класу всіх обчислювано перелічуваних множин, так і для класу всіх підмножин натуральних чисел. Крім того, досліджено співвідношення між зводимостями. Наприклад, відомо, що кожен ступінь Тюрінга або є ступенем за таблицею істинності, або є об'єднанням нескінченної кількості ступенів за таблицею істинності.

Також досліджувалися зводимості, слабші за зводимість за Тюрінгом (тобто зводимості, що випливають із зводимості за Тюрінгом). Найбільш відомими є арифметична зводимість і гіперарифметична зводимість. Ці зводимості тісно пов'язані з визначеністю відносно стандартної моделі арифметики.

Теорема Райса та арифметична ієрархія

Райс показав, що для кожного нетривіального класу C (який містить деякі, але не всі обчислювано перелічувані множини) індексна множина E = {e: e-та обчислювано перелічувана множина W_e знаходиться в C} має властивість, що або задача зупинки, або її доповнення є зведеною за зводимістю багато-до-одного до E (докладніше див. теорему Райса). Але багато з цих індексних множин є навіть складнішими, ніж задача зупинки. Цей тип множин можна класифікувати за допомогою арифметичної ієрархії. Наприклад, індексна множина FIN класу всіх скінченних множин знаходиться на рівні Σ₂, індексна множина REC класу всіх рекурсивних множин знаходиться на рівні Σ₃, індексна множина COFIN всіх кокінцевих множин також знаходиться на рівні Σ₃, а індексна множина COMP класу всіх повних множин за Тюрінгом — на рівні Σ₄. Ці рівні ієрархії визначаються індуктивно: Σ_n+1 містить лише всі множини, які є обчислювано перелічуваними відносно Σ_n; Σ₁ містить обчислювано перелічувані множини. Наведені тут індексні множини є повними для своїх рівнів, тобто всі множини на цих рівнях можуть бути зведені за зводимістю багато-до-одного до зазначених індексних множин.

Зворотна математика

Програма зворотної математики запитує, які аксіоми існування множин необхідні для доведення конкретних теорем математики в підсистемах арифметики другого порядку. Це дослідження було ініційоване Харві Фрідманом, а його детально вивчали Стівен Сімпсон та інші; Сімпсон (1999) дає детальне обговорення програми. Аксіоми існування множин, про які йде мова, неформально відповідають аксіомам, які стверджують, що множина степенів натуральних чисел замкнена відносно різних понять зводимості. Найслабшою такою аксіомою, що вивчається у зворотній математиці, є рекурсивне розуміння, яке стверджує, що множина степенів натуральних чисел замкнена відносно зводимості за Тюрінгом.

Нумерація

Нумерація — це перелічення функцій; вона має два параметри, e і x, і виводить значення e-ї функції в нумерації на вхід x. Нумерація може бути частково обчислюваною, хоча деякі її члени є тотальними обчислюваними функціями. Допустимі нумерації — це нумерації, до яких можна звести всі інші. Нумерація Фрідберга (названа на честь її першовідкривача) — це нумерація один-до-одного всіх частково обчислюваних функцій. Пізніші дослідження також стосувалися нумерацій інших класів, наприклад класів обчислювано перелічуваних множин. Гончаров відкрив, наприклад, клас обчислювано перелічуваних множин, для яких нумерації поділяються точно на два класи відносно обчислювальних ізоморфізмів.

Метод пріоритетів

Задача Поста була розв'язана за допомогою методу, який називається методом пріоритетів; доведення, яке спирається на цей метод, називається аргументом пріоритетів. Цей метод в основному використовується для побудови обчислювано перелічуваних множин з певними властивостями. Щоб використовувати цей метод, бажані властивості множини, яку потрібно побудувати, розбиваються на нескінченний список цілей, відомих як вимоги, так що виконання всіх вимог призведе до того, що побудована множина матиме потрібні властивості. Кожній вимозі присвоюється натуральне число, що представляє пріоритет вимоги; так, 0 призначається найважливішому пріоритету, 1 — другому за важливістю тощо. Потім множина будується поетапно, кожен етап намагається задовольнити одну чи кілька вимог шляхом додавання чисел до множини або виключення чисел з множини, щоб кінцева множина задовольнила вимогу. Може статися, що задоволення однієї вимоги призведе до незадоволення іншої; порядок пріоритетів використовується, щоб вирішити, що робити в такому випадку.

Аргументи пріоритетів були використані для розв'язання багатьох задач у теорії обчислюваності та були класифіковані в ієрархії на основі їх складності (Соаре 1987). Оскільки складні аргументи пріоритетів можуть бути технічними і важкими для сприйняття, традиційно вважалося бажаним доводити результати без аргументів пріоритетів або перевіряти, чи результати, доведені за допомогою аргументів пріоритетів, також можна довести без них. Наприклад, Куммер опублікував статтю з доведення існування нумерації Фрідберга без використання методу пріоритетів.

Решітка обчислювано перелічуваних множин

Коли Пост визначив поняття простої множини як обчислювано перелічуваної множини з нескінченним доповненням, що не містить жодної нескінченної обчислювано перелічуваної множини, він почав вивчати структуру обчислювано перелічуваних множин при включенні. Ця решітка стала добре вивченою конструкцією. Обчислювані множини можна визначити в цій структурі завдяки базовому результату: множина є обчислюваною тоді й тільки тоді, коли множина та її доповнення є обчислювано перелічуваними. Нескінченні обчислювано перелічувані множини завжди мають нескінченні обчислювані підмножини; але, з іншого боку, прості множини існують та не завжди мають кокінцеву обчислювану надмножину. Пост (1944) ввів гіперпрості та гіпергіперпрості множини; пізніше були побудовані максимальні множини — обчислювано перелічувані множини такі, що кожна обчислювано перелічувана надмножина є або скінченним варіантом даної максимальної множини, або кокінцевою. Початкова мотивація Поста у дослідженні цієї решітки полягала в тому, щоб знайти структурну властивість, при якій кожна множина, що задовольняє цю властивість, не перебуває ні в ступені Тюрінга обчислюваних множин, ні в ступені Тюрінга задачі зупинки. Пост не знайшов такої властивості, і замість цього для розв'язання його задачі застосували методи пріоритетів; Гаррінгтон і Соаре (1991) врешті знайшли таку властивість.

Задачі автоморфізму

Іншим важливим питанням є існування автоморфізмів у структурах теорії обчислюваності. Однією з цих структур є структура обчислювано перелічуваних множин при включенні за модулем скінченної різниці; у цій структурі A знаходиться нижче B тоді і тільки тоді, коли різниця B − A є скінченною. Максимальні множини (як визначено в попередньому абзаці) мають властивість, що вони не можуть бути автоморфними до немаксимальних множин, тобто якщо існує автоморфізм обчислювано перелічуваних множин у щойно згаданій структурі, то кожна максимальна множина відображається на іншу максимальну множину. Соаре (1974) показав, що виконується і зворотне, тобто будь-які дві максимальні множини є автоморфними. Отже, максимальні множини утворюють орбіту: кожен автоморфізм зберігає максимальність, і будь-які дві максимальні множини перетворюються одна в одну за допомогою деякого автоморфізму. Харрінгтон навів ще один приклад автоморфної властивості: властивість творчих множин — множин, які є еквівалентними за зводимістю багато-до-одного задачі зупинки.

Крім решітки обчислювано перелічуваних множин, автоморфізми досліджуються також для структури ступенів Тюрінга всіх множин, а також для структури ступенів Тюрінга обчислювано перелічуваних множин. В обох випадках Купер стверджує, що побудував нетривіальні автоморфізми, які відображають одні ступені в інші; ця конструкція, однак, не була перевірена, і деякі колеги вважають, що конструкція містить помилки і що питання про те, чи існує нетривіальний автоморфізм ступенів Тюрінга, досі залишається одним з основних невирішених питань у цій галузі.

Колмогоровська складність

Галузь колмогоровської складності та алгоритмічної випадковості була розроблена протягом 1960-х і 1970-х років Чайтіним, Колмогоровим, Левіним, Мартін-Льофом і Соломоновим (імена наведено в алфавітному порядку; значна частина досліджень була незалежною, і єдність концепції випадковості на той час не була зрозуміла). Основна ідея полягає в тому, щоб розглянути універсальну машину Тюрінга U і виміряти складність числа (або рядка) x як довжину найкоротшого входу p такого, що U(p) виводить x. Цей підхід революціонізував попередні способи визначення того, коли нескінченна послідовність (еквівалентно, характеристична функція підмножини натуральних чисел) є випадковою чи ні, використовуючи поняття випадковості для скінченних об'єктів. Колмогоровська складність стала не тільки предметом самостійного вивчення, але й застосовується до інших предметів як інструмент для отримання доведень. У цій сфері залишається багато відкритих задач. З цієї причини в січні 2007 року відбулася дослідницька конференція в цій галузі, а список відкритих задач ведуть Джозеф Міллер та Андре Ніс.

Частотні обчислення

Ця галузь теорії обчислюваності аналізувала таке питання: для фіксованих m і n де 0 < m < n, для яких функцій A можна обчислити для будь-яких різних n входів x₁, x₂, …, x_n кортеж із n чисел y₁, y₂,…,y_n таких, що принаймні m рівностей A(x_k) = y_k є істинними. Такі множини відомі як (m, n)-рекурсивні множини. Першим основним результатом у цій галузі теорії обчислюваності є результат Трахтенброта про те, що множина є обчислюваною, якщо вона є (m, n)-рекурсивною для деяких m, n з 2m > n. З іншого боку, напіврекурсивні множини Джокуша (які вже були відомі неофіційно до того, як Джокуш представив їх у 1968 році) є прикладами множини, яка є (m, n)-рекурсивною тоді і тільки тоді, коли 2m < n + 1. Існує незліченна кількість таких множин, а також деякі обчислювано перелічувані, але необчислювані. Пізніше Дегтєв встановив ієрархію обчислювано перелічуваних множин, які є (1, n + 1)-рекурсивними, але не (1, n)-рекурсивними. Після тривалого етапу досліджень російських вчених ця тема знову стала поширеною на Заході завдяки дисертації Бейгеля про обмежені запити, яка пов'язала частотні обчислення з вищезгаданими обмеженими зводимостями та іншими пов'язаними поняттями. Одним з головних результатів була теорема потужності Куммера, яка стверджує, що множина A є обчислюваною тоді і тільки тоді, коли існує n таке, що деякий алгоритм перераховує для кожного кортежу з n різних чисел до n можливих варіантів потужності перетину цих n чисел з A; ці варіанти повинні містити справжню потужність, але допускати принаймні один хибний.

Індуктивний висновок

Це галузь теорії навчання, що спирається на теорію обчислюваності. Вона заснована на моделі навчання в границі Е. Марка Голда з 1967 року і з тих пір розробляє все більше і більше моделей навчання. Загальний сценарій виглядає наступним чином: для класу обчислюваних функцій S чи існує учень (тобто обчислюваний функціонал), який виводить гіпотезу для будь-якого входу виду (f(0), f(1),…, f(n)). Учень M вивчає функцію f, якщо майже всі гіпотези мають однаковий індекс e для f відносно попередньо узгодженої допустимої нумерації всіх обчислюваних функцій; M вивчає S, якщо M вивчає кожну f у S. Основні результати полягають у тому, що всі обчислювано перелічувані класи функцій є такими, що вивчаються, тоді як клас REC усіх обчислюваних функцій не є таким. Було розглянуто багато пов'язаних моделей, а також вивчення класів обчислювано перелічуваних множин із позитивних даних є темою, яка досліджується з новаторської роботи Голда в 1967 році.

Узагальнення обчислюваності за Тюрінгом

Теорія обчислюваності включає вивчення узагальнених понять цієї галузі, таких як арифметична зводимість, гіперарифметична зводимість і теорія α-рекурсії, як описано Саксом (1990). Ці узагальнені поняття включають зводимості, які не можуть бути виконані машинами Тюрінга, але, тим не менш, є узагальненнями зводимості за Тюрінгом. Ці дослідження включають підходи до вивчення аналітичної ієрархії, яка відрізняється від арифметичної тим, що дозволяє кількісно оцінювати множини натуральних чисел на додаток до окремих чисел. Ці галузі пов'язані з теоріями добре впорядкованих множин і дерев; наприклад, множина всіх індексів обчислюваних (небінарних) дерев без нескінченних гілок є повною для рівня $\Pi _{1}^{1}$ аналітичної ієрархії. У галузі ефективної описової теорії множин важливі як зводимість за Тюрінгом, так і гіперарифметична зводимість. Ще більш загальне поняття ступенів конструктивності вивчається в теорії множин.

Теорія неперервної обчислюваності

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

Зв'язки між визначеністю, доведенням і обчислюваністю

Існує тісний зв'язок між ступенем Тюрінга множини натуральних чисел і складністю (з точки зору арифметичної ієрархії) визначення цієї множини за допомогою формули першого порядку. Один з таких зв'язків уточнюється теоремою Поста. Більш слабкий зв'язок був продемонстрований Куртом Геделем у доведеннях його теореми про повноту та теорем про неповноту. Доведення Геделя показують, що множина логічних наслідків ефективної теорії першого порядку є обчислювано перелічуваною множиною, і якщо теорія достатньо сильна, ця множина буде необчислюваною. Аналогічно, теорема про невизначеність Тарського може бути інтерпретована як з точки зору визначеності, так і з точки зору обчислюваності.

Теорія обчислюваності також пов'язана з арифметикою другого порядку, формальною теорією натуральних чисел і множин натуральних чисел. Той факт, що певні множини є обчислюваними або відносно обчислюваними, часто означає, що ці множини можна визначити в слабких підсистемах арифметики другого порядку. Програма зворотної математики використовує ці підсистеми для вимірювання необчислюваності, властивої добре відомим математичним теоремам. Сімпсон (1999) обговорює багато аспектів арифметики другого порядку та зворотної математики.

Сфера теорії доведень включає вивчення арифметики другого порядку та арифметики Пеано, а також формальних теорій натуральних чисел, слабших, ніж арифметика Пеано. Одним із методів класифікації сили цих слабких систем є визначення того, для яких обчислюваних функцій система може довести їх тотальність. Наприклад, у примітивно-рекурсивній арифметиці будь-яка обчислювана функція, яка є доказово тотальною, насправді є примітивно рекурсивною, тоді як арифметика Пеано доводить, що такі функції, як функція Акермана, які не є примітивно рекурсивними, є тотальними. Однак не кожна обчислювана функція є доказово тотальною в арифметиці Пеано; прикладом такої функції є теорема Гудштейна.

Назва

Галузь математичної логіки, що стосується обчислюваності та її узагальнень, з перших днів свого існування називалася «теорією рекурсії». Роберт І. Соаре, видатний дослідник у цій галузі, запропонував замість цього назвати цю галузь «теорією обчислюваності». Він стверджує, що термінологія Тюрінга, що використовує слово «обчислюваний», є більш природною та більш зрозумілою, ніж термінологія, що використовує слово «рекурсивний», яку ввів Кліні. Багато сучасних дослідників почали використовувати цю альтернативну термінологію. Ці дослідники також використовують таку термінологію, як частково обчислювана функція та обчислювано перелічувана множина замість часткова рекурсивна функція та рекурсивно перелічувана множина. Однак не всі дослідники були переконані, як пояснили Фортноу і Сімпсон. Деякі коментатори стверджують, що як «теорія рекурсії», так і «теорія обчислюваності» не можуть передати той факт, що більшість об'єктів, що вивчаються в теорії обчислюваності, не є обчислюваними.

Роджерс (1967) припустив, що ключовою властивістю теорії обчислюваності є те, що її результати та структури повинні бути інваріантними щодо обчислюваних бієкцій на натуральних числах (ця пропозиція спирається на ідеї програми Ерлангена в геометрії). Ідея полягає в тому, що обчислювана бієкція просто перейменовує числа в множині, а не вказує на будь-яку структуру в множині, так само як обертання евклідової площини не змінює жодного геометричного аспекту накреслених на ній ліній. Оскільки будь-які дві нескінченні обчислювані множини пов'язані обчислюваною бієкцією, ця пропозиція ототожнює всі нескінченні обчислювані множини (скінченні обчислювані множини розглядаються як тривіальні). Згідно з Роджерсом, множини, що представляють інтерес у теорії обчислюваності, — це необчислювані множини, розбиті на класи еквівалентності обчислюваними бієкціями натуральних чисел.

Професійні організації

Головною професійною організацією з теорії обчислюваності є Асоціація символічної логіки, яка щороку проводить кілька дослідницьких конференцій. Міждисциплінарна дослідницька асоціація Computability in Europe (CIE) також організовує серію щорічних конференцій.

Див. також

• Рекурсія (інформатика)
• Логіка обчислюваності
• Трансобчислювальна задача

Література

Тексти рівня бакалавріату

• Cooper, S.B. (2004). Computability Theory. Chapman & Hall/CRC. ISBN 1-58488-237-9.
• Cutland, N. (1980). Computability, An introduction to recursive function theory. Cambridge University Press. ISBN 0-521-29465-7.
• Matiyasevich, Y. (1993). Hilbert's Tenth Problem (English) . MIT Press. ISBN 0-262-13295-8.

Тексти для подальшого вивчення

• Jain, S.; Osherson, D.; Royer, J.; Sharma, A. (1999). Systems that learn, an introduction to learning theory (вид. 2nd). Bradford Book. ISBN 0-262-10077-0.
• Kleene, S. (1952). Introduction to Metamathematics. North-Holland. ISBN 0-7204-2103-9.
• Lerman, M. (1983). Degrees of unsolvability. Perspectives in Mathematical Logic. Springer-Verlag. ISBN 3-540-12155-2.
• Nies, Andre (2009). Computability and Randomness. Oxford University Press. ISBN 978-0-19-923076-1.
• Odifreddi, P. (1989). Classical Recursion Theory. North-Holland. ISBN 0-444-87295-7.
• Odifreddi, P. (1999). Classical Recursion Theory. Т. II. Elsevier. ISBN 0-444-50205-X.
• Rogers, Jr., H. (1987). The Theory of Recursive Functions and Effective Computability (вид. 2nd). MIT Press. ISBN 0-262-68052-1.
• Sacks, G. (1990). Higher Recursion Theory. Springer-Verlag. ISBN 3-540-19305-7.
• Simpson, S.G. (1999). Subsystems of Second Order Arithmetic. Springer-Verlag. ISBN 3-540-64882-8.
• Soare, R.I. (1987). Recursively Enumerable Sets and Degrees. Perspectives in Mathematical Logic. Springer-Verlag. ISBN 0-387-15299-7.

Оглядові документи та збірники

• Ambos-Spies, K.; Fejer, P. (2006). Degrees of Unsolvability (PDF). Архів оригіналу (PDF) за 20 квітня 2013. Процитовано 27 жовтня 2006. Неопублікований передрук.
• Enderton, H. (1977). Elements of Recursion Theory. У Barwise, J. (ред.). Handbook of Mathematical Logic. North-Holland. с. 527–566. ISBN 0-7204-2285-X.
• Ershov, Y.L.; Goncharov, S.S.; Nerode, A.; Remmel, J.B. (1998). Handbook of Recursive Mathematics. North-Holland. ISBN 0-7204-2285-X.
• Fairtlough, M.; Wainer, S.S. (1998). Hierarchies of Provably Recursive Functions. У Buss, S.R. (ред.). Handbook of Proof Theory. Elsevier. с. 149—208. ISBN 978-0-08-053318-6.
• Soare, R.I. (1996). Computability and recursion (PDF). Bulletin of Symbolic Logic. 2 (3): 284—321. doi:10.2307/420992. JSTOR 420992. S2CID 5894394.

Наукові праці та збірники

• Burgin, M.; Klinger, A. (2004). Experience, Generations, and Limits in Machine Learning. Theoretical Computer Science. 317 (1—3): 71—91. doi:10.1016/j.tcs.2003.12.005.
• Church, A. (1936). An unsolvable problem of elementary number theory. American Journal of Mathematics. 58 (2): 345—363. doi:10.2307/2371045. JSTOR 2371045.
• Church, A. (1936). A note on the Entscheidungsproblem. Journal of Symbolic Logic. 1 (1): 40—41. doi:10.2307/2269326. JSTOR 2269326.Передруковано в Davis, 1965.
• Davis, Martin, ред. (2004). The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions. Courier. ISBN 978-0-486-43228-1.
• Friedberg, R.M. (1958). Three theorems on recursive enumeration: I. Decomposition, II. Maximal Set, III. Enumeration without repetition. The Journal of Symbolic Logic. 23 (3): 309—316. doi:10.2307/2964290. JSTOR 2964290.
• Gold, E. Mark (1967). Language Identification in the Limit (PDF). Information and Control. 10 (5): 447—474. doi:10.1016/s0019-9958(67)91165-5.
• Harrington, L.; Soare, R.I. (1991). Post's Program and incomplete recursively enumerable sets. Proc. Natl. Acad. Sci. U.S.A. 88 (22): 10242—6. Bibcode:1991PNAS...8810242H. doi:10.1073/pnas.88.22.10242. PMC 52904. PMID 11607241.
• Jockusch jr, C.G. (1968). Semirecursive sets and positive reducibility. Trans. Amer. Math. Soc. 137 (2): 420—436. doi:10.1090/S0002-9947-1968-0220595-7. JSTOR 1994957.
• Kleene, S.C.; Post, E.L. (1954). The upper semi-lattice of degrees of recursive unsolvability. Annals of Mathematics. Second. 59 (3): 379—407. doi:10.2307/1969708. JSTOR 1969708.
• Moore, C. (1996). Recursion theory on the reals and continuous-time computation. Theoretical Computer Science. 162 (1): 23—44. doi:10.1016/0304-3975(95)00248-0.
• Myhill, J. (1956). The lattice of recursively enumerable sets. The Journal of Symbolic Logic. 21: 215—220. doi:10.1017/S002248120008525X.
• Orponen, P. (1997). A survey of continuous-time computation theory. Advances in Algorithms, Languages, and Complexity: 209—224. doi:10.1007/978-1-4613-3394-4_11. ISBN 978-1-4613-3396-8.
• Post, E. (1944). Recursively enumerable sets of positive integers and their decision problems. Bulletin of the American Mathematical Society. 50 (5): 284—316. doi:10.1090/S0002-9904-1944-08111-1. MR 0010514.
• Post, E. (1947). Recursive unsolvability of a problem of Thue. Journal of Symbolic Logic. 12 (1): 1—11. doi:10.2307/2267170. JSTOR 2267170. Передруковано в Davis, 1965.
• Shore, Richard A.; Slaman, Theodore A. (1999). Defining the Turing jump (PDF). Mathematical Research Letters. 6 (6): 711—722. doi:10.4310/mrl.1999.v6.n6.a10. MR 1739227.
• Slaman, T.; Woodin, W.H. (1986). Definability in the Turing degrees. Illinois J. Math. 30 (2): 320—334. doi:10.1215/ijm/1256044641. MR 0840131.
• Soare, R.I. (1974). Automorphisms of the lattice of recursively enumerable sets, Part I: Maximal sets. Annals of Mathematics. 100 (1): 80—120. doi:10.2307/1970842. JSTOR 1970842.
• Turing, A.M. (1938). On Computable Numbers, with an Application to the Entscheidungsproblem. A Correction. Proceedings of the London Mathematical Society. s2-43 (1): 544—6. doi:10.1112/plms/s2-43.6.544. Передруковано в Davis, 1965. PDF із comlab.ox.ac.uk
• Turing, A.M. (1939). Systems of logic based on ordinals. Proceedings of the London Mathematical Society. s2-45 (1): 161—228. doi:10.1112/plms/s2-45.1.161. {{cite journal}}: |hdl-access= вимагає |hdl= (довідка) Передруковано в Davis, 1965.

Посилання

• Домашня сторінка асоціації символічної логіки
• Домашня сторінка обчислюваності в Європі
• Веб-сторінка курсу теорії рекурсії на рівні магістратури з приблизно 100 сторінками конспектів лекцій
• Конспекти лекцій німецькою мовою з індуктивного висновку