2 ms·
Not just possibly. Here's a non-exhaustive list of models of computation that are all equivalent. + Turing machines + Lambda calculus + General recursive fun
by dwohnitmok 7y ago
Not just possibly. Here's a non-exhaustive list of models of computation that are all equivalent.
+ Turing machines
+ Lambda calculus
+ General recursive functions
+ Mu-recursive functions
+ SKI calculus
+ Pi calculus
+ Register machines
+ The semantics of essentially every mainstream general programming language
This remarkable profusion of equivalences is the main reason why the Church-Turing Thesis (an informal statement that our intuitive notion of computation coincides with Turing machines and/or the lambda calculus) is commonly accepted.
- deleted 7y ago[deleted]