4 ms·
Computation is the creation of and executing of algorithms. Even if an algorithm is expressed functionally, it progresses through a sequence of states when exec
by amw-zero 5y ago
Computation is the creation of and executing of algorithms. Even if an algorithm is expressed functionally, it progresses through a sequence of states when executed.
Check out Computation and State Machines by Leslie Lamport: https://lamport.azurewebsites.net/pubs/state-machine.pdf https://lamport.azurewebsites.net/pubs/state-machine.pdf. Specifically, in Section 3, he shows how interactive and recursive definitions of the same program are actually executing the same underlying algorithm, even though their source code looks drastically different.
Syntax is superficial, and declarativeness is really just an illusion, or maybe a convenience. But, a program is executing a sequence of states no matter what paradigm it’s expressed in. Functional programs are still executed.
In this respect, you’re talking about a very superficial aspect of algorithms.
- benlivengood 5y agoAdditionally 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
- zelphirkalt 5y agoIt might be more correct to say, that a program are the instructions, which lead to the machine transitioning throught some sequence of states.