Asymptotic Properties of Programs Expressed in Different Computational Models

Abstract

Asymptotic properties of combinatorial objects representing entities of logical provenance form a prominent subject of modern research in computational logic. In recent years, a growing attention has been given to various models of computation, like Turing machines, combinatory logic and, in particular, lambda calculus, which constitutes the core of functional programming languages, such as Haskell or OCaml.? ????? In my talk I will discuss some combinatorial representations of the aforementioned models, as well as some syntactic and semantic properties that are satisfied by random programs expressed within these systems. Moreover, I will explain an increasing interest in such investigations and their role in practical applications.