Теория вычислимости - Computability theory

Теория вычислимости, также известен как теория рекурсии, является ветвью математическая логика, Информатика, а теория вычислений который возник в 1930-х годах с изучением вычислимые функции и Степени Тьюринга. С тех пор эта область расширилась за счет изучения обобщенных вычислимость и определимость^{[необходимо разрешение неоднозначности ]}. В этих областях теория рекурсии пересекается с теория доказательств и эффективная дескриптивная теория множеств.

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

• Что это значит для функция на натуральные числа быть вычислимым?
• Как можно классифицировать невычислимые функции в иерархию на основе их уровня невычислимости?

Хотя существует значительное совпадение в терминах знаний и методов, теоретики математической рекурсии изучают теорию относительной вычислимости, понятия сводимости и структуры степеней; специалисты в области информатики сосредотачиваются на теории субрекурсивные иерархии, формальные методы, и формальные языки.

Вычислимые и невычислимые множества

Теория рекурсии зародилась в 1930-х годах. Курт Гёдель, Церковь Алонсо, Рожа Петер, Алан Тьюринг, Стивен Клини, и Эмиль Пост.^[1][2]

Полученные исследователями фундаментальные результаты установили Вычислимость по Тьюрингу как правильная формализация неформального представления об эффективном расчете. Эти результаты привели Стивен Клини (1952), чтобы придумать два названия: «Тезис Чёрча» (Kleene 1952: 300) и «Тезис Тьюринга» (Kleene 1952: 376). В настоящее время их часто рассматривают как единую гипотезу. Тезис Черча – Тьюринга, который утверждает, что любая функция, вычислимая алгоритм это вычислимая функция. Хотя поначалу он был настроен скептически, к 1946 году Гедель выступил в поддержку этого тезиса:

«Тарский подчеркнул в своей лекции (и я думаю, что это справедливо) огромную важность концепции общей рекурсивности (или вычислимости Тьюринга). Мне кажется, что эта важность во многом объясняется тем фактом, что с этой концепцией времени удалось дать абсолютное понятие интересному эпистемологическому понятию, т. е. понятию, не зависящему от выбранного формализма *. »(Gödel 1946 in Davis 1965: 84).^[3]

С определением эффективных вычислений пришли первые доказательства того, что в математике есть проблемы, которые нельзя эффективно решить. приняли решение. Черч (1936a, 1936b) и Тьюринг (1936), вдохновленные методами, использованными Геделем (1931) для доказательства его теорем о неполноте, независимо продемонстрировали, что Entscheidungsproblem не разрешима эффективно. Этот результат показал, что не существует алгоритмической процедуры, которая могла бы правильно решить, истинны или ложны произвольные математические предложения.

Много проблем в математика было показано, что они неразрешимы после того, как были установлены эти первоначальные примеры. В 1947 г. Марков и Пост опубликовали независимые статьи, показывающие, что проблема слов для полугрупп не может быть эффективно решена. Расширяя этот результат, Петр Новиков и Уильям Бун независимо показали в 1950-х, что проблема слов для групп не разрешима эффективно: не существует эффективной процедуры, которая, учитывая слово в конечно представленной группа, будет решать, является ли элемент, представленный словом, элемент идентичности группы. В 1970 г. Юрий Матиясевич доказано (с использованием результатов Джулия Робинсон ) Теорема Матиясевича, откуда следует, что Десятая проблема Гильберта не имеет эффективного решения; эта проблема спрашивала, существует ли эффективная процедура для определения того, Диофантово уравнение над целыми числами имеет решение в целых числах. В список неразрешимых проблем дает дополнительные примеры проблем, для которых нет вычислимого решения.

Изучение того, какие математические построения могут быть эффективно выполнены, иногда называют рекурсивная математика; то Справочник по рекурсивной математике (Ершов и другие. 1998) охватывает многие известные результаты в этой области.

Вычислимость по Тьюрингу

Основная форма вычислимости, изучаемая в теории рекурсии, была введена Тьюрингом (1936). Набор натуральных чисел называется вычислимое множество (также называемый разрешимый, рекурсивный, или Вычислимый по Тьюрингу набор), если есть Машина Тьюринга что, учитывая номер п, останавливается с выходом 1, если п находится в наборе и останавливается с выходом 0, если п нет в комплекте. Функция ж от натуральных чисел к себе есть рекурсивный или (Тьюринг) вычислимая функция если есть машина Тьюринга, которая на входе п, останавливает и возвращает вывод ж(п). Здесь нет необходимости использовать машины Тьюринга; есть много других модели вычислений обладающие той же вычислительной мощностью, что и машины Тьюринга; например μ-рекурсивные функции полученный из примитивной рекурсии и оператора μ.

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

