ABSTRACT
A model of computation is an abstraction of a real computing device. Dierent computational models serve dierent objectives and purposes. us, they always suppress some properties and details that are irrelevant for the purpose at hand, and they focus on other properties that are essential. Consequently, models of computation have been evolving during the history of computing. In the early decades between and the main focus was on the question: “What is computable?” e Turing machine and the lambda calculus are prominent examples of computational models developed to investigate that question.∗ It turned out that several, very dierent models of computation such as the Turing machine, the lambda calculus, partial recursive functions, register machines, Markov algorithms, Post systems, etc. [Tay] are all equivalent in the sense that they all denote the same set of computable mathematical functions. us, today the so-called Church-Turing thesis is widely accepted.
