Alexander Kuklev (akuklev) wrote,
Alexander Kuklev
akuklev

Category:

Зачем нужна индукция-рекурсия и зачем вселенные Mahlo

Теорема о проблеме останова говорит нам, что на чистых тотальных языках невозможно написать функцию (тотальную и чистую) eval, способную привести любое выражение языка к нормальной форме. Коль скоро нет eval'а, хочется хотя бы иметь вот такие свойства замкнутости:
1) если на языке можно написать функцию f : X -> Expr[T], то можно написать и функцию f' : X -> T, являющуюся метатеоретически f = eval ∘ f.
2) если на (чистом, тотальном, строго типизированном) языке L можно написать программу generate_type : X -> TypeExpression, вычисляющую для каждого x : X, где X индуктивный тип, корректное выражение языка L, обозначающее тип, то можно написать и найдётся такая вселенная U и такая функция generate_type', что метатеоретически generate_type' = eval ∘ generate_type.

Первое условие довольно тривиально выполняется во всех вариантах и расширениях MLTT, а вот второе не совсем. Если условие 2 ослабить до ситуации, когда generate_type возвращает типовые выражения, живущие во вселенной не более чем фиксированного уровня, то для наличия такой замкнутости достаточно наличия индукции-рекурсии в языке (интересно было бы охарактеризовать, какая именно форма индукции рекурсии необходима и достаточна для этого), а вот если без такого ограничения, то нужна иерархия вселенных не просто нумерованных натуральными числами, а счётная иерархия вселенных, нумерованных конструируемыми в рамках данной теории ординалами.

Насколько я понимаю, что если ослабить условие, что тип Х должен быть индуктивным, (но оставить, что уровень конечен) нам понадобится вселенная Махло, а если совместно с отсутствием ограничения на уровень, то счётная иерархия вселенных, индексированная любыми вычислымими счётными ординалами, т.е. до ординала Чёрча-Клини невключительно. Последний абзац скорее спекулятивен.
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.
  • 1 comment