Не каждый набор натуральных чисел вычислим. В проблема остановки, который представляет собой набор (описаний) машин Тьюринга, которые останавливаются на входе 0, является хорошо известным примером невычислимого набора. Существование множества невычислимых множеств следует из того факта, что существуют только счетно много Машины Тьюринга и, следовательно, только счетное множество вычислимых множеств, но согласно Теорема кантора, есть бесчисленное множество наборы натуральных чисел.

Хотя проблема остановки не поддается вычислению, можно смоделировать выполнение программы и создать бесконечный список программ, которые действительно останавливаются. Таким образом, проблема остановки является примером рекурсивно перечислимый набор, который представляет собой набор, который может быть перечислен машиной Тьюринга (другие термины для рекурсивного перечисления включают вычислимо перечислимый и полуразрешимый). Точно так же набор рекурсивно перечислим тогда и только тогда, когда он является диапазоном некоторой вычислимой функции. Рекурсивно перечислимые множества, хотя и не разрешимы в общем случае, подробно изучены в теории рекурсии.

Направления исследований

Начиная с теории рекурсивных множеств и функций, описанной выше, область теории рекурсии расширилась и включает изучение многих тесно связанных тем. Это не независимые области исследований: каждая из этих областей черпает идеи и результаты из других, и большинство теоретиков рекурсии знакомы с большинством из них.

Относительная вычислимость и степени Тьюринга

Теория рекурсии в математической логике традиционно фокусировалась на относительная вычислимость, обобщение вычислимости по Тьюрингу, определенное с помощью оракул машины Тьюринга, введенный Тьюрингом (1939). Оракульная машина Тьюринга - это гипотетическое устройство, которое, помимо выполнения действий обычной машины Тьюринга, способно задавать вопросы оракул, который представляет собой определенный набор натуральных чисел. Оракул-машина может задавать вопросы только в форме "Есть п в наборе оракула? ". На каждый вопрос будет немедленно дан правильный ответ, даже если набор оракула не вычислим. Таким образом, машина оракула с невычислимым оракулом сможет вычислить множества, которые машина Тьюринга без оракула не может.

Неформально набор натуральных чисел А является Сводимый по Тьюрингу к набору B если есть машина оракула, которая правильно сообщает, находятся ли числа в А когда бежишь с B как набор оракула (в данном случае набор А также называется (относительно) вычислим из B и рекурсивный в B). Если набор А сводится по Тьюрингу к множеству B и B сводится ли Тьюринг к А тогда говорят, что множества имеют одинаковые Степень Тьюринга (также называется степень неразрешимости). Степень Тьюринга множества дает точную меру того, насколько невычислимо это множество.

Естественные примеры невычислимых множеств, включая множество различных множеств, которые кодируют варианты проблема остановки, имеют два общих свойства:

1. Они есть рекурсивно перечислимый, и
2. Каждый может быть переведен на любой другой через много-одно сокращение. То есть с учетом таких наборов А и B, существует полная вычислимая функция ж такой, что А = {Икс : ж(Икс) ∈ B}. Эти наборы называются много-один эквивалент (или м-эквивалент).

Редукции многие-единицы «сильнее», чем редукции Тьюринга: если множество А сводится к множеству B, тогда А сводится ли Тьюринг к B, но не всегда верно обратное. Хотя естественные примеры невычислимых множеств эквивалентны многим единицам, можно построить рекурсивно перечислимые множества. А и B такой, что А сводится ли Тьюринг к B но не многие-один сводится к B. Можно показать, что каждое рекурсивно перечислимое множество сводится к задаче остановки до нескольких единиц, и, таким образом, проблема остановки является наиболее сложным рекурсивно перечислимым множеством в отношении сводимости до нескольких единиц и сводимости по Тьюрингу. Пост (1944) спросил, каждый рекурсивно перечислимое множество либо вычислимо, либо Эквивалент Тьюринга к проблеме остановки, то есть о том, не существует ли рекурсивно перечислимого множества со степенью Тьюринга, промежуточной между этими двумя.

В качестве промежуточных результатов Пост определил естественные типы рекурсивно перечислимых множеств, такие как просто, гиперпростой и гипергиперпростые множества. Пост показал, что эти множества находятся строго между вычислимыми множествами и проблемой остановки в отношении сводимости многих единиц. Пост также показал, что некоторые из них являются строго промежуточными по другим понятиям сводимости, более сильным, чем сводимость по Тьюрингу. Но Пост оставил открытой главную проблему существования рекурсивно перечислимых множеств промежуточной степени Тьюринга; эта проблема стала известна как Проблема с постом. Спустя десять лет Клини и Пост показали в 1954 г., что существуют промежуточные степени Тьюринга между степенями вычислимых множеств и проблемой остановки, но им не удалось показать, что какая-либо из этих степеней содержит рекурсивно перечислимое множество. Вскоре после этого Фридберг и Мучник независимо решили проблему Поста, установив существование рекурсивно перечислимых множеств промежуточной степени. Этот новаторский результат открыл широкое исследование степеней Тьюринга рекурсивно перечислимых множеств, которые, как оказалось, обладают очень сложной и нетривиальной структурой.

