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

Для понятия вычислимости см. Вычислимость .

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

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

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

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

Введение

н	2	3	4	5	6	7	...
С( п )	4	6	13	4098	> 3,5 × 10 18 267	> 10 10 10 10 18 705 353	?
Не появляется. Функция Busy Beaver Σ( n ) растет быстрее, чем любая вычислимая функция. Следовательно, оно не вычислимо; известны лишь несколько значений.

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

Фундаментальные результаты, полученные исследователями, установили, что вычислимость Тьюринга является правильной формализацией неформальной идеи эффективных вычислений. В 1952 году эти результаты побудили Клини придумать два названия «тезис Черча». и «Диссертация Тьюринга». В настоящее время их часто рассматривают как единую гипотезу, тезис Чёрча-Тьюринга , который утверждает, что любая функция, вычислимая алгоритмом , является вычислимой функцией . Хотя поначалу он был настроен скептически, к 1946 году Гёдель выступил в пользу этого тезиса:

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

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

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

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

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

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

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

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

Области исследований

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

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

Основные статьи: сокращение Тьюринга и степень Тьюринга

Теория вычислимости в математической логике традиционно фокусируется на относительной вычислимости , обобщении вычислимости Тьюринга, определенном с использованием оракулов-машин Тьюринга , представленных Тьюрингом в 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. представляет собой набор натуральных чисел , Скачок Тьюринга любого набора всегда имеет более высокую степень Тьюринга, чем исходный набор, а теорема Фридбурга показывает, что любой набор, вычисляющий проблему остановки, может быть получен как скачок Тьюринга другого набора. Теорема Поста устанавливает тесную связь между операцией прыжка Тьюринга и арифметической иерархией , которая представляет собой классификацию определенных подмножеств натуральных чисел, основанную на их определимости в арифметике.

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

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

Основная статья: Редукция (теория рекурсии)

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

К сильной сводимости относятся:

Сводимость к одному : A сводится к одному (или 1-сводится ) к B если существует полная вычислимая инъективная функция f такая, что каждое n находится в A тогда и только тогда, когда f ( n ) находится в B. ,

Сводимость «многие к одному» . По сути, это сводимость «один к одному» без ограничения на f инъективность . A является сводимым по многим параметрам (или m-сводимым ) к B, если существует полная вычислимая функция f такая, что каждое находится в A тогда и только тогда, когда f ( n ) находится в B. n

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

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

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

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

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

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

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

Основная статья: Обратная математика

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

Нумерация

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

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

Дополнительная информация: степень Тьюринга § Проблема Поста и метод приоритетов.

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

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

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

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

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

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

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

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

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

Область колмогоровской сложности и алгоритмической случайности разрабатывалась в 1960-х и 1970-х годах Хайтиным, Колмогоровым, Левиным, Мартином-Лёфом и Соломоновым (имена здесь даны в алфавитном порядке; большая часть исследований была независимой, а единство концепции случайности в то время еще не понимали). Основная идея состоит в том, чтобы рассмотреть универсальную машину Тьюринга U и измерить сложность числа (или строки) x как длину кратчайшего входного сигнала p, такого, что U ( p ) выводит x . Этот подход произвел революцию в более ранних способах определения того, является ли бесконечная последовательность (т. е. характеристическая функция подмножества натуральных чисел) случайной или нет, используя понятие случайности для конечных объектов. Колмогоровская сложность стала не только предметом самостоятельного изучения, но и применяется к другим предметам как инструмент получения доказательств.В этой области еще остается много открытых проблем.

Вычисление частоты

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

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

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

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

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

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

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

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

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

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

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

Имя

