Alexander Kuklev (akuklev) wrote,
Alexander Kuklev
akuklev

Category:

Вопрос математикам и информатикам

Есть вот примитивно-рекурсивные функции, они очень простые и заведомо тотальные.
Примитивно-рекурсивные функции классифицируются по скорости роста в т.н. иерархию Грегорчука:
Сложение, умножение, возведение в степень, тетрация и дальнейшие ступени итерированного инкремента (стрелки Кнута).

Теория, осознающая полноту max(x, y) имеет силу ω
Теория, осознающая полноту инкремента имеет силу ω∙2.
Теория, осознающая полноту сложения имеет силу ω2.
Теория, осознающая полноту возведения в степень имеет силу ω3.
Теория, осознающая полноту тетрации в степень имеет силу ω4.
...
Примитивно-рекурсивная арифметика имеет силу ωω.

Далеко не все “интересные на практике” функции примитивно-рекурсивны, однако практически все high order primitive recursive, не знаю как это называется. В общем функции, определённые через примитивную рекурсию высшего порядка. Это функции, тотальность которых устанавливается при помощи системы типов Gödel T, в определённом смысле это всё ещё финитизм. Таковы функция Аккермана и все функции, определяемые цепной стрелочной записью Конвея. Это позволяет расширить иерархию Грегорчука до иерархии Вайнера:

Теория, осознающая полноту стрелок Конвея длины n имеет силу ωn.
Теория, осознающая полноту стрелок Конвея любой длины имеет силу ωω.
Теория, осознающая полноту двумерных стрелок Конвея любого размера имеет силу ωωω.
Теория, осознающая полноту стрелок Конвея любой размерности и любого размера имеет силу ε0 = ωωωω ·..

Насколько я слышал Gödel T (правда ли это?), Gödel T имеет силу ε0, так что (обобщённые) стрелки Конвея классифицируют в иерархию по скорости роста все высшепорядково-примитивно-рекурсивные функции.

Зависимые системы типов и другие “наиболее мощные, но всё ещё конструктивные” системы вроде ATR0 имеют силу Γ0, что значительно больше ε0. То есть стало быть там можно доказать например полноту функции Гудштейна (см. пост avva/“Геркулес и Гидра”). Кстати, как?

Я себе этой раньше как-то не отдавал отчёта, что Γ0-то сильно больше, чем ε0 и упорно думал, что все Γ-вычислимые функции расслаиваются обобщёнными стрелками Конвея. Они все конечно растут медленее функции Фридмана* TREE, но как себе конструктивно представить иерархию, классифицирующую их скорости роста?

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.
  • 10 comments

  • (no subject)

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

  • Прогресс

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

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

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