> When we look at what computation is, physically, we find it's a lot like a Turing machine underneath (physical rewriting systems), albeit with different kinds

> When we look at what computation is, physically, we find it's a lot like a Turing machine underneath (physical rewriting systems), albeit with different kinds of structures that are being rewritten. I don't think that's the case at all. We see sequential TM-like processes when we look at mainstream electronic computers, but that's kind of a circular argument. When we look at physical processes in general, the computations they're performing tend to be massively parallel. Pure computation (e.g. lambda calculus, and especially combinatory logic) is well suited to running on massively parallel circuitry (e.g. https://en.wikipedia.org/wiki/Graph_reduction_machine https://en.wikipedia.org/wiki/Graph_reduction_machine ). It's perhaps also worth mentioning that such languages can be interpreted as (descriptions of) circuitry! E.g. see http://conal.net/papers/compiling-to-categories http://conal.net/papers/compiling-to-categories