Re:Discovering Dennis Ritchie’s Lost Dissertation
by vilhelm_s on Saturday June 20, 2020 @11:24PM
(#23589493)
"How to Program an Infinite Abacus" defines register machines (a.k.a counter machines), and shows that they coincide with general recursive functions. "The complexity of loop programs" defines loop programs, and shows that the coincide with primitive recursive functions. (A key difference is whether loops are bounded or not.)
Lambek in turn cites Melzak's "An Informal Arithmetical Approach to Computability and Computation" which not identical - it has transfer and arbitrary compare branch instructions - but that seems a compromise for pedagogical purposes as deriving both from the "abacus" seems fairly trivial to me.