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

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

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

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

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

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

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

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

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

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

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

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

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

Програма зворотної математики запитує, які аксіоми існування множин необхідні для доведення конкретних теорем математики в підсистемах арифметики другого порядку . Це дослідження було ініційоване Харві Фрідманом, а його детально вивчали Стівен Сімпсон та інші; Сімпсон (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 < м < n, для яких функцій A можна обчислити будь-які різні n входів x ₁ , х ₂ , ..., x _n кортеж із n чисел y ₁ ,y ₂ ,...,y _n таких, що принаймні m рівнянь A ( x _k ) = y _k є істинними. Такі множини відомі як ( m , n )-рекурсивні множини. Першим основним результатом у цій галузі теорії обчислюваності є результат Трахтенброта про те, що множина обчислювана, якщо вона є ( m , n )-рекурсивною для деяких m , н з 2м > п . З іншого боку, напіврекурсивні множини Джокуша (які вже були відомі неофіційно до того, як Джокуш представив їх у 1968 році) є прикладами множини, яка є ( m , n )-рекурсивною тоді і тільки тоді, коли 2 m < п + 1. Існує незліченна кількість цих множин, а також деякі перераховувальні, але необчислювані. Пізніше Дегтєв встановив ієрархію перераховувальних множин, які є (1, п + 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.
• 0-7204-2285-XCutland, N. (1980). Computability, An introduction to recursive function theory. Cambridge University Press. ISBN 0-521-29465-7.
• 0-7204-2285-XMatiyasevich, 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.
• 978-0-486-43228-1Nies, 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.
• 0-7204-2285-XErshov, Y.L.; Goncharov, S.S.; Nerode, A.; Remmel, J.B. (1998). Handbook of Recursive Mathematics. North-Holland. ISBN 0-7204-2285-X.
• 0-7204-2285-XFairtlough, 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.
• 978-0-08-053318-6Soare, 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 .
• 978-0-486-43228-1Davis, 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.
• 978-1-4613-3396-8Orponen, 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 сторінками конспектів лекцій
• Конспекти лекцій німецької мови з індуктивного висновку