Существует несчетное количество множеств, которые не являются рекурсивно перечислимыми, и исследование степеней Тьюринга всех множеств занимает такое же центральное место в теории рекурсии, как и исследование рекурсивно перечислимых степеней Тьюринга. Было построено много степеней со специальными свойствами: гипериммунные степени где каждая функция, вычислимая относительно этой степени, мажорируется (нерелятивизированной) вычислимой функцией; высокие степени относительно которого можно вычислить функцию ж который доминирует над каждой вычислимой функцией г в том смысле, что существует постоянная c в зависимости от г такой, что д (х) <е (х) для всех х> с; случайные степени содержащий алгоритмически случайные множества; 1-общий степени 1-общих множеств; и степени ниже проблемы остановки предельно-рекурсивный наборы.

Изучение произвольных (не обязательно рекурсивно перечислимых) степеней Тьюринга включает изучение скачка Тьюринга. Учитывая набор А, то Прыжок Тьюринга из А представляет собой набор натуральных чисел, кодирующих решение проблемы остановки для машин Тьюринга Oracle, работающих с Oracle А. Скачок Тьюринга любого набора всегда имеет более высокую степень Тьюринга, чем исходный набор, и теорема Фридбурга показывает, что любой набор, который вычисляет проблему остановки, может быть получен как скачок Тьюринга другого набора. Теорема Поста устанавливает тесную связь между операцией перехода Тьюринга и арифметическая иерархия, который представляет собой классификацию определенных подмножеств натуральных чисел на основе их определимости в арифметике.

Многие недавние исследования степеней Тьюринга были сосредоточены на общей структуре множества степеней Тьюринга и множества степеней Тьюринга, содержащих рекурсивно перечислимые множества. Глубокая теорема Шора и Сламана (1999) утверждает, что функция, отображающая степень Икс степень ее скачка Тьюринга определима в частичном порядке степеней Тьюринга. Недавний обзор, проведенный Ambos-Spies и Fejer (2006), дает обзор этого исследования и его исторического развития.

Другие сводимости

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

Сильные сводимости включают:

Сводимость один-один

А является однозначно сводимый (или 1-сводимый) к B если есть общая вычислимая инъективная функция ж так что каждый п в А если и только если ж(п) в B.

Сводимость многих единиц

По сути, это сводимость один к одному без ограничения, которое ж быть инъективным. А является много-один сводимый (или m-сводимый) к B если есть полная вычислимая функция ж так что каждый п в А если и только если ж(п) в B.

Сводимость таблицы истинности

А сводится ли таблица истинности к B если А сводится ли Тьюринг к B через машину Тьюринга оракула, которая вычисляет общую функцию независимо от того, какой оракул ей дан. Из-за компактности Канторовское пространство, это эквивалентно тому, что сокращение представляет один список вопросов (зависящий только от входных данных) одновременно для оракула, а затем, увидев их ответы, можно получить результат, не задавая дополнительных вопросов, независимо от ответа оракула на начальные запросы. Также были изучены многие варианты сводимости таблицы истинности.

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

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

Сводимости более слабые, чем сводимость по Тьюрингу (то есть сводимости, подразумеваемые сводимостью по Тьюрингу), также изучались. Наиболее известны арифметическая сводимость и гиперарифметическая сводимость. Эти сводимости тесно связаны с определимостью по стандартной модели арифметики.

Теорема Райса и арифметическая иерархия

Райс показал, что для каждого нетривиального класса C (который содержит некоторые, но не все r.e. множества) индексный набор E = {е: the еth r.e. набор W_е в C} обладает тем свойством, что либо проблема остановки или его дополнение много-единица сводится к E, то есть может быть отображено с помощью много-одно сокращение к E (увидеть Теорема Райса для более подробной информации). Но многие из этих наборов индексов даже сложнее, чем проблема остановки. Эти типы наборов можно классифицировать с помощью арифметическая иерархия. Например, индексное множество FIN класса всех конечных множеств находится на уровне Σ₂, индексное множество REC класса всех рекурсивных множеств находится на уровне Σ₃, индексное множество COFIN всех конфинитных множеств также находится на уровне Σ₃ и индексное множество COMP класса всех полных по Тьюрингу множеств Σ₄. Эти уровни иерархии определяются индуктивно: Σ_п+1 содержит только все множества, которые рекурсивно перечислимы относительно Σ_п; Σ₁ содержит рекурсивно перечислимые множества. Приведенные здесь наборы индексов являются полными даже для своих уровней, то есть все наборы на этих уровнях могут быть сведены в один ряд к данным наборам индексов.

