Jump to content

Теория альфа-рекурсии

В теории рекурсии теория рекурсии α является обобщением теории рекурсии на подмножества допустимых ординалов. . Допустимое множество замкнуто при функции, где обозначает ранг конструктивной иерархии Геделя . является допустимым ординалом, если является моделью теории множеств Крипке–Платека . Далее считается фиксированным.

Определения [ править ]

Объекты исследования в рекурсия является подмножеством . Говорят, что эти множества обладают некоторыми свойствами:

  • Набор Говорят, что это -рекурсивно-перечисляемый, если это так определяемый более , возможно, с параметрами из в определении. [1]
  • А есть -рекурсивно, если и A, и (его относительное дополнение в ) являются -рекурсивно-перечисляемый. Примечательно, что -рекурсивные множества являются членами по определению .
  • Члены называются -конечны и играют ту же роль, что и конечные числа в классической теории рекурсии.
  • Члены называются -арифметика . [2]

Существуют также некоторые похожие определения отображения функций. к : [3]

  • функция Частичная из к является -рекурсивно-перечисляемый , или -частичная рекурсия , [4] тогда и только тогда, когда его график -определяемый на .
  • Частичная функция из к является -рекурсивный тогда и только тогда, когда его график -определяемый на . Как и в случае с классической теорией рекурсии, любая сумма -рекурсивно-перечислимая функция является -рекурсивный.
  • Кроме того, частичная функция из к является -арифметика тогда и только тогда, когда существует некоторое такая, что график функции имеет вид -определяемый на .

Можно провести дополнительные связи между теорией рекурсии и теорией α-рекурсии, хотя явные определения для их формализации, возможно, еще не были написаны:

Мы говорим, что 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]

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

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

  1. ^ П. Кепке, Б. Зейферт, Порядковые машины и допустимая теория рекурсии (препринт) (2009, стр.315). По состоянию на 12 октября 2021 г.
  2. ^ Р. Гостанян, Следующий допустимый порядковый номер , Анналы математической логики 17 (1979). По состоянию на 1 января 2023 г.
  3. ^ Jump up to: Перейти обратно: а б Сребрный, Мариан, Относительно конструктивные транзитивные модели (1975, стр.165). По состоянию на 21 октября 2021 г.
  4. ^ В. Рихтер, П. Аксель, « Индуктивные определения и отражающие свойства допустимых ординалов » (1974), стр.30. По состоянию на 7 февраля 2023 г.
  5. ^ Т. Араи, Теория доказательств для теорий ординалов - I: рекурсивно ординалы Мало (1998). стр.2
  6. ^ С.Г. Симпсон, «Теория степеней допустимых ординалов», стр. 170–171. Появилось в книге Дж. Фенстада, П. Хинмана, «Обобщенная теория рекурсии: материалы симпозиума в Осло 1972 года» (1974), ISBN 0 7204 22760.
  7. ^ П. Кёпке, Б. Зейферт, « Порядковые машины и допустимая теория рекурсии ». Анналы чистой и прикладной логики, том. 160 (2009), стр. 310–318.
  8. ^ Д. Натингга, Теорема вложения для группы автоморфизмов степеней α-перечисления (стр. 155), докторская диссертация, 2019.
  9. ^ П. Д. Уэлч, Разветвленная аналитическая иерархия с использованием расширенной логики (2018, стр. 4). Доступ 8 августа 2021 г.
  10. ^ Дж. Э. Сакс, Теория высшей рекурсии (стр. 152). «Перспективы логики», Ассоциация символической логики.
  11. ^ П. Одифредди, Классическая теория рекурсии (1989), теорема IV.3.22.
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 87a51d32ff19e8fc92387ea16a46d45e__1706182800
URL1:https://arc.ask3.ru/arc/aa/87/5e/87a51d32ff19e8fc92387ea16a46d45e.html
Заголовок, (Title) документа по адресу, URL1:
Alpha recursion theory - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)