Higher types, Finite Domains and Resource-bounded Hiring Machines

摘要

We prove that neat and natural fragments of the higher order programming language, PCF, capture complexity classes denned by imposing resource bounds on Turing machines. Moreover, we survey some related research on on Godel's T, and discuss the relationship between fragments of Godel's T and fragments of PCF. Our proofs are based on denotational semantics and domain theory.