Обратная математика

Программа обратная математика спрашивает, какие аксиомы существования множеств необходимы для доказательства конкретных теорем математики в подсистемах арифметика второго порядка. Это исследование было инициировано Харви Фридман и был подробно изучен Стивен Симпсон и другие; Симпсон (1999) дает подробное обсуждение программы. Рассматриваемые аксиомы существования множеств неформально соответствуют аксиомам, утверждающим, что множество степеней натуральных чисел замкнуто относительно различных понятий сводимости. Самая слабая такая аксиома, изучаемая в обратной математике, - это рекурсивное понимание, который утверждает, что множество натуральных чисел замкнуто относительно сводимости по Тьюрингу.

Нумерации

Нумерация - это перечисление функций; у него два параметра, е и Икс и выводит значение е-я функция в нумерации на входе Икс. Нумерация может быть частично рекурсивной, хотя некоторые из ее членов являются полностью рекурсивными, то есть вычислимыми функциями. Допустимые нумерации те, в которые могут быть переведены все остальные. А Нумерация Фридберга (назван в честь своего первооткрывателя) - это однозначная нумерация всех частично рекурсивных функций; это обязательно не допустимая нумерация. Более поздние исследования касались также нумерации других классов, таких как классы рекурсивно перечислимых множеств. Гончаров открыл, например, класс рекурсивно перечислимых множеств, нумерация которых распадается ровно на два класса относительно рекурсивных изоморфизмов.

Приоритетный метод

Для дальнейшего объяснения см. Раздел Проблема поста и метод приоритета в статье Степень Тьюринга.

Проблема Post была решена с помощью метода, названного приоритетный метод; доказательство с использованием этого метода называется приоритетный аргумент. Этот метод в основном используется для создания рекурсивно перечислимых наборов с определенными свойствами. Чтобы использовать этот метод, желаемые свойства создаваемого набора разбиваются на бесконечный список целей, известный как требования, так что выполнение всех требований приведет к тому, что построенный набор будет иметь желаемые свойства. Каждому требованию присваивается натуральное число, представляющее приоритет требования; поэтому 0 присваивается самому важному приоритету, 1 - второму по важности и так далее. Затем набор строится поэтапно, каждый этап пытается удовлетворить одно или несколько требований, либо добавляя числа к набору, либо запрещая числа из набора, чтобы окончательный набор удовлетворял требованию. Может случиться так, что выполнение одного требования приведет к неудовлетворению другого; порядок приоритета используется, чтобы решить, что делать в таком случае.

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

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

Когда Пост определил понятие простого множества как r.e. множество с бесконечным дополнением, не содержащим бесконечных с.в. set, он начал изучать структуру рекурсивно перечислимых множеств при включении. Эта решетка стала хорошо изученной структурой. Рекурсивные множества могут быть определены в этой структуре по основному результату, что набор является рекурсивным тогда и только тогда, когда набор и его дополнение рекурсивно перечислимы. Бесконечный r.e. множества всегда имеют бесконечные рекурсивные подмножества; но с другой стороны, простые множества существуют, но не имеют бесконечного рекурсивного надмножества. Пост (1944) ввел уже гиперпростые и гипергиперпростые множества; позже были построены максимальные множества, т. е. такие множества, что каждое с.в. надмножество является либо конечным вариантом данного максимального набора, либо ко-конечным. Первоначальной мотивацией Поста при изучении этой решетки было найти такое структурное понятие, что каждое множество, удовлетворяющее этому свойству, не находится ни в степени Тьюринга рекурсивных множеств, ни в степени Тьюринга проблемы остановки. Пост не нашел такого свойства, и вместо этого для решения его проблемы были применены методы приоритета; Харрингтон и Соар (1991) в конце концов обнаружили такое свойство.

Проблемы автоморфизма

Другой важный вопрос - существование автоморфизмов в теоретико-рекурсивных структурах. Одна из этих структур состоит в том, что одно из рекурсивно перечислимых множеств относительно включения по модулю конечной разности; в этой структуре, А ниже B тогда и только тогда, когда установленная разница B − А конечно. Максимальные наборы (как определено в предыдущем абзаце) обладают тем свойством, что они не могут быть автоморфными по отношению к немаксимальным множествам, то есть, если существует автоморфизм рекурсивных перечислимых множеств в рамках только что упомянутой структуры, то каждое максимальное множество отображается в другое максимальное множество. набор. Соар (1974) показал, что верно и обратное, т. Е. Любые два максимальных множества автоморфны. Таким образом, максимальные множества образуют орбиту, то есть каждый автоморфизм сохраняет максимальность, и любые два максимальных множества преобразуются друг в друга некоторым автоморфизмом. Харрингтон привел еще один пример автоморфного свойства: свойство творческих множеств, множеств, равных множеству единиц, эквивалентной проблеме остановки.

