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

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

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

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

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

Вычислимые и невычислимые множества [ править ]

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

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

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

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

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

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

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

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

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

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

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

Области исследований [ править ]

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

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

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

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

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

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

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

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

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

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

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

Другие сводимости [ править ]

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

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

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

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

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

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

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

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

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

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

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

Теорема Райса и арифметическая иерархия [ править ]

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

Обратная математика [ править ]

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

Нумерация [ править ]

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

Метод приоритета [ править ]

Более подробное объяснение см. В разделе «Проблема Поста и метод приоритета» статьи « Степень Тьюринга» .

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

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

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

Когда Пост определил понятие простого множества как набора с бесконечным дополнением, не содержащего никакого бесконечного набора, он начал изучать структуру рекурсивно перечислимых множеств при включении. Эта решетка стала хорошо изученной структурой. Рекурсивные множества могут быть определены в этой структуре по основному результату, заключающемуся в том, что набор является рекурсивным тогда и только тогда, когда набор и его дополнение рекурсивно перечислимы. Бесконечные наборы всегда имеют бесконечные рекурсивные подмножества; но с другой стороны, простые множества существуют, но не имеют бесконечного рекурсивного надмножества. Пост (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 г. была проведена недавняя исследовательская конференция в этой области ^[4], и список открытых проблем ^[5] поддерживается Джозефом Миллером и Андре Нисом.

Вычисление частоты [ править ]

Этот раздел теории рекурсии проанализировал следующий вопрос: для фиксированных 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) являются примерами множества, ( т ,  п ) -recursive тогда и только тогда , когда 2 м  <  п + 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 , если М узнает весь п в S . Основные результаты заключаются в том, что все рекурсивно перечислимые классы функций доступны для обучения, в то время как класс REC всех вычислимых функций не обучается. Было рассмотрено множество связанных моделей, а также изучение классов рекурсивно перечислимых множеств на основе положительных данных является темой, изученной в новаторской статье Голда, опубликованной в 1967 году.

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

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

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

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

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

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

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

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

Имя [ редактировать ]

Область математической логики, имеющая дело с вычислимостью и ее обобщениями, с самого начала называлась «теорией рекурсии». Роберт И. Соар , видный исследователь в этой области, предложил (Soare 1996) вместо этого называть эту область "теорией вычислимости". Он утверждает, что терминология Тьюринга с использованием слова «вычислимый» более естественна и более понятна, чем терминология с использованием слова «рекурсивный», введенная Клини. Многие современные исследователи начали использовать эту альтернативную терминологию. ^[6] Эти исследователи также используют терминологию, такую ​​как частично вычислимая функция и вычислимо перечислимое ( ce ) множество вместочастичная рекурсивная функция и рекурсивно перечислимый ( пере ) набор . Однако не все исследователи были убеждены, как объяснили Фортноу ^[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) 20 апреля 2013 года . Проверено 27 октября 2006 . Неопубликованный препринт.
• Эндертон, Х. (1977). «Элементы теории рекурсии». В Барвайз, Дж. (Ред.). Справочник по математической логике . Северная Голландия. С.  527–566 . ISBN 0-7204-2285-X.
• Ершов Ю.Л .; Гончаров, СС; Nerode, A .; Реммель, Дж. Б. (1998). Справочник по рекурсивной математике . Северная Голландия. ISBN 0-7204-2285-X.
• Fairtlough, M .; Уайнер, СС (1998). «Иерархии доказуемо рекурсивных функций» . In Buss, SR (ред.). Справочник по теории доказательства . Эльзевир. С. 149–208. ISBN 978-0-08-053318-6.
• Соаре, Р.И. (1996). «Вычислимость и рекурсия» (PDF) . Вестник символической логики . 2 (3): 284–321. DOI : 10.2307 / 420992 . JSTOR  420992 .

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

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

Внешние ссылки [ править ]

Викискладе есть медиафайлы по теории вычислимости .

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