I think complexity is entirely the wrong question to ask regarding Turing completeness. It's about the kind of rules, not how many. That said, maybe the cheeki

I think complexity is entirely the wrong question to ask regarding Turing completeness. It's about the kind of rules, not how many. That said, maybe the cheekiest answer is an actual computer: fantastically complex, but technically TC requires infinite memory.