4 ms·
Additionally lambda calculus, general recursive functions, combinatorial logic, Turing machines, and a number of other systems are equivalently powerful[0] and
by benlivengood 5y ago
Additionally lambda calculus, general recursive functions, combinatorial logic, Turing machines, and a number of other systems are equivalently powerful[0] and so any computable function can be expressed in any of the systems. So it's fine to refer either to purely functional algorithms or purely state-machine algorithms since they are equivalent statements.
[0] https://en.m.wikipedia.org/wiki/Church%E2%80%93Turing_thesis https://en.m.wikipedia.org/wiki/Church%E2%80%93Turing_thesis
- Ar-Curunir 5y agoDifferent formalisms can describe the same concept, but they don’t always make the same analyses easy. Eg: one of the main things we do with algorithms is analyze their time and space complexity, and it’s often easier to do this in a state machine model