Higher Types, Finite Domains and Resource-bounded Turing Machines
Lars Bjørlykke Kristiansen · Journal of Logic and Computation · 2010
We prove that neat and natural fragments of the higher order programming language, PCF, capture complexity classes defined by imposing resource bounds on Turing machines. Moreover, we survey some related research on on Gödel’s T, and discuss the relationship between fragments of Gödel’s T and fragments of PCF. Our proofs are based on denotational semantics and domain theory.