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

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

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

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

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

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

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

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

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

Фундаментальні результати, отримані дослідниками, встановили обчислюваність за Тюрінгом як правильну формалізацію неформальної ідеї ефективного обчислення. Ці результати спонукали Стівена Кліні (1952) створити дві назви «теза Черча» і «теза Тюрінга». Нині їх часто розглядають як одну гіпотезу, тезу Черча-Тюрінга, яка стверджує, що будь-яка функція, обчислювана за допомогою алгоритму, є обчислюваною функцією. Хоча спочатку скептично налаштований, до 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) ввів кілька сильних зведень, названих так тому, що вони передбачають зведеність таблиці істинності. Машина Тюрінга, що реалізує сильну зведеність, обчислює повну функцію (total function) незалежно від того, який оракул вона представлена. Слабкі зведення — це ті, де процес зведення може не закінчитися для всіх оракулів; Одним із прикладів є зведення по Тюрінгу.

До сильних скорочень належать:

Багатозначне зведення (один до одного)

A є 1-зведеним до 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, тобто може бути відображений за допомогою багатозначного зведення до E (докладніше див. теорему Райса). Але багато з цих множин індексів навіть складніші, ніж проблема зупинки. Цей тип множин можна класифікувати за допомогою арифметичної ієрархії. Наприклад, множина індексів FIN класу всіх кінцевих множин знаходиться на рівні Σ₂, множина індексів REC класу всіх рекурсивних множин знаходиться на рівні Σ₃, множина індексів COFIN всіх скінченних множин також знаходиться на рівень Σ₃ та множина індексів COMP класу всіх повних множин Тюрінга Σ₄. Ці рівні ієрархії визначаються індуктивно, Σ_n+1 містить лише всі множини, які є пререраховувальними щодо Σ_n; Σ₁ містить пререраховувальні множини. Наведені тут множини індексів є повними для своїх рівнів, тобто всі множини на цих рівнях можуть бути багатозначно зведені (багато до одиного) до заданих множин індексів.

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

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

Нумерація

Нумерація — це перерахування функцій; він має два параметри, 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.[1]
• 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 сторінками конспектів лекцій
• Конспекти лекцій німецької мови з індуктивного висновку