Consider the various models of computation: Turing machines, lambda calculus, Boolean circuits, etc. They have different primitives—tapes, substitution rules, logic gates—but the Church-Turing thesis tells us they’re equivalent.
Nit: the standard notion of Boolean circuit isn’t Turing-complete.
Yeah, good catch—the correct notion here is a (uniform) family of Boolean circuits, which are Turing-complete in the sense that every uniform circuit family decides a decidable language, and every decidable language can be decided by a uniform circuit family. (Usefully, they also preserve complexity theory: for example, a language is in P if and only if it can be decided by a P-uniform polynomial-size circuit family.)
Agreed. I guess the small saving grace (as I’m sure you know) is that the TM under the hood is used to limit the computational power of the family rather than contribute to it. But yeah that part is kind of ugly.
Nit: the standard notion of Boolean circuit isn’t Turing-complete.
Yeah, good catch—the correct notion here is a (uniform) family of Boolean circuits, which are Turing-complete in the sense that every uniform circuit family decides a decidable language, and every decidable language can be decided by a uniform circuit family. (Usefully, they also preserve complexity theory: for example, a language is in P if and only if it can be decided by a P-uniform polynomial-size circuit family.)
(Though that notion assumes a Turing machine under the hood, so it’s not a full-fledged alternative model of computation like lambda calculus.)
Agreed. I guess the small saving grace (as I’m sure you know) is that the TM under the hood is used to limit the computational power of the family rather than contribute to it. But yeah that part is kind of ugly.