Вычислимый порядковый номер
-
Определение вычислимых ординалов
- Вычислимый ординал α называется рекурсивным, если существует упорядоченное подмножество натуральных чисел с типом order α.
- ω является вычислимым ординалом.
- Следующий за вычислимым ординалом также является вычислимым, а множество всех вычислимых ординалов замкнуто вниз.
-
Ординал Черча-Клини
- Высший из вычислимых ординалов называется ординалом Черча-Клини и обозначается ω1CK.
- Ординал Черча-Клини является предельным ординалом.
- Вычислимый ординал α меньше ω1CK тогда и только тогда, когда α является вычислимым.
-
Счетность вычислимых ординалов
- Существует только счетное число вычислимых ординалов, так как существует только счетное число вычислимых соотношений.
- Ординал ω1CK является счетным.
-
Система Клини и вычислимые ординалы
- Вычислимые ординалы — это ординалы, которые имеют порядковое обозначение в системе Клини.
-
Дополнительные ресурсы
- Ссылки на книги и статьи по теории рекурсивных функций и эффективной вычислимости.
- Указание на возможность расширения статьи для Википедии.
Полный текст статьи: