stringtranslate.com

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

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

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

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

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

Теория вычислимости в математической логике традиционно фокусировалась на относительной вычислимости , обобщении вычислимости Тьюринга, определяемой с помощью оракульных машин Тьюринга , введенных Тьюрингом в 1939 году. [13] Оракульная машина Тьюринга — это гипотетическое устройство, которое, в дополнение к выполнению действий обычной машины Тьюринга, способно задавать вопросы оракулу , который является определенным набором натуральных чисел. Оракульная машина может задавать только вопросы вида «Входит ли 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 году Пост [14] задался вопросом, является ли каждое вычислимо перечислимое множество либо вычислимым, либо эквивалентным по Тьюрингу проблеме остановки, то есть не существует ли вычислимо перечислимого множества со степенью Тьюринга, промежуточной между этими двумя.

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

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

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

Многие недавние исследования степеней Тьюринга были сосредоточены на общей структуре множества степеней Тьюринга и множестве степеней Тьюринга, содержащих вычислимо перечислимые множества. Глубокая теорема Шора и Сламана [15] утверждает, что функция, отображающая степень x в степень ее скачка Тьюринга, определима в частичном порядке степеней Тьюринга. Обзор Амбоса-Списа и Фейера [16] дает обзор этого исследования и его исторического развития.

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

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

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

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

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

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

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

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

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

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

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

Нумерация

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

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

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

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

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

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

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

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

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

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

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

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

Эта ветвь теории вычислимости анализировала следующий вопрос: для фиксированных m и n с 0 <  m  <  n , для каких функций A возможно вычислить для любых различных n входных данных x 1 ,  x 2 , ...,  x n кортеж из n чисел y 1 , y 2 , ..., y n такой, что по крайней мере m из уравнений A ( x k ) = y k верны. Такие множества известны как ( m ,  n )-рекурсивные множества. Первым важным результатом в этой ветви теории вычислимости является результат Трахтенброта о том, что множество вычислимо, если оно ( m ,  n )-рекурсивно для некоторых m ,  n с 2 m  >  n . С другой стороны, полурекурсивные множества Джокуша (которые были известны неформально еще до того, как Джокуш ввел их в 1968 году) являются примерами множества, которое является ( m ,  n )-рекурсивным тогда и только тогда, когда 2m  <  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 году. [21] Эти обобщенные понятия включают сводимости, которые не могут быть выполнены машинами Тьюринга, но, тем не менее, являются естественными обобщениями сводимости Тьюринга. Эти исследования включают подходы к исследованию аналитической иерархии , которая отличается от арифметической иерархии тем, что допускает квантификацию по множествам натуральных чисел в дополнение к квантификации по отдельным числам. Эти области связаны с теориями вполне упорядоченных множеств и деревьев; например, множество всех индексов вычислимых (недвоичных) деревьев без бесконечных ветвей является полным для уровня аналитической иерархии. Как сводимость по Тьюрингу, так и гиперарифметическая сводимость важны в области эффективной дескриптивной теории множеств . Еще более общее понятие степеней конструктивности изучается в теории множеств .

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

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

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

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

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

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

Имя

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

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

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

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

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

Примечания

  1. ^ Справочник по рекурсивной математике [1] охватывает многие известные результаты в этой области.
  2. ↑ Многие из этих основополагающих статей собраны в книге «Неразрешимое» (1965) под редакцией Мартина Дэвиса .
  3. ^ Список неразрешимых проблем дает дополнительные примеры.
  4. ^ Список открытых проблем поддерживается Джозефом Миллером и Андре Нисом, он опубликован на домашней странице Андре Ниса.
  5. ^ Поисковые запросы MathSciNet по таким заголовкам, как « computably enumerable » и «ce», показывают, что многие статьи были опубликованы как с использованием этой, так и с использованием другой терминологии.

