Барная рекурсия - Bar recursion

Барная рекурсия является обобщенной формой рекурсии, разработанной К. Спектором в его статье 1962 года.[1] Это связано с барная индукция так же, как примитивная рекурсия относится к обычным индукция, или трансфинитная рекурсия относится к трансфинитная индукция.

Техническое определение

Позволять V, р, и О быть типы, и я быть любым натуральным числом, представляющим последовательность параметров, взятых из V. Тогда последовательность функций ж функций жп от Vя+п → р к О определяется полосовой рекурсией из функций Lп : р → О и B с участием Bп : ((Vя+п → р) Икс (Vп → р)) → О если:

  • жп((λα:Vя+п)р) = Lп(р) для любого р достаточно долго, чтобы Lп+k на любом продлении р равно Lп. Предполагая L - непрерывная последовательность, должны быть такие р, потому что непрерывная функция может использовать только конечное количество данных.
  • жп(п) = Bп(п, (λИкс:V)жп+1(Кот(п, Икс))) для любого п в Vя+п → р.

Здесь «кот» - это конкатенация функция, отправка п, Икс к последовательности, которая начинается с п, и имеет Икс как его последний срок.

(Это определение основано на определении Эскардо и Оливы.[2])

При условии, что для любой достаточно длинной функции (λα)р типа Vя → р, существует некоторое п с участием Lп(р) = Bп((λα)р, (λИкс:V)Lп+1(р)) правило индукции стержня гарантирует, что ж четко определено.

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

Принципы барной индукции и барной рекурсии являются интуиционистскими эквивалентами аксиомы зависимый выбор.[3]

использованная литература

  1. ^ К. Спектор (1962). «Доказуемо рекурсивные функционалы анализа: доказательство непротиворечивости анализа путем расширения принципов современной интуиционистской математики». В Ф. Д. Э. Деккер (ред.). Теория рекурсивных функций: Учеб. Симпозиумы по чистой математике. 5. Американское математическое общество. С. 1–27.
  2. ^ Мартин Эскардо; Пауло Олива. «Функции выбора, линейная рекурсия и обратная индукция» (PDF). Математика. Struct. в Comp.Science.
  3. ^ Джереми Авигад; Соломон Феферман (1999). «VI: Функциональная (« Диалектика ») интерпретация Гёделя». В С. Р. Басс (ред.). Справочник по теории доказательств (PDF).