Imho the fact that a Turing machine is capable of universal computation is surprising/insightful. I'm not sure the fact that other simple systems are then also complete adds much more surprise/insight, even if it's difficult to predict which ones will be.
What I think people often miss is the difference between computational completeness and computational "power". Yes rule 110 is complete, but what that means in practice is that you've shifted most of the work (for solving a real problem) onto specifying the initial conditions.
Maybe Tetris is Turing complete but it's still a lot easier to compute 2+2 on a pocket calculator.
What I think people often miss is the difference between computational completeness and computational "power". Yes rule 110 is complete, but what that means in practice is that you've shifted most of the work (for solving a real problem) onto specifying the initial conditions.
Maybe Tetris is Turing complete but it's still a lot easier to compute 2+2 on a pocket calculator.