Помимо решетки рекурсивно перечислимых множеств, автоморфизмы изучаются также для структуры степеней Тьюринга всех множеств, а также для структуры степеней Тьюринга с.в. наборы. В обоих случаях Купер утверждает, что построил нетривиальные автоморфизмы, которые переводят одни степени в другие; эта конструкция, однако, не была проверена, и некоторые коллеги полагают, что конструкция содержит ошибки и что вопрос о том, существует ли нетривиальный автоморфизм степеней Тьюринга, по-прежнему является одним из основных нерешенных вопросов в этой области (Slaman and Woodin 1986, Ambos-Spies and Fejer 2006).

Колмогоровская сложность

Поле Колмогоровская сложность и алгоритмическая случайность был разработан в 1960-х и 1970-х годах Чайтиным, Колмогоровым, Левиным, Мартином-Лёфом и Соломоновым (имена даны здесь в алфавитном порядке; большая часть исследований была независимой, и единство концепции случайности в то время не понималось ). Основная идея - рассмотреть универсальная машина Тьюринга U и для измерения сложности числа (или строки) Икс как длина самого короткого ввода п такой, что U(п) выходы Икс. Этот подход произвел революцию в более ранних способах определения, когда бесконечная последовательность (эквивалентная характеристическая функция подмножества натуральных чисел) является случайной или нет, путем обращения к понятию случайности для конечных объектов. Колмогоровская сложность стала не только предметом самостоятельного изучения, но и применяется к другим предметам как инструмент для получения доказательств. В этой области до сих пор остается много открытых проблем. По этой причине в январе 2007 г. была проведена недавняя исследовательская конференция в этой области.^[4] и список открытых проблем^[5] поддерживается Джозефом Миллером и Андре Нисом.

Расчет частоты

В этом разделе теории рекурсии анализируется следующий вопрос: при фиксированном м и п с 0 <м < п, для которых функции А возможно ли вычислить для любого другого п входы Икс₁, Икс₂, ..., Икс_п кортеж п числа у₁, y₂, ..., y_п так что по крайней мере м уравнений А(Икс_k) = у_k верны. Такие наборы известны как (м, п) -рекурсивные множества. Первым важным результатом в этой ветви теории рекурсии является результат Трахтенброта о том, что множество вычислимо, если оно (м, п) -рекурсивно для некоторых м, п с 2м > п. С другой стороны, Джокуш полурекурсивный множества (которые были уже неофициально известны до того, как Джокуш представил их в 1968 году) являются примерами множества, которое (м, п) -рекурсивно тогда и только тогда, когда 2м < п + 1. Таких множеств несчетное количество, а также несколько рекурсивно перечислимых, но невычислимых множеств этого типа. Позже Дегтев установил иерархию рекурсивно перечислимых множеств, которые (1,п + 1) -рекурсивно, но не (1,п) -рекурсивный. После долгого этапа исследований, проведенных российскими учеными, эта тема стала популярной на Западе благодаря тезису Бейгеля об ограниченных запросах, в котором вычисление частот связывалось с вышеупомянутыми ограниченными сводимостями и другими связанными понятиями. Одним из основных результатов была теория мощности Куммера, которая утверждает, что множество А вычислимо тогда и только тогда, когда существует п такой, что некоторый алгоритм перечисляет для каждого кортежа п разные числа до п много возможных вариантов мощности этого набора п числа пересекаются с А; эти варианты должны содержать истинное количество элементов, но не включать по крайней мере одно ложное.

Индуктивный вывод

Это теоретико-рекурсивный раздел теории обучения. Он основан на Э. Марк Голд Модель обучения в пределе с 1967 года, и с тех пор разрабатывается все больше и больше моделей обучения. Общий сценарий следующий: для данного класса S вычислимых функций, существует ли обучающийся (то есть рекурсивный функционал), который выводит для любого ввода формы (ж(0),ж(1),...,ж(п)) гипотеза. Ученик M изучает функцию ж если почти все гипотезы имеют одинаковый индекс е из ж относительно заранее согласованной приемлемой нумерации всех вычислимых функций; M учится S если M учится каждому ж в S. Основные результаты заключаются в том, что все рекурсивно перечисляемые классы функций доступны для обучения, в то время как класс REC всех вычислимых функций не обучается. Было рассмотрено множество связанных моделей, а также изучение классов рекурсивно перечислимых множеств на основе положительных данных - тема, изученная в новаторской статье Голда 1967 года.

