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.
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.