ABSTRACT
Combinatory logic is a powerful formalism. This is demonstrated by its ability to formalize the notion of a computable function. Some other formal systems that can model the same class of functions are Turing machines, Post calculi, recursive functions, λ -calculi, Markov algorithms and register machines. (There are further formalisms that are just as expressive as those mentioned.) Some of these formal systems have several versions. For instance, variants of Turing machines can have a one-way or a two-way infinite tape, which does not alter the class of functions computable by Turing machines; bounding the size of the available tape by a linear function restricts, whereas adding an oracle expands, the class of computable functions.1