Обобщения вычислимости по Тьюрингу

Теория рекурсии включает изучение обобщенных понятий этой области, таких как арифметическая сводимость, гиперарифметическая сводимость и теория α-рекурсии, как описано Sacks (1990). Эти обобщенные понятия включают сводимости, которые не могут быть выполнены машинами Тьюринга, но, тем не менее, являются естественными обобщениями сводимости Тьюринга. Эти исследования включают подходы к исследованию аналитическая иерархия который отличается от арифметическая иерархия разрешая количественную оценку по наборам натуральных чисел в дополнение к количественной оценке по отдельным числам. Эти области связаны с теориями хороших порядков и деревьев; например, набор всех индексов рекурсивных (недвоичных) деревьев без бесконечных ветвей является полным для уровня ${ displaystyle Pi _ {1} ^ {1}}$ аналитической иерархии. Как сводимость по Тьюрингу, так и гиперарифметическая сводимость важны в области эффективная дескриптивная теория множеств. Еще более общее понятие степени конструктивности изучается в теория множеств.

Теория непрерывной вычислимости

Теория вычислимости цифровых вычислений хорошо разработана. Теория вычислимости менее развита для аналоговые вычисления что происходит в аналоговые компьютеры, обработка аналогового сигнала, аналоговая электроника, нейронные сети и непрерывное время теория управления, смоделированный дифференциальные уравнения и непрерывный динамические системы (Орпонен 1997; Мур 1996).

Связь между определимостью, доказательством и вычислимостью

Существует тесная взаимосвязь между степенью Тьюринга набора натуральных чисел и сложностью (в терминах арифметическая иерархия ) определения этого множества с помощью формула первого порядка. Одно из таких отношений уточняется Теорема Поста. Более слабые отношения продемонстрировали Курт Гёдель в доказательствах его теорема полноты и теоремы о неполноте. Доказательства Гёделя показывают, что множество логических следствий эффективной теории первого порядка рекурсивно перечислимый набор, и что, если теория достаточно сильна, это множество будет невычислимым. Так же, Теорема Тарского о неопределенности можно интерпретировать как с точки зрения определимости, так и с точки зрения вычислимости.

Теория рекурсии также связана с арифметика второго порядка, формальная теория натуральных чисел и множеств натуральных чисел. Тот факт, что определенные множества вычислимы или относительно вычислимы, часто подразумевает, что эти множества могут быть определены в слабых подсистемах арифметики второго порядка. Программа обратная математика использует эти подсистемы для измерения невычислимости, присущей хорошо известным математическим теоремам. Симпсон (1999) обсуждает многие аспекты арифметики второго порядка и обратной математики.

Поле теория доказательств включает изучение арифметики второго порядка и Арифметика Пеано, а также формальные теории натуральных чисел более слабые, чем арифметика Пеано. Одним из методов классификации силы этих слабых систем является определение вычислимых функций, которые система может оказаться Всего (см. Fairtlough and Wainer (1998)). Например, в примитивная рекурсивная арифметика любая вычислимая функция, которая доказуемо является полной, на самом деле примитивно рекурсивный, в то время как Арифметика Пеано доказывает, что функционирует как Функция Аккермана, которые не являются примитивно рекурсивными, являются общими. Однако не всякая итоговая вычислимая функция доказуемо является тотальной в арифметике Пеано; пример такой функции предоставляется Теорема Гудштейна.

имя

Область математической логики, имеющая дело с вычислимостью и ее обобщениями, с самого начала называлась «теорией рекурсии». Роберт И. Соаре, известный исследователь в этой области, предложил (Soare 1996) вместо этого называть эту область «теорией вычислимости». Он утверждает, что терминология Тьюринга, использующая слово «вычислимый», более естественна и более понятна, чем терминология, в которой используется слово «рекурсивный», введенная Клини. Многие современные исследователи начали использовать эту альтернативную терминологию.^[6] Эти исследователи также используют такую ​​терминологию, как частичная вычислимая функция и вычислимо перечислимый (c.e.) набор вместо того частичная рекурсивная функция и рекурсивно перечислимый (r.e.) набор. Однако не все исследователи были убеждены, как объяснил Фортноу^[7] и Симпсон.^[8]Некоторые комментаторы утверждают, что оба названия теория рекурсии и теория вычислимости не могут передать тот факт, что большинство объектов, изучаемых в теории рекурсии, не вычислимы.^[9]

