Alexander Kuklev (akuklev) wrote,
Alexander Kuklev
akuklev

Чего-то я не понимаю. Согласно статье "Recursiveness of initial segments of Kleen's O" (Carl Jockusch, Jr., 1973) для каждого рекурсивного ординала ф существует рекурсивная запись всех ординалов ниже его. (Т.е. некая грамматика G и заданное на ней вычислимой функцией отношение частичного порядка R, порядкоизоморфное ф. Т.е. каждому ординалу ниже ф соответствует выражение G.)

А где-то раньше я читал, что максимальным ординалом для которого возможна сюрьективная рекурсивная запись является малый ординал Веблена, а записи более высоких ординалов неизбежно пропускают по дороге какие-то ординалы (т.е. речь вообще идёт о системах записи другого плана: тут ординалы задаются не через отношения порядка на конкретных конструктивных объектах, а через фундаментальные последовательности.).

Upd: кажется факт про ординал Веблена получается, если говорить не про вообще рекурсивные, а только примитивно-рекурсивные сюрьективные системы записи.
Subscribe

  • (no subject)

    Встретил фотографию толпы футбольных фанатов, и она меня скорее напугала, у меня уж точно нет желания быть там среди них. Но внезапно я понял, что…

  • Прогресс

    Десять дней назад, вторая ступень SpaceX'овского корабля Starship своим ходом слетала своим ходом на десять километров вверх, и усмепшно приземлилась…

  • О водосбережении

    Как известно, питьевая вода во многих странах дефицитный ресурс. И даже в дождливой Германии летом иногда случаются засухи, в результате которых она…

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 0 comments