JetBrains Research unites scientists working in challenging new disciplines

The expressive power of higher-order types and non-determinism

It is well-known that different features of functional programming languages, such that being first- or higher- order, do not affect their expressiveness. Both classes are Turing-complete. Nevertheless, considering programming languages that are less than Turing-complete one can use complexity classes to characterize the expressive power of different language features. We will discuss how features like availability of higher-order functions, cons-freedom, recursion type and non-deterministic choice affect programming language expressiveness.


Speaker: Daniil Berezun


The seminar will be held in google meet on Monday April 27 at 17:15 (google meet room: https://meet.google.com/myu-dhmz-gvu)