Alexander Kuklev (akuklev) wrote,
Alexander Kuklev
akuklev

Если кто не знает

(Маленький пост из серии “Если кто не знает”)

Существует такой “Язык программирования” под названием Jot, только он называется автором Крисом Бекером не языком программирования собственно, а «a better Gödel-numbering». Это взаимно-однозначный способ кодировать лямбда-выражения строками из единиц и нулей. Система декодирования проще некуда. Пустая строка означает id, т.е. лямбда-выражение [x|x]. Остальные строки последовательно расшифровываются с конца в дерево комбинаторов:
*0 → *SK
*1 → [x|y|*(x(y))].

Напоминаю, что константный комбинатор K = [x|y|x], а комбинатор обобщённого применения S = [x|y|z|x(z)(y(z))]. А Gödel numbering оно потому, что при добавлении к алфавиту из нуля и единицы ряда дополнительных символов, получается способ кодирования произвольных логических высказываний конечными строками символов конечного алфавита. Например для получения интуиционистской логики достаточно добавления символа отрицания, символа импликации и символа равенства. Для получения Observational Type Theory с ZFC-эквивалентной теорией множеств понадобится добавление 7 символов. Π, Σ, W, ⊥, ⊤, Ω, Set.
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.
  • 3 comments