Ссылки

  1. ^ Ершов, Юрий Леонидович ; Гончаров, Сергей Савостьянович [в Викиданных] ; Нероде, Анил ; Реммель, Джеффри Б. (1998). Справочник по рекурсивной математике . Северная Голландия . ISBN 0-7204-2285-X.
  2. ^ Радо, Тибор (май 1962). «О невычислимых функциях». Bell System Technical Journal . 41 (3): 877–884. doi :10.1002/j.1538-7305.1962.tb00480.x.
  3. ^ Soare, Robert Irving (2011-12-22). "Computability Theory and Applications: The Art of Classical Computability" (PDF) . Department of Mathematics . University of Chicago . Архивировано (PDF) из оригинала 2022-06-30 . Получено 2017-08-23 .
  4. ^ ab Kleene, Stephen Cole (1952). Введение в метаматематику . North-Holland . стр. 300, 376. ISBN 0-7204-2103-9.
  5. ^ ab Davis, Martin , ed. (2004) [1965]. Неразрешимое: основные статьи о неразрешимых предложениях, неразрешимых проблемах и вычислимых функциях. Dover Publications, Inc. стр. 84. ISBN 978-0-486-43228-1. стр. 84: Курт Гёдель (1946): Тарский подчеркнул в своей лекции (и я думаю справедливо) большую важность концепции общей рекурсивности (или вычислимости Тьюринга). Мне кажется, что эта важность во многом обусловлена ​​тем фактом, что с помощью этой концепции впервые удалось дать абсолютное понятие интересному эпистемологическому понятию, т. е. не зависящему от выбранного формализма.
  6. ^ Гедель, Курт (1990). "[Гедель (1946)]". В Feferman, Solomon ; et al. (ред.). Kurt Gödel Publications 1938–1974 Volume II . Vol. II. Нью-Йорк, США: Oxford University Press . стр. 144ff. ISBN 978-0-19-514721-6. стр. 150: Точнее: функция целых чисел вычислима в любой формальной системе, содержащей арифметику, тогда и только тогда, когда она вычислима в арифметике, где функция f называется вычислимой в S , если в S существует вычислимый терм, представляющий f .(Примечание. В этот том также включена статья Курта Гёделя 1946 года (с комментариями Чарльза Парсонса на стр. 144 и далее). В этом издании 1990 года цитируемая сноска добавлена ​​Гёделем на стр. 150 (которая также была добавлена ​​к переизданию Гёделя в сборнике Дэвиса 1965 года).)
  7. ^ Чёрч, Алонзо (1936a). «Неразрешимая проблема элементарной теории чисел». American Journal of Mathematics . 58 (2): 345–363. doi :10.2307/2371045. JSTOR  2371045.Перепечатано в Дэвисе в 1965 году.
  8. ^ Чёрч, Алонзо (1936b). «Заметка о проблеме Entscheidungsproblem». Журнал символической логики . 1 (1): 40–41. doi :10.2307/2269326. JSTOR  2269326. S2CID  42323521.Перепечатано в Дэвисе в 1965 году.
  9. ^ ab Turing, Alan Mathison (1937) [1936]. «О вычислимых числах с приложением к Entscheidungsproblem». Труды Лондонского математического общества . 2. 42 (1): 230–265. doi :10.1112/plms/s2-42.1.230. S2CID  73712. Turing, Alan Mathison (1938). «О вычислимых числах с приложением к Entscheidungsproblem. Исправление» (PDF) . Труды Лондонского математического общества . 2. 43 (1): 544–546. doi :10.1112/plms/s2-43.6.544. Архивировано (PDF) из оригинала 2022-07-18 . Получено 2022-08-08 .Перепечатано в Дэвисе в 1965 году.
  10. ^ Катланд, Найджел Дж. (1980). Вычислимость, введение в теорию рекурсивных функций . Cambridge University Press . ISBN 0-521-29465-7.
  11. ^ ab Soare, Robert Irving (1987). Рекурсивно перечислимые множества и степени . Перспективы математической логики. Springer-Verlag . ISBN 0-387-15299-7.
  12. ^ ab Soare, Robert Irving (1996). "Вычислимость и рекурсия" (PDF) . Bulletin of Symbolic Logic . 2 (3): 284–321. doi :10.2307/420992. JSTOR  420992. S2CID  5894394.
  13. ^ Тьюринг, Алан Матисон (1939). «Системы логики, основанные на ординалах». Труды Лондонского математического общества . 2. 45 (1): 161–228. doi :10.1112/plms/s2-45.1.161. hdl : 21.11116/0000-0001-91CE-3 .Перепечатано в Дэвисе в 1965 году.
  14. ^ abc Post, Эмиль Леон (1944). «Рекурсивно перечислимые множества положительных целых чисел и проблемы их решения». Бюллетень Американского математического общества . 50 (5): 284–316. doi : 10.1090/S0002-9904-1944-08111-1 . MR  0010514.Перепечатано в Дэвисе в 1965 году.
  15. ^ Шор, Ричард Арнольд ; Сламан, Теодор Аллен (1999). «Определение скачка Тьюринга». Mathematical Research Letters . 6 (6): 711–722. doi : 10.4310/mrl.1999.v6.n6.a10 . ISSN  1073-2780. MR  1739227.
  16. ^ ab Ambos-Spies, Klaus; Fejer, Peter A. (2014). "Степени неразрешимости" (PDF) . В Siekmann, Jörg H. (ред.). Computational Logic . Handbook of the History of Logic. Vol. 9. Amsterdam: Elsevier/North-Holland. pp. 443–494. doi :10.1016/B978-0-444-51624-4.50010-1. ISBN 978-0-444-51624-4. MR  3362163. Архивировано из оригинала (PDF) 2013-04-20.
  17. ^ ab Simpson, Steven George (1999). Подсистемы арифметики второго порядка . Springer-Verlag . ISBN 3-540-64882-8.
  18. ^ Харрингтон, Лео Энтони ; Соаре, Роберт Ирвинг (1991). «Программа Поста и неполные рекурсивно перечислимые множества». Труды Национальной академии наук США . 88 (22): 10242–10246. Bibcode : 1991PNAS...8810242H. doi : 10.1073 /pnas.88.22.10242 . PMC 52904. PMID  11607241. 
  19. ^ Soare, Robert Irving (1974). «Автоморфизмы решетки рекурсивно перечислимых множеств. Часть I: Максимальные множества». Annals of Mathematics . 100 (1): 80–120. doi :10.2307/1970842. JSTOR  1970842.
  20. ^ Сламан, Теодор Аллен ; Вудин, Уильям Хью (1986). «Определимость в степенях Тьюринга». Illinois Journal of Mathematics . 30 (2): 320–334. doi : 10.1215/ijm/1256044641 . MR  0840131.
  21. ^ Сакс, Джеральд Энох (1990). Теория высшей рекурсии . Springer-Verlag . ISBN 3-540-19305-7.
  22. ^ Орпонен, Пекка (1997). «Обзор теории непрерывных вычислений». Достижения в области алгоритмов, языков и сложности . стр. 209–224. CiteSeerX 10.1.1.53.1991 . doi :10.1007/978-1-4613-3394-4_11. ISBN  978-1-4613-3396-8.
  23. ^ Мур, Крис (1996). «Теория рекурсии на вещественных числах и вычислениях в непрерывном времени». Теоретическая информатика . 162 (1): 23–44. CiteSeerX 10.1.1.6.5519 . doi :10.1016/0304-3975(95)00248-0. 
  24. ^ Фэртлоу, Мэтт; Уэйнер, Стэнли С. (1998). «Иерархии доказуемо рекурсивных функций». В Buss, Samuel R. (ред.). Справочник по теории доказательств . Elsevier . стр. 149–208. ISBN 978-0-08-053318-6.
  25. ^ Фортнау, Лэнс Джереми (2004-02-15). «Является ли это рекурсивным, вычислимым или разрешимым?». Архивировано из оригинала 2022-08-07 . Получено 2018-03-22 .
  26. ^ Симпсон, Стивен Джордж (1998-08-24). "Что такое теория вычислимости?". Список рассылки FOM . Архивировано из оригинала 2021-12-18 . Получено 2006-01-09 .
  27. ^ Фридман, Харви (1998-08-28). "Переименование теории рекурсии". Список адресов электронной почты FOM . Архивировано из оригинала 2022-03-01 . Получено 2006-01-09 .
  28. ^ Роджерс, Хартли-младший (1987). Теория рекурсивных функций и эффективная вычислимость (2-е изд.). MIT Press . ISBN 0-262-68052-1.

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

Тексты для бакалавриата
Расширенные тексты
Обзорные работы и сборники
Научные работы и сборники

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

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