Перегляд вихідного коду сторінки Теорія обчислюваності

{{For|Концепт обчислюваності|Обчислюваність}}
{| class="wikitable floatright"
!n
! width="30px" | 2
! width="30px" | 3
! width="30px" | 4
! width="50px" | 5
! width="120px" | 6
! width="120px" | 7
! width="30px" | . . .
|-
! Σ(''n'')
| align="center" | 4
| align="center" | 6
| align="center" | 13
| align="center" | {{Val|4098}} {{Кольоровий текст|#800000|?}}
| align="center" | > 3,5×10<sup>18267</sup>
| align="center" | {{Кольоровий текст|#800000|>}} 10<sup>10<sup>10<sup>10<sup>{{Val|18705353}}</sup></sup></sup></sup>
| align="center" | {{Кольоровий текст|#800000|?}}
|-
! colspan="8" |<small>Функція {{Нп|Зайнятий бобер|зайнятого бобра|en|Busy beaver}} Σ(''n'') зростає швидше ніж будь-яка обчислювана функція</small>

<small>Таким чином можна судити про її необчислюваність;<ref>{{cite journal|author=[[Tibor Radó]]|date=May 1962|title=On non-computable functions|url=https://archive.org/details/bstj41-3-877|journal=[[Bell System Technical Journal]]|volume=41|pages=877&ndash;884|doi=10.1002/j.1538-7305.1962.tb00480.x|number=3}}</ref> Вона розрахована лише частково.</small>
|}
{| class="wikitable floatright"
|}
'''Теорія обчислюваності''', також відома як '''теорія рекурсії''', є розділом [[Математична логіка|математичної логіки]], [[Інформатика|інформатики]] та [[Теорія алгоритмів|теорії обчислень]], що виникла в 1930-х роках з вивчення [[Обчислювана функція|обчислювальних функцій]] і [[Степінь Тюрінга|степенів Тюрінга]]. З тих пір ця сфера розширилася, включивши в себе вивчення узагальненої [[Обчислюваність|обчислюваності]] та {{Нп|Визначений набір|визначеності|en|Definable set}}. У цих областях теорія обчислюваності перетинається з [[Теорія доведення|теорією доказів]] та {{Нп|Ефективна описова теорія множин|ефективною описовою теорією множин|en|Effective descriptive set theory}}.

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

* Що означає обчислюваність [[Функція (математика)|функції]] над [[Натуральні числа|натуральними числами]]?
* Як можна класифікувати необчислювані функції в ієрархію на основі їхнього рівня не обчислюваності?

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

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

== Обчислювані та необчислювані множини ==
Теорія обчислюваності виникла в 1930-х роках завдяки роботам [[Курт Гедель|Курта Геделя]], [[Алонзо Черч]]а, [[Роза Петер|Рози Петер]], [[Алан Тюрінг|Алана Тюрінга]], [[Стівен Коул Кліні|Стівена Кліні]] та [[Еміль Пост|Еміля Поста]].<ref>Many of these foundational papers are collected in ''The Undecidable'' (1965) edited by [[Мартін Девіс|Martin Davis]].</ref><ref>{{Cite web|last=Soare|first=Robert Irving|title=Computability Theory and Applications: The Art of Classical Computability|url=http://www.people.cs.uchicago.edu/~soare/Turing/frontice.pdf|website=Department of Mathematics|publisher=University of Chicago|accessdate=23 серпня 2017|date=22 грудня 2011}}</ref>

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

: «''[[Альфред Тарський|Тарський]] підкреслив у своїй лекції (і я вважаю справедливо) велике значення концепції загальної рекурсивності (або обчислюваності за Тюрінгом). Мені здається, що ця важливість значною мірою пояснюється тим, що за допомогою цієї концепції вперше вдалося дати абсолютне поняття цікавому гносеологічному поняттю, тобто не залежному від обраного формалізму.''*»(Gödel 1946 у Davis 1965:84).<ref>The full paper can also be found at pages 150ff (with commentary by Charles Parsons at 144ff) in Feferman et al. editors 1990 ''Kurt Gödel Volume II Publications 1938—1974'', Oxford University Press, New York, {{ISBN|978-0-19-514721-6}}. Both reprintings have the following footnote * added to the Davis volume by Gödel in 1965: "To be more precise: a function of integers is computable in any formal system containing arithmetic if and only if it is computable in arithmetic, where a function ''f'' is called computable in ''S'' if there is in ''S'' a computable term representing ''f'' (p. 150).</ref>

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

Виявилося, що багато задач у математиці не можна вирішити після того, як були встановлені ці початкові приклади. У 1947 році [[Марков Андрій Андрійович (молодший)|Марков]] і Пост опублікували незалежні статті, які показали, що {{Нп|Словна задача для напівгруп|словесну проблему для напівгруп|en|Semi-Thue system}} неможливо ефективно вирішити. Розширюючи цей результат, {{Нп|Новіков Петро Сергійович|Петро Новіков|en|Pyotr Novikov}} та {{Нп|Вільям Бун (математик)|Вільям Бун|en|William Boone (mathematician)}} незалежно показали в 1950-х роках, що {{Нп|проблема слова для груп||en|Word problem for groups}} не є ефективно розв'язаною: не існує ефективної процедури, яка б, задавши слово в скінченно представленій [[Група (математика)|групі]], вирішила, чи елемент, представлений словом, є [[Нейтральний елемент|нейтральним елементом]] групи. У 1970 році [[Матіясевич Юрій Володимирович|Юрій Матіясевич]] довів (за допомогою результатів [[Джулія Робінсон|Джулії Робінсон]]) {{Нп|Теорема Матіясевича|теорему Матіясевича|en|Diophantine_set#Matiyasevich's_theorem}}, з якої випливає, що {{Нп|Десята задача Гільберта|десята задача Гільберта|en|Hilbert's tenth problem}} не має ефективного рішення; Ця проблема ставила питання про існування ефективної процедури, яка з'ясовує чи має [[Діофантові рівняння|діофантове рівняння]] над цілими числами розв'язок у цілих числах. {{Нп|Список алгоритмічно нерозв'язних задач|||List of undecidable problems}} надає додаткові приклади задач без обчислювального розв'язку.

Вивчення того, які математичні конструкції можна ефективно виконувати, іноді називають '''рекурсивною математикою'''; ''Довідник з рекурсивної математики'' (Ershov ''et al.'' 1998) охоплює багато відомих результатів у цій галузі.

== Обчислюваність за Тюрінгом ==
Основна форма обчислюваності, що вивчається в теорії обчислюваності, була введена Тюрінгом (1936). Множина натуральних чисел називається ''[[Рекурсивна множина|обчислюваною множиною]]'' (також званою ''розв'язуваною'', ''рекурсивною'' або ''обчислюваною множиною за Тюрінгом''), якщо існує [[машина Тюрінга]], яка приймаючи число '''''n''''' зупиняється з виходом '''1''', якщо '''''n''''' знаходиться в множині, і зупиняється. з виходом '''0''', якщо '''''n''''' не входить у набір. Функція '''''f''''' від натуральних чисел до натуральних чисел є ''[[Обчислювана функція|обчислювальною]] (Тюрінгом)'' або ''обчислюваною функцією'', якщо існує машина Тюрінга, яка на прийнявши на вхід '''''n''''' зупиняється та повертає '''''f'' (''n'')'''. Використання машин Тюрінга тут не є необхідним; є багато інших [[Модель обчислення|моделей обчислень]], які мають таку ж обчислювальну потужність, що й машини Тюрінга; наприклад, [[Мю-рекурсивна функція|µ-рекурсивні функції]], отримані з примітивної рекурсії, і µ-оператора.

Термінологія обчислювальних функцій і множин не повністю стандартизована. Визначення в термінах μ-рекурсивних функцій, а також інше визначення ''обчислюваних'' функцій Геделем привели до традиційної назви ''обчислюваних'' для множин і функцій, обчислюваних машиною Тюрінга. Слово ''вирішуваний'' походить від німецького слова ''Entscheidungsproblem'', яке використовувалося в оригінальних роботах Тюрінга та інших. У сучасному вживанні термін «обчислювана функція» має різні визначення: згідно з Катлендом (1980), це часткова рекурсивна функція (яка може бути невизначеною для деяких вхідних даних), тоді як відповідно до Соаре (1987) вона є повністю рекурсивною (еквівалентно, загальна рекурсивна) функція. Ця стаття відповідає другому з цих умов. Соаре (1996) дає додаткові коментарі щодо термінології.

Не кожен набір натуральних чисел обчислюється. Проблема [[Проблема зупинки|зупинки]], яка являє собою набір (описів) машин Тюрінга, які зупиняються на вході '''0''', є добре відомим прикладом необчислюваної множини. Існування багатьох не обчислюваних множин випливає з того факту, що існує лише [[Зліченна множина|зліченна кількість]] машин Тюрінга, а отже, лише зліченна кількість обчислювальних множин, але згідно [[Теорема Кантора|з теоремою Кантора]] існує [[Незліченна множина|незліченна кількість]] множин натуральних чисел.

Хоча проблема зупинки не обчислюється, можна змоделювати виконання програми та створити нескінченний список програм, які зупиняються. Таким чином, проблема зупинки є прикладом ''{{Нп|Рекурсивно перераховна множина|перераховуваної множини|en|Computably enumerable}}'', яка являє собою множину, яку можна перерахувати машиною Тюрінга (інші терміни для ''перераховуваної'' множини включають ''рекурсивно перераховані'' та ''напіввирішуваний''). Еквівалентно, множина є ''перераховуваною'' [[Тоді й лише тоді|тоді і тільки тоді]], коли вона є діапазоном деякої обчислювальної функції. Множини, хоча і не розв'язні в цілому, були детально вивчені в теорії обчислюваності.

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

=== Відносна обчислюваність і степені Тюрінга ===
Теорія обчислюваності в математичній логіці традиційно зосереджується на ''відносній обчислюваності'', узагальненні обчислюваності за Тюрінгом, визначеній за допомогою [[Пророча машина|оракульних машин Тюрінга]], введеної Тюрінгом (1939). Машина Тюрінга оракула&nbsp;— це гіпотетичний пристрій, який, крім виконання дій звичайної машини Тюрінга, здатний задавати питання ''оракулу'', який є певною множиною натуральних чисел. Машина оракула може задавати лише запитання виду «Чи є ''n'' у множині оракула?». На кожне запитання буде негайно дано правильну відповідь, навіть якщо набір оракула не обчислюється. Таким чином, машина оракула з невичислимим оракулом зможе обчислювати множини, які машина Тюрінга без оракула не може.

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

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

# Їх можна обчислити, і
# Кожне з них можна перевести в будь-який інший за допомогою [[Багатозначна зводимість|багатозначної зводимості]]. Тобто для таких множин ''A'' і ''B'' існує повна обчислювана функція ''f'' така, що ''A'' = {''x'': ''f''(''x'') ∈ ''B''}. Ці множини називаються ''еквівалентними багато-одного'' (або ''m-еквівалентними'').

Багатозначна зводимість «сильніше», ніж скорочення Тюрінга: якщо множина ''A'' зводиться до множини ''B'', то ''A'' є зведеною за Тюрінгом до ''B'', але зворотне не завжди виконується. Хоча природні приклади необчислюваних множин є еквівалентними багатозначним, можна побудувати обчислювані множини ''A'' і ''B'' так, що ''A'' зводиться за Тюрінгом до ''B'', але не зводиться багаозначно до ''B.'' Можна показати, що кожна обчислювально перераховувана множина зводиться багатозначно, а потім і до проблеми зупинки, отже, проблема зупинки є найскладнішою обчислювальною множиною, яка може бути перерахована враховуючи багатозначну зводимість і зводимість за Тюрінгом. Пост (1944) запитав, чи ''кожна'' обчислювано перераховувана множина обчислювана або [[Степінь Тюрінга|еквівалентна за Тюрінгом]] до задачі зупинки, тобто чи не існує перераховувальної множини з проміжним степенем Тюрінга між цими двома.

Як проміжні результати Пост визначив природні типи перераховуваних множин, таких як прості, гіперпрості та гіпергіперпрості множини. Пост показав, що ці множини знаходяться строго між обчислювальними множинами і проблемою зупинки щодо багатозначної зводності. Пост також показав, що деякі з них є строго проміжними за іншими поняттями зводимості, більш сильними, ніж звідність по Тюрінгу. Але Пост залишив відкритою головну проблему існування перераховуваних множин проміжного степеня Тюрінга; ця проблема стала відома як ''[[Степінь Тюрінга|проблема Поста]]''. Через десять років, (в 1954 році) Кліні і Пост показали, що існують проміжні степені Тюрінга між множинами, що обчислюються, і проблемою зупинки, але їм не вдалося показати, що жодна з цих степенів містить перераховувану множину. Дуже скоро після цього Фрідберг і Мухнік незалежно вирішили проблему Поста, встановивши існування перераховувальних множин проміжного степеня. Цей новаторський результат відкрив широке вивчення степенів Тюрінга перераховуваних множин, які, як виявилося, мають дуже складну і нетривіальну структуру.

Існує незліченно багато множин, які неможливо перерахувати, і дослідження степенів Тюрінга всіх множин є таким же центральним у теорії обчислюваності, як дослідження перераховуваних степенів Тюрінга. Було побудовано багато степенів зі спеціальними властивостями: ''гіперімунні степені'', де кожна обчислювана відносно цього степеня функція мажорується (нерелятивізованою) обчислюваною функцією; ''високі степені'', щодо яких можна обчислити функцію ''f'', яка домінує над кожною обчислюваною функцією ''g'' у тому сенсі, що існує константа ''c'', що залежить від ''g'', така, що ''g(x) < f(x)'' для всіх ''x > c''; ''випадкові степені'', що містять {{Нп|Алгоритмічно випадкова послідовність|алгоритмічно випадкові множини|en|Algorithmically random sequence}}; ''1-родові'' степені 1-родових множин; і градуси нижче проблеми зупинки {{Нп|Обмеження обчислюваності|гранично обчислювальних|en|Computation in the limit}} множин.

Вивчення довільних (не обов'язково перераховуваних) степенів Тюрінга включає вивчення стрибка Тюрінга. Для множини ''A'' ''{{Нп|стрибок Тюрінга||en|Turing jump}}'' ''A''&nbsp;— це набір натуральних чисел, що кодують рішення проблеми зупинки для машин оракула Тюрінга, що працюють з оракулом ''A.'' Стрибок Тюрінга будь-якої множини завжди має вищий степінь Тюрінга, ніж вихідна множина, і теорема Фрідбурга показує, що будь-яку множину, яка обчислює проблему зупинки, можна отримати як стрибок Тюрінга іншої множини. [[Критерій Поста|Теорема Поста]] встановлює тісний зв'язок між операцією стрибка Тюрінга та {{Нп|Арифметична ієрархія|арифметичною ієрархією|en|Arithmetical hierarchy}}, яка є класифікацією певних підмножин натуральних чисел на основі їх визначеності в арифметиці.

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

=== Інші зведення ===
Нинішня область досліджень у теорії обчислюваності вивчає відношення зводимості, відмінні від зводимості за Тюрінгом. Пост (1944) ввів кілька ''сильних зведень'', названих так тому, що вони передбачають зведеність [[таблиці істинності]]. Машина Тюрінга, що реалізує сильну зведеність, обчислює повну функцію ''(total function)'' незалежно від того, який оракул вона представлена. ''Слабкі'' зведення&nbsp;— це ті, де процес зведення може не закінчитися для всіх оракулів; Одним із прикладів є зведення по Тюрінгу.

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

; [[Багатозначна зводимість|Багатозначне зведення (один до одного)]]
: ''A'' є ''1-зведеним'' до ''B'', якщо існує повна обчислювана [[Ін'єкція (математика)|ін'єкційна функція]] ''f'' така, що кожне ''n'' знаходиться в ''A'' тоді й тільки тоді, коли ''f''(''n'') знаходиться в ''B.''
; [[Багатозначна зводимість|Багатозначне зведення (багато до одного)]]: Це, по суті, зведеність один до одного без обмеження, що ''f'' є ін'єкційним. ''A'' є ''множинним зведеним'' (або ''m-зведеним'') до ''B'', якщо існує повна обчислювана функція ''f'' така, що кожне ''n'' знаходиться в ''A'' тоді і тільки тоді, коли ''f''(''n'') знаходиться в ''B.''
; {{Нп|Зводимість таблиці істини|Зводимість таблиці істинності|en|Truth-table reduction}}
: ''A'' є зведеною до ''B'', якщо ''A'' є зведеною за Тюрінгом до ''B'' за допомогою оракула-машини Тюрінга, яка обчислює повну функцію незалежно від того, який оракул їй заданий. Через компактність {{Нп|Канторівський простір|простору Кантора|en|Cantor space}} це еквівалентно тому, що зведення одночасно представляє оракулу єдиний список запитань (залежно від вхідних даних), а потім, побачивши їх відповіді, може створити вихідні дані, не задаючи додаткових запитань незалежно від відповідей оракула на початкові запити. Зводимість таблиці істинності також широко досліджена.

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

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

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

=== Теорема Райса та арифметична ієрархія ===
Райс показав, що для кожного нетривіального класу ''C'' (який містить деякі, але не всі перераховувані множини) [[Індексна множина|індексний]] набір ''E'' = {''e'': ''e''-та перераховувані множина ''W<sub>e</sub>'' знаходиться в ''C''} має властивість, що або [[Проблема зупинки|проблема зупинки,]] або її доповнення є багатозначно зведеним до ''E'', тобто може бути відображений за допомогою [[Багатозначна зводимість|багатозначного зведення]] до ''E'' (докладніше див. {{Нп|Теорема Райса|теорему Райса|en|Rice's theorem}}). Але багато з цих множин індексів навіть складніші, ніж проблема зупинки. Цей тип множин можна класифікувати за допомогою {{Нп|Арифметична ієрархія|арифметичної ієрархії|en|Arithmetical hierarchy}}. Наприклад, множина індексів FIN класу всіх кінцевих множин знаходиться на рівні Σ<sub>2</sub>, множина індексів REC класу всіх рекурсивних множин знаходиться на рівні Σ<sub>3</sub>, множина індексів COFIN всіх скінченних множин також знаходиться на рівень Σ<sub>3</sub> та множина індексів COMP класу всіх повних множин Тюрінга Σ<sub>4</sub>. Ці рівні ієрархії визначаються індуктивно, Σ<sub>''n''+1</sub> містить лише всі множини, які є пререраховувальними щодо Σ<sub>''n''</sub>; Σ<sub>1</sub> містить пререраховувальні множини. Наведені тут множини індексів є повними для своїх рівнів, тобто всі множини на цих рівнях можуть бути багатозначно зведені (багато до одиного) до заданих множин індексів.

=== Зворотна математика ===
Програма ''{{Нп|Зворотна математика|зворотної математики|en|Reverse mathematics}}'' запитує, які аксіоми існування множин необхідні для доведення конкретних теорем математики в підсистемах {{Нп|Арифметика другого порядку|арифметики другого порядку|en|Second-order arithmetic}}. Це дослідження було ініційоване {{Нп|Харві Фрідман|Харві Фрідманом|en|Harvey Friedman}}, а його детально вивчали {{Нп|Стів Сімпсон (математик)|Стівен Сімпсон|en|Steve Simpson (mathematician)}} та інші; Сімпсон дає детальне обговорення програми. Аксіоми існування множин, про які йде мова, неформально відповідають аксіомам, які кажуть, що [[Булеан|множина степенів]] натуральних чисел закрита відповідно до різних уявлень про зведення. Найслабшою такою аксіомою, що вивчається у зворотній математиці, є ''рекурсивне розуміння'', яке стверджує, що множина степенів натуральних чисел замкнута відповідно до зведеності за Тюрінгом.

=== Нумерація ===
Нумерація&nbsp;— це перерахування функцій; він має два параметри, ''e'' і ''x'', і виводить значення ''e''-ї функції в нумерації ''x,'' що подаються на вхід. Нумерація може бути частково обчислюваною, хоча деякі її члени є повністю обчислюваними функціями. {{Нп|Допустима нумерація|Допустимі нумерації|en|Admissible numbering}}&nbsp;— це нумерації, на які можна перевести всі інші. {{Нп|Нумерація Фрідберга|Нумерація Фрідберга|en|Friedberg numbering}} (названа на честь її першовідкривача)&nbsp;— це нумерація всіх частково обчислюваних функцій. Пізніші дослідження також стосувалися нумерації інших класів, наприклад класів перерераховувальних множин. Гончаров відкрив, наприклад, клас пререраховувальних множин, для яких нумерації поділяються точно на два класи відносно обчислювальних ізоморфізмів.

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

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

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

=== Проблеми автоморфізму ===
Іншим важливим питанням є існування автоморфізмів у теоретико-обчислювальних структурах. Однією з цих структур є одна з пререраховувальних множин включенні за модулем [[Скінченні різниці|скінченної різниці]]; у цій структурі ''A'' знаходиться нижче ''B'' тоді і тільки тоді, коли встановлена різниця ''B'' − ''A'' є кінцевим. {{Нп|Максимальна множина|Максимальні множини|en|Maximal set}} (як визначено в попередньому абзаці) мають властивість, що вони не можуть бути автоморфними до немаксимальних множин, тобто якщо існує автоморфізм пререраховувальних множин у щойно згаданій структурі, тоді кожна максимальна множина відображається на іншу максимальну множину. Соаре (1974) показав, що буває і зворотне, тобто кожні дві максимальні множини є автоморфними. Отже, максимальні множини утворюють орбіту, тобто кожен автоморфізм зберігає максимальність і будь-які дві максимальні множини перетворюються одна в одну за допомогою деякого автоморфізму. Харрінгтон навів ще один приклад автоморфної властивості: властивість творчих множин, множин, які є багатозначно (багато-один) еквівалентними задачі зупинки.

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

=== Колмогоровська складність ===
{{Main|Колмогоровська складність}}
Область [[Колмогоровська складність|колмогоровської складності]] та алгоритмічної випадковості була розроблена протягом 1960-х і 1970-х років Чайтіним, Колмогоровим, Левіним, Мартін-Льофом і Соломоновим (імена наведені тут в алфавітному порядку; значна частина досліджень була незалежною, а єдність концепції випадковості в той час не було зрозуміло). Основна ідея полягає в тому, щоб розглянути [[Універсальна машина Тюрінга|універсальну машину Тюрінга]] ''U'' і виміряти складність числа (або рядка) ''x'' як довжину найкоротшого входу ''p'' так, що ''U'' (''p'') виводить ''x''. Цей підхід революціонізував попередні способи визначення того, коли нескінченна послідовність (еквівалентно, характеристична функція підмножини натуральних чисел) є випадковою чи ні, використовуючи поняття випадковості для кінцевих об'єктів. Колмогоровська складність стала не тільки предметом самостійного вивчення, але й стала застосовуватися до інших предметів як інструмент для отримання доказів. У цій сфері залишається багато відкритих проблем. З цієї причини в січні 2007 року відбулася дослідницька конференція в цій галузі, а список відкритих проблем<ref>[http://www.cs.auckland.ac.nz/~nies/ The homepage] of Andre Nies has a list of open problems in Kolmogorov complexity</ref> ведуть Джозеф Міллер та Андре Ніс.

=== Розрахунок частоти ===
Ця галузь теорії обчислюваності аналізувала таке питання: для фіксованих ''m'' і ''n'' де 0&nbsp;<&nbsp;''m''&nbsp;<&nbsp;''n'', для яких функцій ''A'' можна обчислити будь-які різні ''n'' входів ''x''<sub>1</sub>,&nbsp;''x''<sub>2</sub>,&nbsp;…,&nbsp;''x<sub>n</sub>'' кортеж із ''n'' чисел ''y<sub>1</sub>, y<sub>2</sub>,…,y<sub>n</sub>'' таких, що принаймні ''m'' рівнянь ''A''(''x<sub>k</sub>'') = ''y<sub>k</sub>'' є істинними. Такі множини відомі як (''m'',&nbsp;''n'')-рекурсивні множини. Першим основним результатом у цій галузі теорії обчислюваності є результат Трахтенброта про те, що множина обчислювана, якщо вона є (''m'',&nbsp;''n'')-рекурсивною для деяких ''m'',&nbsp;''n'' з 2''m''&nbsp;&gt;&nbsp;''n''. З іншого боку, напіврекурсивні множини Джокуша (які вже були відомі неофіційно до того, як Джокуш представив їх у 1968 році) є прикладами множини, яка є (''m'',&nbsp;''n'')-рекурсивною тоді і тільки тоді, коли 2''m''&nbsp;<&nbsp;''n''&nbsp;+&nbsp;1. Існує незліченна кількість цих множин, а також деякі перераховувані, але необчислювані. Пізніше Дегтєв встановив ієрархію перераховуваних множин, які є (1,&nbsp;''n''&nbsp;+&nbsp;1)-рекурсивними, але не (1,&nbsp;''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 році.

=== Узагальнення обчислюваності за Тюрінгом ===
Теорія обчислюваності включає вивчення узагальнених понять цієї області, таких як арифметична зводимість, {{Нп|Гіперарифметична теорія|гіперарифметична звідність|en|Hyperarithmetical_theory#Relativized_hyperarithmeticity_and_hyperdegrees}} і {{Нп|Теорія α-рекурсії|теорія α-рекурсії|en|Alpha recursion theory}}, як описано Саксом (1990). Ці узагальнені поняття включають зводимості, які не можуть бути виконані машинами Тюрінга, але, тим не менш, є узагальненнями зведеності Тюрінга. Ці дослідження включають підходи до дослідження {{Нп|Аналітична ієрархія|аналітичної ієрархії|en|Analytical hierarchy}}, яка відрізняється від арифметичної, дозволяючи кількісно оцінювати набори натуральних чисел на додаток до кількісної оцінки окремих чисел. Ці області пов'язані з теоріями сильного впорядкування і дерев; наприклад, множина усіх індексів обчислюваних (небінарних) дерев без нескінченних розгалужень повний для рівня <math>\Pi^1_1</math> аналітичної ієрархії. У галузі {{Нп|Ефективна описова теорія множин|ефективної описової теорії множин|en|Effective descriptive set theory}} важливі як зводимість за Тюрінгом, так і гіперарифметична. Ще більш загальне поняття степенів конструктивності вивчається в [[Теорія множин|теорії множин]].

=== Теорія неперервної обчислюваності ===
Теорія обчислюваності для цифрових обчислень добре розроблена. Теорія обчислюваності менш добре розроблена для [[Аналогова обчислювальна машина|аналогових обчислень]], які відбуваються в [[Аналогова обчислювальна машина|аналогових комп'ютерах]], обробці аналогових сигналів, [[Аналогова електроніка|аналоговій електроніці]], [[Штучна нейронна мережа|нейронних мережах]] і безперервної [[Теорія керування|теорії керування]], змодельованої [[Диференціальні рівняння|диференціальними рівняннями]] та безперервними [[Динамічна система|динамічними системами]].

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

Теорія обчислюваності також пов'язана з {{Нп|Арифметика другого порядку|арифметикою другого порядку|en|Second-order arithmetic}}, формальною теорією натуральних чисел і множин натуральних чисел. Той факт, що певні множини обчислювані або відносно обчислювані, часто означає, що ці множини можна визначити в слабких підсистемах арифметики другого порядку. Програма зворотної математики використовує ці підсистеми для вимірювання невичислимості, властивої добре відомим математичним теоремам. Сімпсон&nbsp;(1999) обговорює багато аспектів арифметики другого порядку та зворотної математики.

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

== Назва ==
Область математичної логіки, що стосується обчислюваності та її узагальнень, з перших днів її існування називалася «теорією рекурсії». {{Нп|Роберт І. Соаре|Роберт І. Соаре|en|Robert I. Soare}}, видатний дослідник у цій галузі, запропонував замість цього назвати цю область «теорією обчислюваності». Він стверджує, що термінологія Тюрінга, що використовує слово «обчислювальний», є більш природною та більш зрозумілою, ніж термінологія, що використовує слово «рекурсивний» яку ввів Кліні. Багато сучасних дослідників почали використовувати цю альтернативну термінологію.<ref>[[MathSciNet]] searches for the titles like «computably enumerable» and «c.e.» show that many papers have been published with this terminology as well as with the other one.</ref> Ці дослідники також використовують таку термінологію, як ''частково обчислювана функція'' та ''перераховувана множина'' замість ''часткової рекурсивної функції'' та ''рекурсивно перераховуваної'' ''множини''. Однак не всі дослідники були переконані, як пояснили Фортноу<ref>Lance Fortnow, "[https://blog.computationalcomplexity.org/2004/02/is-it-recursive-computable-or.html Is it Recursive, Computable or Decidable?], " 2004-2-15, accessed 2018-3-22.</ref> і Сімпсон.<ref>[[Steve Simpson (mathematician)|Stephen G. Simpson]], "[http://www.cs.nyu.edu/pipermail/fom/1998-August/001993.html What is computability theory?], " FOM email list, 1998-8-24, accessed 2006-1-9.</ref> Деякі коментатори стверджують, що як ''теорія рекурсії, так і теорія'' ''обчислюваності'' не можуть передати той факт, що більшість об'єктів, що вивчаються в теорії обчислюваності, не є обчислювальними.<ref>Harvey Friedman, "[http://www.cs.nyu.edu/pipermail/fom/1998-August/002017.html Renaming recursion theory], " FOM email list, 1998-8-28, accessed 2006-1-9.</ref>

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

== Професійні організації ==
Головною професійною організацією з теорії обчислюваності є ''[[Асоціація символьної логіки|Асоціація символічної логіки]]'', яка щороку проводить кілька дослідницьких конференцій. Міждисциплінарна дослідницька асоціація ''{{Нп|Обчислювальність в Європі (CIE)|Computability in Europe|en|Computability in Europe}}'' (''CIE'') також організовує серію щорічних конференцій.
{{Портал|Філософія}}

== Див. також ==
* [[Рекурсія (програмування)|Рекурсія (інформатика)]]
* {{Нп|Логіка обчислюваності|Логіка обчислюваності|en|Computability logic}}
* {{Нп|Трансобчислювальна задача|Трансобчислювальна задача|en|Transcomputational problem}}

== Примітки ==
{{Reflist}}

== Посилання ==

; ''Тексти рівня бакалавриата''
;* {{cite book
|title=Computability Theory
|last=Cooper
|first=S.B.
|year=2004
|publisher=Chapman & Hall/CRC
|isbn=1-58488-237-9
|author-link=S. Barry Cooper
}}
;* <bdi></bdi>{{cite book
|url=https://archive.org/details/computabilityint0000cutl
|title=Computability, An introduction to recursive function theory
|last=Cutland
|first=N.
|year=1980
|publisher=Cambridge University Press
|isbn=0-521-29465-7
|url-access=registration
}}
;* <bdi></bdi>{{cite book
|title=Hilbert's Tenth Problem
|url=https://archive.org/details/hilbertstenthpro0000mati
|last=Matiyasevich
|first=Y.
|year=1993
|publisher=MIT Press
|language=English
|isbn=0-262-13295-8
|author-link=Матіясевич Юрій Володимирович
}}

; ''Тексти для подальшого вивчення''
:* {{cite book
|title=Systems that learn, an introduction to learning theory
|last1=Jain
|first1=S.
|last2=Osherson
|first2=D.
|last3=Royer
|first3=J.
|last4=Sharma
|first4=A.
|year=1999
|publisher=Bradford Book
|edition=2nd
|isbn=0-262-10077-0
}}
:* {{cite book
|title=Introduction to Metamathematics
|last=Kleene
|first=S.
|year=1952
|publisher=North-Holland
|isbn=0-7204-2103-9
|author-link=Stephen Kleene
}}
:* {{cite book
|title=Degrees of unsolvability
|url=https://archive.org/details/degreesofunsolva0000lerm
|last=Lerman
|first=M.
|year=1983
|series=Perspectives in Mathematical Logic
|publisher=Springer-Verlag
|isbn=3-540-12155-2
}}
:* <bdi></bdi>{{cite book
|title=Computability and Randomness
|last=Nies
|first=Andre
|year=2009
|publisher=Oxford University Press
|isbn=978-0-19-923076-1
}}
:* {{cite book
|url=https://archive.org/details/classicalrecursi0000odif
|title=Classical Recursion Theory
|last=Odifreddi
|first=P.
|year=1989
|publisher=North-Holland
|isbn=0-444-87295-7
|author-link=Piergiorgio Odifreddi
|url-access=registration
}}
:* {{cite book
|title=Classical Recursion Theory
|last=Odifreddi
|first=P.
|year=1999
|publisher=Elsevier
|volume=II
|isbn=0-444-50205-X
}}
:* {{cite book
|title=The Theory of Recursive Functions and Effective Computability
|last=Rogers, Jr.
|first=H.
|year=1987
|publisher=MIT Press
|edition=2nd
|isbn=0-262-68052-1
|author-link=Hartley Rogers, Jr.
}}
:* {{cite book
|url=https://archive.org/details/higherrecursiont0000sack
|title=Higher Recursion Theory
|last=Sacks
|first=G.
|year=1990
|publisher=Springer-Verlag
|isbn=3-540-19305-7
|url-access=registration
}}
:* {{cite book
|title=Subsystems of Second Order Arithmetic
|last=Simpson
|first=S.G.
|year=1999
|publisher=Springer-Verlag
|isbn=3-540-64882-8
|author-link=Steve Simpson (mathematician)
}}
:* {{cite book
|title=Recursively Enumerable Sets and Degrees
|last=Soare
|first=R.I.
|year=1987
|series=Perspectives in Mathematical Logic
|publisher=Springer-Verlag
|isbn=0-387-15299-7
}}

; ''Оглядові документи та збірники''
:* {{cite web|first1=K.|last1=Ambos-Spies|first2=P.|last2=Fejer|title=Degrees of Unsolvability|date=2006|url=http://www.cs.umb.edu/~fejer/articles/History_of_Degrees.pdf|access-date=2006-10-27|archive-url=https://web.archive.org/web/20130420184948/http://www.cs.umb.edu/~fejer/articles/History_of_Degrees.pdf|archive-date=2013-04-20|url-status=dead}} Неопублікований передрук.
:* {{cite book
|title=Handbook of Mathematical Logic
|last=Enderton
|first=H.
|year=1977
|editor-last=Barwise
|editor-first=J.
|editor-link=Jon Barwise
|publisher=North-Holland
|pages=[https://archive.org/details/handbookofmathem0090unse/page/527 527–566]
|chapter=Elements of Recursion Theory
|isbn=0-7204-2285-X
|chapter-url=https://archive.org/details/handbookofmathem0090unse/page/527
}}
:* <bdi></bdi>{{cite book
|title=Handbook of Recursive Mathematics
|last1=Ershov
|first1=Y.L.
|last2=Goncharov
|first2=S.S.
|last3=Nerode
|first3=A.
|last4=Remmel
|first4=J.B.
|year=1998
|publisher=North-Holland
|isbn=0-7204-2285-X
}}
:* <bdi></bdi>{{cite book
|title=Handbook of Proof Theory
|last1=Fairtlough
|first1=M.
|last2=Wainer
|first2=S.S.
|date=1998
|editor-last=Buss
|editor-first=S.R.
|publisher=Elsevier
|pages=149–208
|chapter=Hierarchies of Provably Recursive Functions
|isbn=978-0-08-053318-6
|chapter-url=https://books.google.com/books?id=MfTMDeCq7ukC&pg=PA149
}}
:* <bdi></bdi>{{cite journal|last=Soare|first=R.I.|year=1996|title=Computability and recursion|url=http://www.people.cs.uchicago.edu/~soare/History/compute.pdf|journal=Bulletin of Symbolic Logic|volume=2|issue=3|pages=284–321|doi=10.2307/420992|jstor=420992|s2cid=5894394}}

; Наукові праці та збірники
:* {{cite journal|last1=Burgin|first1=M.|last2=Klinger|first2=A.|year=2004|title=Experience, Generations, and Limits in Machine Learning|journal=Theoretical Computer Science|volume=317|issue=1–3|pages=71–91|doi=10.1016/j.tcs.2003.12.005|doi-access=free}}
:* {{cite journal|last=Church|first=A.|year=1936|title=An unsolvable problem of elementary number theory|url=https://archive.org/details/sim_american-journal-of-mathematics_1936-04_58_2/page/345|journal=American Journal of Mathematics|volume=58|issue=2|pages=345–363|doi=10.2307/2371045|jstor=2371045}}
:* {{cite journal|last=Church|first=A.|year=1936|title=A note on the Entscheidungsproblem|journal=Journal of Symbolic Logic|volume=1|issue=1|pages=40–41|doi=10.2307/2269326|jstor=2269326}}Передруковано в {{Harvnb|Davis|1965}}.
:* <bdi></bdi>{{cite book
|url=https://books.google.com/books?id=qW8x7sQ4JXgC
|title=The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions
|date=2004
|editor-last=Davis
|editor-first=Martin
|publisher=Courier
|isbn=978-0-486-43228-1
|ref={{harvid|Davis|1965}}
}}
:* {{cite journal|last=Friedberg|first=R.M.|year=1958|title=Three theorems on recursive enumeration: I. Decomposition, II. Maximal Set, III. Enumeration without repetition|journal=The Journal of Symbolic Logic|volume=23|issue=3|pages=309–316|doi=10.2307/2964290|jstor=2964290}}
:* {{Cite journal|last=Gold|first=E. Mark|year=1967|title=Language Identification in the Limit|url=http://web.mit.edu/~6.863/www/spring2009/readings/gold67limit.pdf|journal=[[Information and Control]]|volume=10|issue=5|pages=447–474|doi=10.1016/s0019-9958(67)91165-5|doi-access=free}}[https://web.archive.org/web/20090125120159/http://www.isrl.uiuc.edu/~amag/langev/paper/gold67limit.html]
:* {{cite journal|last1=Harrington|first1=L.|last2=Soare|first2=R.I.|year=1991|title=Post's Program and incomplete recursively enumerable sets|journal=Proc. Natl. Acad. Sci. U.S.A.|volume=88|issue=22|pages=10242–6|bibcode=1991PNAS...8810242H|doi=10.1073/pnas.88.22.10242|pmc=52904|pmid=11607241|doi-access=free}}
:* {{cite journal|last=Jockusch jr|first=C.G.|year=1968|title=Semirecursive sets and positive reducibility|journal=Trans. Amer. Math. Soc.|volume=137|issue=2|pages=420–436|doi=10.1090/S0002-9947-1968-0220595-7|jstor=1994957|doi-access=free}}
:* {{cite journal|last1=Kleene|first1=S.C.|last2=Post|first2=E.L.|year=1954|title=The upper semi-lattice of degrees of recursive unsolvability.|journal=Annals of Mathematics|series=Second|volume=59|issue=3|pages=379–407|doi=10.2307/1969708|jstor=1969708}}
:* {{cite journal|last=Moore|first=C.|author-link=Cris Moore|year=1996|title=Recursion theory on the reals and continuous-time computation|journal=Theoretical Computer Science|volume=162|issue=1|pages=23–44|doi=10.1016/0304-3975(95)00248-0}}
:* {{cite journal|last=Myhill|first=J.|year=1956|title=The lattice of recursively enumerable sets|journal=The Journal of Symbolic Logic|volume=21|pages=215–220|doi=10.1017/S002248120008525X}}
:* <bdi></bdi>{{cite journal|last=Orponen|first=P.|year=1997|title=A survey of continuous-time computation theory|journal=Advances in Algorithms, Languages, and Complexity|pages=209–224|doi=10.1007/978-1-4613-3394-4_11|isbn=978-1-4613-3396-8}}
:* {{cite journal|last=Post|first=E.|year=1944|title=Recursively enumerable sets of positive integers and their decision problems|journal=Bulletin of the American Mathematical Society|volume=50|issue=5|pages=284–316|doi=10.1090/S0002-9904-1944-08111-1|mr=0010514|doi-access=free}}
:* {{cite journal|last=Post|first=E.|year=1947|title=Recursive unsolvability of a problem of Thue|journal=Journal of Symbolic Logic|volume=12|issue=1|pages=1–11|doi=10.2307/2267170|jstor=2267170}} Передруковано в {{Harvnb|Davis|1965}}.
:* {{cite journal|last1=Shore|first1=Richard A.|last2=Slaman|first2=Theodore A.|author2-link=Theodore Slaman|year=1999|title=Defining the Turing jump|url=http://www.math.cornell.edu/~shore/papers/pdf/jumpmrl.pdf|journal=[[Mathematical Research Letters]]|volume=6|issue=6|pages=711–722|doi=10.4310/mrl.1999.v6.n6.a10|mr=1739227|doi-access=free}}
:* {{cite journal|last1=Slaman|first1=T.|last2=Woodin|first2=W.H.|year=1986|title=Definability in the Turing degrees|url=https://archive.org/details/sim_illinois-journal-of-mathematics_summer-1986_30_2/page/320|journal=Illinois J. Math.|volume=30|issue=2|pages=320–334|doi=10.1215/ijm/1256044641|mr=840131|doi-access=free}}
:* {{cite journal|last=Soare|first=R.I.|year=1974|title=Automorphisms of the lattice of recursively enumerable sets, Part I: Maximal sets|url=https://archive.org/details/sim_annals-of-mathematics_1974-07_100_1/page/80|journal=Annals of Mathematics|volume=100|issue=1|pages=80–120|doi=10.2307/1970842|jstor=1970842}}
:* {{cite journal|last=Turing|first=A.M.|year=1938|title=On Computable Numbers, with an Application to the Entscheidungsproblem. A Correction|journal=Proceedings of the London Mathematical Society|volume=s2-43|issue=1|pages=544–6|doi=10.1112/plms/s2-43.6.544}} Передруковано в {{Harvnb|Davis|1965}}. [http://web.comlab.ox.ac.uk/oucl/research/areas/ieg/e-library/sources/tp2-ie.pdf PDF із comlab.ox.ac.uk]
:* {{cite journal|last=Turing|first=A.M.|year=1939|title=Systems of logic based on ordinals|journal=Proceedings of the London Mathematical Society|volume=s2-45|issue=1|pages=161–228|doi=10.1112/plms/s2-45.1.161|hdl-access=free}} Передруковано в {{Harvnb|Davis|1965}}.

== Посилання ==

* [http://www.aslonline.org/ Домашня сторінка асоціації символічної логіки]
* [http://www.maths.leeds.ac.uk/cie/ Домашня сторінка обчислюваності в Європі]
* [http://www.comp.nus.edu.sg/~fstephan/recursiontheory.html Веб-сторінка курсу теорії рекурсії на рівні магістратури з приблизно 100 сторінками конспектів лекцій]
* [http://www.comp.nus.edu.sg/~fstephan/learning.ps Конспекти лекцій німецької мови з індуктивного висновку]
{{Інформатика}}{{Математична логіка}}
[[Категорія:Математична логіка]]
[[Категорія:Теорія рекурсії]]