Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

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

Гиперарифметические множества и определимость [ править ]

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

Гиперарифметические множества и повторные скачки Тьюринга: гиперарифметическая иерархия [ править ]

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

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

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

  • Число 0 - это обозначение порядкового номера 0.
  • Если n - обозначение порядкового номера λ, то это обозначение λ + 1;
  • Предположим, что δ - предельный ординал . Отметка при б является числом вида , где е является показателем общей вычислимой функции таким образом, что для каждого п , является обозначением порядкового Х п меньше б , и δ является SUP множества .

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

Порядковые обозначения используются для определения повторных переходов Тьюринга. Это наборы натуральных чисел, обозначенные для каждого . Предположим, что δ имеет обозначение e . Набор определяется с помощью e следующим образом.

  • Если δ = 0, то - пустое множество.
  • Если δ = λ + 1, то это скачок Тьюринга . Обозначения и обычно используются для и соответственно.
  • Если δ - предельный ординал, пусть будет последовательность порядковых номеров меньше δ, заданная обозначением e . Набор задается правилом . Это эффективное соединение множеств .

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

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

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

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

если существует такое i , что f ( i )> 0,
если не существует такого i , что f ( i )> 0.

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

Пример: набор истинности арифметики [ править ]

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

Фундаментальные результаты [ править ]

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

Результаты о полноте также имеют фундаментальное значение для теории. Множество натуральных чисел является полным , если он находится на уровне от аналитической иерархии , и каждого набора натуральных чисел многие одна приводимы к нему. Определение полного подмножества пространства Бэра ( ) аналогично. Завершено несколько наборов, связанных с теорией гиперарифметики :

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

Результаты, известные как ограничивающие, следуют из этих результатов для полноты. Для любого набора S порядковых обозначений существует такой, что каждый элемент S является обозначением для порядкового номера меньше, чем . Для любого подмножества T пространства Бэра, состоящего только из характеристических функций порядков скважин, существует такое, что каждый ординал, представленный в T , меньше, чем .

Релятивизированная гиперарифметичность и гиперстепени [ править ]

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

Определение можно также относить к произвольному набору натуральных чисел. Единственное изменение в определении состоит в том, что он определяется как X, а не как пустое множество, так что это скачок Тьюринга X и так далее. Вместо того, чтобы завершать иерархию относительно X, проходит через все порядковые номера меньше, чем .

Релятивизированная гиперарифметическая иерархия используется для определения гиперарифметической сводимости . Для заданных множеств X и Y мы говорим тогда и только тогда, когда существует такое, что X сводится к Тьюрингу . Если и то запись используется для обозначения Х и Y являются hyperarithmetically эквивалентны . Это более грубое отношение эквивалентности, чем эквивалентность по Тьюрингу ; например, каждый набор натуральных чисел гиперарифметически эквивалентен своему скачку Тьюринга.но не эквивалент Тьюринга прыжку Тьюринга. Классы эквивалентности гиперарифметической эквивалентности известны как гиперстепени .

Функция , которая принимает множество X к известна как hyperjump по аналогии со скачком Тьюринга. Установлены многие свойства гиперскачка и гиперстепеней. В частности, известно, что проблема Поста для гиперстепеней имеет положительный ответ: для каждого множества X натуральных чисел существует множество Y таких натуральных чисел, что .

Обобщения [ править ]

Гиперарифметическая теория обобщается теорией α-рекурсии , которая представляет собой исследование определимых подмножеств допустимых ординалов . Гиперарифметическая теория - это частный случай, когда α есть .

Связь с другими иерархиями [ править ]


Ссылки [ править ]

  • Х. Роджерс мл., 1967. Теория рекурсивных функций и эффективная вычислимость , второе издание 1987 г., MIT Press. ISBN  0-262-68052-1 (мягкая обложка), ISBN 0-07-053522-1 
  • Г. Сакс, 1990. Высшая теория рекурсии , Springer-Verlag. ISBN 3-540-19305-7 
  • С. Симпсон, 1999. Подсистемы арифметики второго порядка , Springer-Verlag.
  • CJ Ash, JF Knight , 2000. Вычислимые структуры и гиперарифметическая иерархия , Elsevier. ISBN 0-444-50072-3 

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

  • Теория описательных множеств . Примечания Дэвида Маркера, Иллинойсский университет в Чикаго. 2002 г.
  • Математическая логика II . Примечания Дага Нормана, Университет Осло. 2005 г.