Alexander Kuklev (akuklev) wrote,
Alexander Kuklev
akuklev

(черновик)Любую вычислимую биективную запись инициального сегмента ординалов можно выразить в виде abstract rewritting system с рекурсивно-перечислимым набором правил. (По идее, ARS должно быть можно заменить более узким формализмом interaction networks.)

Конечно же нельзя определить, записывает ли какая-то данная ARS ординал (т.е. является ли она сильно-нормализующей), т.к. это эквивалентно проблеме останова, однако в противоположную сторону работает: для любого рекурсивного инициального сегмента система найдётся.

Выражения ARS = ординалы описываемого сегмента, порядок на них = порядок заданный редукцией. Система тотальна (strongly normalizing) тогда и только тогда, когда этот порядок является well-founded-quasi-order, т.е. порядкоизоморфен какому-то ординалу. Учитывая, что ABS автоматически снабжена функцией |.| на термах, измеряющей их длину, мы автоматически получаем (экзистенциальное) определение (частичной) функции H: Nat -> Nat, вычисляющей для каждой длины термов l максимально-возможную для термов длинны l длину цепочки редукций. H тотальна тогда и только тогда, когда ARS действительно задаёт ординал.

Существует ли способ дать функции H не экзистенциальное, а конструктивное определение? По идее должна как-то легко конструироваться производная ARS, типа сети взаимодействия, содержащая натуральные числа, комбинатор H и какие-то вспомогательные комбинаторы, с тем свойством, что тотальность исходной ARS по построению эквивалентна нормализуемости выражения H(n) для всех n?
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