Область математической логики, занимающаяся вычислимостью и ее обобщениями, с самого начала называлась «теорией рекурсии». Роберт И. Соаре , известный исследователь в этой области, предложил вместо этого эту область следует называть «теорией вычислимости». Он утверждает, что терминология Тьюринга, использующая слово «вычислимый», более естественна и более широко понятна, чем терминология, использующая слово «рекурсивный», введенная Клини. Многие современные исследователи начали использовать эту альтернативную терминологию. Эти исследователи также используют такую ​​терминологию, как частично вычислимая функция и вычислимо перечислимое ( ce ) множество вместо частично рекурсивной функции и рекурсивно перечислимого ( re ) множества . Однако, как пояснил Fortnow, не все исследователи были в этом убеждены. и Симпсон. имен Некоторые комментаторы утверждают, что ни теория рекурсии , ни теория вычислимости не отражают тот факт, что большинство объектов, изучаемых в теории вычислимости, невычислимы.

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

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

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

См. также

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

Дальнейшее чтение

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

• Купер, С. Барри (2004). Теория вычислимости . Чепмен и Холл /CRC. ISBN  1-58488-237-9 .
• Матиясевич, Юрий Владимирович (1993). Десятая проблема Гильберта . МТИ Пресс . ISBN  0-262-13295-8 .

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

• Джайн, Санджай; Ошерсон, Дэниел Натан ; Ройер, Джеймс С.; Шарма, Арун (1999). Системы, которые обучаются: введение в теорию обучения (2-е изд.). Брэдфордская книга / MIT Press . ISBN  0-262-10077-0 . LCCN   98-34861 .
• Лерман, Мануэль (1983). Степени неразрешимости . Перспективы математической логики. Спрингер-Верлаг . ISBN  3-540-12155-2 .
• Нис, Андре (2009). Вычислимость и случайность . Издательство Оксфордского университета . ISBN  978-0-19-923076-1 .
• Одифредди, Пьерджорджо (1989). Классическая теория рекурсии . Северная Голландия . ISBN  0-444-87295-7 .
• Одифредди, Пьерджорджо (1999). Классическая теория рекурсии . Том II. Эльзевир . ISBN  0-444-50205-Х .

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

• Эндертон, Герберт Брюс (1977). «Элементы теории рекурсии» . В Барвайзе, Джон (ред.). Справочник по математической логике . Северная Голландия . стр. 527–566 . ISBN  0-7204-2285-Х .

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

• Бургин, Марк; Клингер, Аллен (2004). «Опыт, поколения и ограничения в машинном обучении». Теоретическая информатика . 317 (1–3): 71–91. дои : 10.1016/j.tcs.2003.12.005 .
• Фридберг, Ричард М. (1958). «Три теоремы о рекурсивном перечислении: I. Разложение, II. Максимальное множество, III. Перечисление без повторения». Журнал символической логики . 23 (3): 309–316. дои : 10.2307/2964290 . JSTOR   2964290 . S2CID   25834814 .
• Голд, Э. Марк (1967). «Языковая идентификация в пределе» (PDF) . Информация и контроль . 10 (5): 447–474. дои : 10.1016/s0019-9958(67)91165-5 . [1]
• Йокуш, Карл Гроос младший (1968). «Полурекурсивные множества и положительная сводимость» . Труды Американского математического общества . 137 (2): 420–436. дои : 10.1090/S0002-9947-1968-0220595-7 . JSTOR   1994957 .
• Клини, Стивен Коул ; Пост, Эмиль Леон (1954). «Верхняя полурешетка степеней рекурсивной неразрешимости». Анналы математики . Серия 2. 59 (3): 379–407. дои : 10.2307/1969708 . JSTOR   1969708 .
• Майхилл, Джон Р. старший (1956). «Решетка рекурсивно перечислимых множеств». Журнал символической логики . 21 : 215–220. дои : 10.1017/S002248120008525X . S2CID   123260425 .
• Пост, Эмиль Леон (1947). «Рекурсивная неразрешимость проблемы Туэ». Журнал символической логики . 12 (1): 1–11. дои : 10.2307/2267170 . JSTOR   2267170 . S2CID   30320278 . Перепечатано в Дэвисе в 1965 году .

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

• Домашняя страница Ассоциации символической логики
• Домашняя страница «Вычислимость в Европе». Архивировано 17 февраля 2011 г. на Wayback Machine.
• Веб-страница курса теории рекурсии для аспирантов с примерно 100 страницами конспектов лекций.
• Конспекты лекций по немецкому языку по индуктивному выводу