Dmitry Astapov (_adept_) wrote in fprog,
Dmitry Astapov
_adept_
fprog

Пределы выразительности свёрток

Пределы выразительности свёрток

Виталий Брагилевский


Аннотация


Свёртки — удобное средство обработки списков и других структур данных. Они позволяют записывать многие функции без явной рекурсии, а также упрощают формальное доказательство их корректности. В настоящей статье рассматривается вопрос о пределах того, что вообще можно записать (вычислить) с помощью свёрток. В частности, показывается, что свёртки могут вести себя как комбинаторы неподвижной точки при моделировании рекурсивных вызовов. С помощью свёрток также реализуется оператор примитивной рекурсии на списках, что позволяет выразить в соответствующих терминах любые примитивно рекурсивные функции.
Tags: #4
Subscribe

  • Post a new comment

    Error

    default userpic

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