Cons-free Programming with Immutable Functions

11/09/2017

∙

by   Cynthia Kop, et al.

∙

0

∙

share

We investigate the power of non-determinism in purely functional programming languages with higher-order types. Specifically, we set out to characterise the hierarchy NP ⊆ NEXP ⊆ NEXP^(2) ⊆...⊆ NEXP^(k) ⊆... solely in terms of higher-typed, purely functional programs. Although the work is incomplete, we present an initial approach using cons-free programs with immutable functions.