Роджерс (1967) предположил, что ключевым свойством теории рекурсии является то, что ее результаты и структуры должны быть инвариантными относительно вычислимых биекции на натуральные числа (это предложение основано на идеях Программа Эрланген по геометрии). Идея состоит в том, что вычислимая биекция просто переименовывает числа в наборе, а не указывает какую-либо структуру в наборе, подобно тому, как поворот евклидовой плоскости не меняет какой-либо геометрический аспект линий, нарисованных на ней. Поскольку любые два бесконечных вычислимых множества связаны вычислимой биекцией, это предложение идентифицирует все бесконечные вычислимые множества (конечные вычислимые множества рассматриваются как тривиальные). Согласно Роджерсу, интересующие нас множества в теории рекурсии - это невычислимые множества, разделенные на классы эквивалентности вычислимыми биекциями натуральных чисел.

Профессиональные организации

Основной профессиональной организацией теории рекурсии является Ассоциация символической логики, который ежегодно проводит несколько научных конференций. Ассоциация междисциплинарных исследований Вычислимость в Европе (CiE) также организует серию ежегодных конференций.

Смотрите также

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

Заметки

использованная литература

Тексты на уровне бакалавриата

• Купер, С. (2004). Теория вычислимости. Чепмен и Холл / CRC. ISBN  1-58488-237-9.
• Катленд, Н. (1980). Вычислимость, Введение в теорию рекурсивных функций. Издательство Кембриджского университета. ISBN  0-521-29465-7.
• Матиясевич, Ю. (1993). Десятая проблема Гильберта. MIT Press. ISBN  0-262-13295-8.

Расширенные тексты

• Jain, S .; Ошерсон, Д .; Royer, J .; Шарма, А. (1999). Системы, которые обучаются, введение в теорию обучения (2-е изд.). Книга Брэдфорда. ISBN  0-262-10077-0.
• Клини, С. (1952). Введение в метаматематику. Северная Голландия. ISBN  0-7204-2103-9.
• Лерман, М. (1983). Степени неразрешимости. Перспективы математической логики. Springer-Verlag. ISBN  3-540-12155-2.
• Nies, Андре (2009). Вычислимость и случайность. Издательство Оксфордского университета. ISBN  978-0-19-923076-1.
• Одифредди, П. (1989). Классическая теория рекурсии. Северная Голландия. ISBN  0-444-87295-7.
• Одифредди, П. (1999). Классическая теория рекурсии. II. Эльзевир. ISBN  0-444-50205-X.
• Роджерс-младший, Х. (1987). Теория рекурсивных функций и эффективной вычислимости (2-е изд.). MIT Press. ISBN  0-262-68052-1.
• Сакс, Г. (1990). Теория высшей рекурсии. Springer-Verlag. ISBN  3-540-19305-7.
• Симпсон, С. (1999). Подсистемы арифметики второго порядка. Springer-Verlag. ISBN  3-540-64882-8.
• Соаре, Р.И. (1987). Рекурсивно перечислимые множества и степени. Перспективы математической логики. Springer-Verlag. ISBN  0-387-15299-7.

Обзорные статьи и сборники

• Ambos-Spies, K .; Фейер, П. (2006). «Степени неразрешимости» (PDF). Архивировано из оригинал (PDF) на 2013-04-20. Получено 2006-10-27. Неопубликованный препринт.
• Эндертон, Х. (1977). «Элементы теории рекурсии». В Барвайз, Дж. (ред.). Справочник по математической логике. Северная Голландия. стр.527–566. ISBN  0-7204-2285-X.
• Ершов Ю.Л .; Гончаров, С.С .; Nerode, A .; Реммель, Дж. Б. (1998). Справочник по рекурсивной математике. Северная Голландия. ISBN  0-7204-2285-X.
• Fairtlough, M .; Вайнер, С.С. (1998). «Иерархии доказуемо рекурсивных функций». In Buss, S.R. (ред.). Справочник по теории доказательств. Эльзевир. С. 149–208. ISBN  978-0-08-053318-6.
• Соаре, Р.И. (1996). «Вычислимость и рекурсия» (PDF). Бюллетень символической логики. 2 (3): 284–321. Дои:10.2307/420992. JSTOR  420992.

Научные статьи и сборники

