Hacker News new | ask | show | jobs
by Dylan16807 3845 days ago
1. I was making a point more about runtime complexity. This system can't take an input of size n and then perform more than O(n) computation. Because you don't just input the first line. Rule 110 has to be at least n^2, probably much more before you get an 'answer'? I don't feel like looking up papers at the moment.

2. But the behavior upon turning the crank is defined as part of the machine. The human can emulate it mentally, but they're not whole-cloth adding something that wasn't already in the machine.

3. The point here lies in the _rules_.

I agree. Which is why CSS is not Turing complete. CSS + a specific web page of enormous unending length + someone holding down a few keys is the minimum to reach Turing complete.

CSS is like "110", the number, by itself. It's not Turing complete without a bunch of rules that have absolutely nothing to do with CSS itself to push it along.