8 ms·
All usual models of computation (such as Turing machines, register machines, the lambda calculus, ...) agree on which functions from the naturals to the natural
by IngoBlechschmid 8y ago
All usual models of computation (such as Turing machines, register machines, the lambda calculus, ...) agree on which functions from the naturals to the naturals they deem computable, and the Church–Turing thesis states that these are exactly those functions which can actually be computed by machines in the real world.
That said, the models of computation bifurcate when studying the question which higher-order functions (functions which input functions as arguments) are computable. Such a function can be easily computable according to one model and not computable at all according to another. I'm writing this because far too often the unqualified statement "all the usual models of computation are equivalent" is made. This is emphatically only true for first-order computation, not for higher-order computation.