• Burgin, M .; Клингер, А. (2004). «Опыт, поколения и ограничения в машинном обучении». Теоретическая информатика. 317 (1–3): 71–91. Дои:10.1016 / j.tcs.2003.12.005.
• Чёрч, А. (1936). «Неразрешимая проблема элементарной теории чисел». Американский журнал математики. 58 (2): 345–363. Дои:10.2307/2371045. JSTOR  2371045. Перепечатано в Дэвис 1965.
• Чёрч, А. (1936). «Заметка по проблеме Entscheidungsproblem». Журнал символической логики. 1 (1): 40–41. Дои:10.2307/2269326. JSTOR  2269326. Перепечатано в Дэвис 1965.
• Дэвис, Мартин, изд. (2004) [1965]. Неразрешимое: основные статьи о неразрешимых предложениях, неразрешимых проблемах и вычислимых функциях. Курьер. ISBN  978-0-486-43228-1.
• Фридберг, Р. (1958). «Три теоремы о рекурсивном перечислении: I. Декомпозиция, II. Максимальное множество, III. Перечисление без повторения». Журнал символической логики. 23 (3): 309–316. Дои:10.2307/2964290. JSTOR  2964290.
• Золото, Э. Марк (1967). «Определение языка в пределе» (PDF). Информация и контроль. 10 (5): 447–474. Дои:10.1016 / s0019-9958 (67) 91165-5. [1]
• Harrington, L .; Соаре, Р.И. (1991). «Программа Поста и неполные рекурсивно перечислимые множества». Proc. Natl. Акад. Sci. СОЕДИНЕННЫЕ ШТАТЫ АМЕРИКИ. 88 (22): 10242–6. Bibcode:1991PNAS ... 8810242H. Дои:10.1073 / pnas.88.22.10242. ЧВК  52904. PMID  11607241.
• Джокуш-младший, К. (1968). «Полукурсивные множества и положительная сводимость». Пер. Амер. Математика. Soc. 137 (2): 420–436. Дои:10.1090 / S0002-9947-1968-0220595-7. JSTOR  1994957.
• Kleene, S.C .; Пост, Э. (1954). «Верхняя полурешетка степеней рекурсивной неразрешимости». Анналы математики. Второй. 59 (3): 379–407. Дои:10.2307/1969708. JSTOR  1969708.
• Мур, К. (1996). «Теория рекурсии на вещественных числах и вычислениях в непрерывном времени». Теоретическая информатика. 162 (1): 23–44. CiteSeerX  10.1.1.6.5519. Дои:10.1016/0304-3975(95)00248-0.
• Майхилл, Дж. (1956). «Решетка рекурсивно перечислимых множеств». Журнал символической логики. 21: 215–220. Дои:10.1017 / S002248120008525X.
• Орпонен, П. (1997). «Обзор теории вычислений в непрерывном времени». Достижения в алгоритмах, языках и сложности: 209–224. CiteSeerX  10.1.1.53.1991. Дои:10.1007/978-1-4613-3394-4_11. ISBN  978-1-4613-3396-8.
• Пост, Э. (1944). «Рекурсивно перечислимые множества натуральных чисел и проблемы их решения». Бюллетень Американского математического общества. 50 (5): 284–316. Дои:10.1090 / S0002-9904-1944-08111-1. Г-Н  0010514.
• Пост, Э. (1947). «Рекурсивная неразрешимость проблемы Туэ». Журнал символической логики. 12 (1): 1–11. Дои:10.2307/2267170. JSTOR  2267170. Перепечатано в Дэвис 1965.
• Шор, Ричард А .; Сламан, Теодор А. (1999). «Определение скачка Тьюринга» (PDF). Письма о математических исследованиях. 6 (6): 711–722. Дои:10.4310 / mrl.1999.v6.n6.a10. Г-Н  1739227.
• Slaman, T .; Вудин, W.H. (1986). «Определимость в степенях Тьюринга». Иллинойс Дж. Математика. 30 (2): 320–334. Дои:10.1215 / ijm / 1256044641. Г-Н  0840131.
• Соаре, Р.И. (1974). "Автоморфизмы решетки рекурсивно перечислимых множеств. Часть I: Максимальные множества". Анналы математики. 100 (1): 80–120. Дои:10.2307/1970842. JSTOR  1970842.
• Тьюринг, А. (1937). «О вычислимых числах с приложением к Entscheidungsproblem». Труды Лондонского математического общества. s2-42 (1): 230–265. Дои:10.1112 / плмс / с2-42.1.230. Тьюринг, А. (1938). «О вычислимых числах в приложении к Entscheidungsproblem. Исправление». Труды Лондонского математического общества. s2-43 (1): 544–6. Дои:10.1112 / плмс / с2-43.6.544. Перепечатано в Дэвис 1965. PDF с comlab.ox.ac.uk
• Тьюринг, А. (1939). «Логические системы на основе ординалов». Труды Лондонского математического общества. s2-45 (1): 161–228. Дои:10.1112 / плмс / с2-45.1.161. HDL:21.11116 / 0000-0001-91CE-3. Перепечатано в Дэвис 1965.

внешние ссылки

• Домашняя страница Association for Symbolic Logic
• Вычислимость в Европе домашняя страница
• Веб-страница курса теории рекурсии для аспирантов с примерно 100 страницами конспектов лекций
• Конспект лекций на немецком языке по индуктивному выводу