"Turing completeness" is extremely orthogonal to complexity. Being "Turing complete" only means that your thing supports unlimited recursion; or, in other word

"Turing completeness" is extremely orthogonal to complexity. Being "Turing complete" only means that your thing supports unlimited recursion; or, in other words, that whatever objects it encodes can be arbitrarily large. See: https://en.wikipedia.org/wiki/Rule_110 https://en.wikipedia.org/wiki/Rule_110 P.S. This also means that, technically speaking, the computers we use aren't Turing complete because they have RAM and storage limits.