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

редактировать

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

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

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

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

Содержание

  • 1 Вычислимые и невычислимые массивы
  • 2 Вычислимые по Тьюрингу
  • 3 Области исследований
    • 3.1 Относительная вычислимость и степень Тьюринга
    • 3.2 Другие сводимости
    • 3.3 Теорема Райса и арифметическая иерархия
    • 3.4 Обратная математика
    • 3.5 Нумерация
    • 3.6 Метод приоритета
    • 3.7 Решетка рекурсивно перечислимых множеств
    • 3.8 Проблемы автоморфизма
    • 3.9 Колмогоровская сложность
    • 3.10 Вычисление частот
    • 3.11 Индуктивный вывод
    • 3.12 Обобщения вычислимости Тьюринга
    • 3.13 Теория непрерывной вычислимости
  • 4 Взаимосвязь, взаимозависимость доказательством и вычислимостью
  • 5 Название
  • 6 Профессиональные организации
  • 7 См. Также
  • 8 Примечания
  • 9 Ссылки
  • 10 Внешние ссылки

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Неформально, набор натуральных чисел A сводится по Тьюрингу к множеству B, если существует машина оракула, которая правильно сообщает, находятся ли числа в A при запуске с B в качестве набора оракулов (в этом качестве случае множество A также называется (относительно) вычислимым из B и рекурсивным в B). Если набор сводится по Тьюрингу к множеству 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) for all x>c; случайные степени, содержащие алгоритмически случайные числа ; 1-общие степени 1-общих множеств; и степени ниже проблемы остановки предельно-рекурсивных наборов.

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

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

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

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

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

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

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

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

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

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

Райс показал, что для каждого нетривиального класса C (который содержит некоторые, но не все r.e. множества) индексное множество E = {e: eth r.e. set W e is in C} имеет свойство, заключающееся в том, что либо проблема остановки, либо ее дополнение сводятся к E, то есть могут быть отображены с использованием many -один редукция до E (см. теорему Райса для более подробной информации). Но многие из этих наборов индексов даже сложнее, чем проблема остановки. Эти типы наборов можно классифицировать с помощью арифметической иерархии. Например, индексное множество FIN класса всех конечных множеств находится на уровне Σ 2, индексное множество REC класса всех рекурсивных множеств находится на уровне Σ 3, индексное множество COFIN всех конфинитных множеств также находится на уровне Σ 3, а индексное множество COMP класса всех полных по Тьюрингу множеств Σ 4. Эти уровни иерархии определены индуктивно, Σ n + 1 содержит только все множества, которые рекурсивно перечислимы относительно Σ n ; Σ 1 содержит рекурсивно перечислимые множества. Приведенные здесь наборы индексов являются полными даже для своих уровней, то есть все наборы на этих уровнях могут быть сведены в один ряд к данным наборам индексов.

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

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

Нумерация

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

Метод приоритета

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

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

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

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

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

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

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

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

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

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

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

В этом разделе теории рекурсии был проанализирован следующий вопрос: для фиксированных m и n с 0 < m < n, for which functions A is it possible to compute for any different n inputs x1, x 2,..., x n кортеж из n чисел y 1,y2,..., y n такой, что по крайней мере m из уравнений A (x k) = y k верны. Такие множества как известны (m, n) -рекурсивные числа. Первым важным результатом в этой ветви теории рекурсии является результат Трахтенброта о том, множество вычислимо, если оно (m, n) -рекурсивно для некоторых m, n с 2m>n. Другой, полурекурсивные множества Джокуша (которые уже были неофициально известны до того, как Джокуш представил их в 1968 году) являются примерами набора, который является (m, n) -рекурсивным тогда и только тогда, когда 2m < n + 1. There are uncountably many of these sets and also some recursively enumerable but noncomputable sets of this type. Later, Degtev established a hierarchy of recursively enumerable sets that are (1, n + 1)-recursive but not (1, n)-recursive. After a long phase of research by Russian scientists, this subject became repopularized in the west by Beigel's thesis on bounded queries, which linked frequency computation to the above-mentioned bounded reducibilities and other related notions. One of the major results was Kummer's Cardinality Theory which states that a set A is computable if and only if there is an n such that some algorithm enumerates for each tuple of n different numbers up to n many possible choices of the cardinality of this set of n numbers intersected with A; these choices must contain the true cardinality but leave out at least one false one.

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

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

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

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

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

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

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

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

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

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

Имя

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

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

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

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

См. Также

  • Философский портал

Примечания

Ссылки

Тексты для бакалавриата
Расширенные тексты
  • 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.
  • Нис, Андре (2009). Вычислимость и случайность. Издательство Оксфордского университета. ISBN 978-0-19-923076-1.
  • Odifreddi, P. (1989). Классическая теория рекурсии. Северная Голландия. ISBN 0-444-87295-7.
  • Odifreddi, P. (1999). Классическая теория рекурсии. II . Эльзевир. ISBN 0-444-50205-X.
  • Rogers, Jr., H. (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.
Обзорные статьи и коллекции
Исследовательские статьи и коллекции

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

На Викискладе есть материалы, связанные с Теория вычислимости.
Последняя правка сделана 2021-05-15 08:29:07
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте