Models of Computation
摘要
Register machines are introduced as a machine-based model of computation. We show that register machines compute exactly the class of general recursive functions and formulate the Church–Turing thesis that this is exactly the collection of computable functions.