Acceptable functional programming systems (Q1061487)

In this paper we present a self-contained treatment of the theory of computable functions using acceptable functional programming systems. We construct a particular acceptable functional programming system. Within the framework of this system we prove two main theorems to show that, when working with substitution operators, the fixed point function defined by the mechanism of the system and the fixed point function defined by the recursion theorem are both equal to the least fixed point. Furthermore we show that the programs defined by the mechanism of the system are easier and faster than the ones defined by the recursion theorem. We make some suggestions about how to implement the system using a suitable environment. We also formulate a natural question: what is the relationship between substitution operators and computable operators?