> Effectively, it is a definition of computation that has so far been accepted because nothing fundamentally different and more powerful than a Turing machine h

> Effectively, it is a definition of computation that has so far been accepted because nothing fundamentally different and more powerful than a Turing machine has been exhibited. Note that there is a commonly accepted extension that is more powerful than a Turing machine: Probabilistic Turing machines. I'm guessing the proof of equivalence generalizes to partial recursive functions and the lambda calculus if you add a 'random oracle'. An interesting counter-argument is that real random oracles don't exist, and that in reality, we can simulate probabilistic computation using Pseudo Random Number Generators. So: * True probabilistic computation isn't possible * And anyway, deterministic computation gets close enough to probabilistic computation through PRNGs Alternatively, one might argue one could build a 'real' random oracle by reading from a 'true' random source. E.g. Cosmic microwave background, atmospheric noise, quantum fluctuations or a video of lava lamps. There is a difference between a random source and a random oracle, but with sufficient storage, that can be patched.