I see. I think your argument falls apart when you wave away the differences (e.g. memory) between a finite state machine, a Turing machine and an actual compute

I see. I think your argument falls apart when you wave away the differences (e.g. memory) between a finite state machine, a Turing machine and an actual computer. Theoretically, the Turing machine and lambda calculus are equivalent: https://en.m.wikipedia.org/wiki/Church–Turing_thesis https://en.m.wikipedia.org/wiki/Church–Turing_thesis However, in practise, the specifics of programming languages are essential: https://en.m.wikipedia.org/wiki/Turing_tarpit https://en.m.wikipedia.org/wiki/Turing_tarpit When you include the state of the memory in the state of the state machine, the state space explodes, which is more than inconvenient. On the other hand, in lambda calculus and Haskell, you don't have to even think about state.