Теория альфа-рекурсии
В теории рекурсии теория рекурсии α является обобщением теории рекурсии на подмножества допустимых ординалов. . Допустимое множество замкнуто при функции, где обозначает ранг конструктивной иерархии Геделя . является допустимым ординалом, если является моделью теории множеств Крипке–Платека . Далее считается фиксированным.
Определения [ править ]
Объекты исследования в рекурсия является подмножеством . Говорят, что эти множества обладают некоторыми свойствами:
- Набор Говорят, что это -рекурсивно-перечисляемый, если это так определяемый более , возможно, с параметрами из в определении. [1]
- А есть -рекурсивно, если и A, и (его относительное дополнение в ) являются -рекурсивно-перечисляемый. Примечательно, что -рекурсивные множества являются членами по определению .
- Члены называются -конечны и играют ту же роль, что и конечные числа в классической теории рекурсии.
- Члены называются -арифметика . [2]
Существуют также некоторые похожие определения отображения функций. к : [3]
- функция Частичная из к является -рекурсивно-перечисляемый , или -частичная рекурсия , [4] тогда и только тогда, когда его график -определяемый на .
- Частичная функция из к является -рекурсивный тогда и только тогда, когда его график -определяемый на . Как и в случае с классической теорией рекурсии, любая сумма -рекурсивно-перечислимая функция является -рекурсивный.
- Кроме того, частичная функция из к является -арифметика тогда и только тогда, когда существует некоторое такая, что график функции имеет вид -определяемый на .
Можно провести дополнительные связи между теорией рекурсии и теорией α-рекурсии, хотя явные определения для их формализации, возможно, еще не были написаны:
- Функции -определяемый в играют роль, аналогичную роли примитивно-рекурсивных функций . [3]
Мы говорим, что R является процедурой редукции, если она рекурсивно перечислим и каждый член R имеет вид где H , J , K все α-конечны.
A Говорят, что является α-рекурсивным в B, если существуют процедуры сокращения, такие, что:
Если A рекурсивно в B, это пишется . По этому определению A рекурсивна в ( пустое множество ) тогда и только тогда, когда A рекурсивно. Однако то, что A рекурсивно в B, не эквивалентно тому, что A является .
Мы говорим, что A регулярен, если или, другими словами, если каждая начальная часть A является α-конечной.
Работа в альфа-рекурсии [ править ]
Теорема Шора о расщеплении: пусть A будет рекурсивно перечислимые и регулярные. Существуют рекурсивно перечислимый такой, что
Теорема Шора о плотности: пусть A , C — α-регулярные рекурсивно перечислимые множества такие, что то существует регулярное α-рекурсивно перечислимое множество B такое, что .
Барвайз доказал, что множества -определяемый на это именно наборы -определяемый на , где обозначает следующий допустимый порядковый номер выше , и принадлежит к иерархии Леви . [5]
Существует обобщение предельной вычислимости на частичный функции. [6]
Компьютерная интерпретация -рекурсия существует, используя " -Машины Тьюринга» с двухсимвольной лентой длины , что на шагах предельных вычислений принимается нижний предел содержимого ячейки, состояния и положения головки. Для допустимого , набор является -рекурсивный тогда и только тогда, когда он вычислим -машина Тьюринга и является -рекурсивно-перечисляемый if представляет собой область значений функции, вычислимой -Машина Тьюринга. [7]
Открытой (по состоянию на 2019 год) проблемой теории α-рекурсии является гипотеза о вложении допустимых ординалов, а именно: для всех ли допустимых , автоморфизмы -степени нумерации вкладываются в автоморфизмы -перечисление степеней. [8]
с анализом Связь
Некоторые результаты в -рекурсию можно перевести в аналогичные результаты относительно арифметики второго порядка . Это из-за отношений имеет с разветвленной аналитической иерархией аналог для языка арифметики второго порядка, состоящего из наборов целых чисел. [9]
Фактически, когда мы имеем дело только с логикой первого порядка, соответствие может быть настолько близким, что для некоторых результатов по , арифметическая иерархия и иерархия Леви могут стать взаимозаменяемыми. Например, множество натуральных чисел можно определить с помощью формула, если это -определяемый на , где — уровень иерархии Леви. [10] В более общем смысле, определимость подмножества ω над HF с формула совпадает с ее арифметической определимостью с помощью формула. [11]
Ссылки [ править ]
- Джеральд Сакс, Теория высшей рекурсии , Springer Verlag, 1990 https://projecteuclid.org/euclid.pl/1235422631
- Роберт Соаре, Рекурсивно перечислимые множества и степени , Springer Verlag, 1987 https://projecteuclid.org/euclid.bams/1183541465
- Кейт Дж. Девлин, Введение в тонкую структуру конструктивной иерархии (стр. 38), North-Holland Publishing, 1974 г.
- Дж. Барвайз, Допустимые множества и структуры . 1975 год
Встроенные ссылки [ править ]
- ^ П. Кепке, Б. Зейферт, Порядковые машины и допустимая теория рекурсии (препринт) (2009, стр.315). По состоянию на 12 октября 2021 г.
- ^ Р. Гостанян, Следующий допустимый порядковый номер , Анналы математической логики 17 (1979). По состоянию на 1 января 2023 г.
- ^ Jump up to: Перейти обратно: а б Сребрный, Мариан, Относительно конструктивные транзитивные модели (1975, стр.165). По состоянию на 21 октября 2021 г.
- ^ В. Рихтер, П. Аксель, « Индуктивные определения и отражающие свойства допустимых ординалов » (1974), стр.30. По состоянию на 7 февраля 2023 г.
- ^ Т. Араи, Теория доказательств для теорий ординалов - I: рекурсивно ординалы Мало (1998). стр.2
- ^ С.Г. Симпсон, «Теория степеней допустимых ординалов», стр. 170–171. Появилось в книге Дж. Фенстада, П. Хинмана, «Обобщенная теория рекурсии: материалы симпозиума в Осло 1972 года» (1974), ISBN 0 7204 22760.
- ^ П. Кёпке, Б. Зейферт, « Порядковые машины и допустимая теория рекурсии ». Анналы чистой и прикладной логики, том. 160 (2009), стр. 310–318.
- ^ Д. Натингга, Теорема вложения для группы автоморфизмов степеней α-перечисления (стр. 155), докторская диссертация, 2019.
- ^ П. Д. Уэлч, Разветвленная аналитическая иерархия с использованием расширенной логики (2018, стр. 4). Доступ 8 августа 2021 г.
- ^ Дж. Э. Сакс, Теория высшей рекурсии (стр. 152). «Перспективы логики», Ассоциация символической логики.
- ^ П. Одифредди, Классическая теория рекурсии (1989), теорема IV.3.22.