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

• Определение и свойства α-рекурсии

  • α-рекурсия – это форма рекурсии, которая использует порядковые числа для определения вычислимости. 
  • α-рекурсия позволяет определить вычислимость множеств, используя порядковые числа, а не натуральные числа. 
  • Множество A является α-рекурсивным, если существует вычислимая функция f такая, что A = f(α). 

• Примеры и теоремы

  • Множество натуральных чисел является α-рекурсивным. 
  • Множество всех множеств, которые не являются α-рекурсивными, также является α-рекурсивным. 
  • Теорема о расщеплении утверждает, что каждое α-рекурсивно перечислимое множество может быть разделено на два непересекающихся множества, одно из которых не является α-рекурсивным. 
  • Теорема о плотности утверждает, что для двух α-рекурсивно перечислимых множеств A и C существует α-рекурсивно перечислимое множество B такое, что A < α B < α C. 

• Связь с анализом и вычислительная интерпретация

  • α-рекурсия связана с аналитической иерархией и арифметикой второго порядка. 
  • Вычислительная интерпретация α-рекурсии использует α-машины Тьюринга для вычисления с использованием порядковых чисел. 

• Гипотеза о вложении

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

• Рекомендации и встроенные ссылки

  • В статье приведены ссылки на работы Джеральда Сакса, Роберта Соара, Кита Джей. Девлина и других авторов, связанные с теорией α-рекурсии.