Comment by Dylan16807 | Hacker News Reader

Comment by Dylan16807 | Hacker News Reader

Parent Full thread

1. Feeding infinite HTML is not the same as feeding tape. A million tape cells can keep a typical Turing machine running indefinitely. A million rows only keep this running for a million execution steps, which is what, a tenth of a second if optimized?

2. The 'crank' here is not part of CSS. Computer languages that are declared 'Turing complete' need to be able to crank themselves. You need to be able to tell them to go, and wait. I accept that magic the gathering Turing machine, (at least as long as you remove the word 'may'), because it's part of the MtG rule set that you continue performing all the state transitions until you reach a halt.

3. Allowing this completely external pump means that anything that can add and multiply three numbers and then exit would be counted as Turing complete, because you can then instantiate an infinite number of these and pump data through. The Turing complete nature of that construction lies mostly in that pump. It is not at all just a crank that say 'go'.

And 3 is really the important part here. None of the scary implications of 'Turing complete' come into play, because you can't take the result of one arithmetic statement and feed it into more. All of that playing around is roughly O(n) in terms of page size. Not O(unlimited) as 'Turing complete' might imply.

This is entirely correct. The article doesn't fix the original reason why the "CSS turing machine" wasn't actually a turing machine. It doesn't "crank its own tape", so to speak.

Layout in a web browser, which includes CSS styling, is implemented as just a top down + bottom up tree traversal. 2 tree traversals do not a turing machine make.

Maybe an analogy will help. I like the multiplier mentioned in the grandparent. Consider the multiplication circuit. I hope you agree that a multiplication circuit is not turing complete. However, if you apply a "pump" and feed its results into one of its inputs, you can calculate the factorial of any number!

This concept can be extended to take any sequence of steps and calculate recursive functions with them. This doesn't mean a linear sequence of instructions is turing complete! The feedback is a fundamental part of what makes the system turing complete.

The headline would better read "CSS + user input which can trigger a reflow is turing complete", but that wouldn't be nearly as interesting.

In fact, if CSS _was_ turing complete, I can solve the halting problem!

Step 1) Encode a turing machine as CSS + html.

Step 2) Run CSS and layout. This is O(size of css + size of html), since it's two tree traversals.

Step 3) It halts. CSS styling is finished.

CSS is just a tree traversal. It has a lot of rules, but the structure is simple. It is not turing complete.

  > 1. Feeding infinite HTML is not the same as feeding 
  > tape. A million tape cells can keep a typical Turing 
  > machine running indefinitely. A million rows only keep 
  > this running for a million execution steps

There are read-only systems that are considered Turing Complete. They also work by concatenating new data (of potentially unbounded size) at each computation step. For example, a one-dimensional cellular automaton called Rule 110: https://en.wikipedia.org/wiki/Rule_110 . The fact that traditional Turing Machines reclaim storage is an implementation detail, not anything fundamental to Turing Completeness or computer science.

The distinction is that those systems have "create a new line via X" as a core part. That's not in CSS, that's external. That's the key thing keeping CSS from really being Turing Complete.

Thank you for pointing out Magic the Gathering is Turing complete! That is such a good read[0].

[0] http://www.toothycat.net/~hologram/Turing/HowItWorks.html

1. Sure, but just since finite input can be handled quickly doesn't mean it's not turing complete. A million cell tape for the Rule 110 automaton in any language will probably execute in milliseconds, if at all optimised... There might be other turing complete problems that can reuse tape the way you suggest, but Rule 110 isn't one of them.

2. In Turings own paper he envisions the "crank" to be a human. I think we can all agree that a human is more than turing complete. The process of feeding the next cell etc isn't part of what makes something Turing complete. There is no requirement that it be self-cranking in Turings papers, nor the current formal definitions I have read. Could you supply an example of where this is brought up as a formal requirement?

3. Well, yes. The point here lies in the _rules_. The method of executing the rules doesn't really matter, as discussed in 2. Humans are > Turing complete ...

About 2, sure. But when people say "X shown Turing complete", that doesn't have much meaning unless the X is somehow doing it without external input. Why? Because otherwise everything is Turing complete. Literally, "series of bits proven Turing complete!", "line of rocks on a sidewalk Turing complete!"

Because, the fact that computers exist is not a surprise. I mean, the original concept of a Turing machine is literally a tape and a read head.

I'm sorry if I totally butcher the fundamental concepts of Turing completeness here; I was neither a CS nor a math major.

But as I understand it a Turing machine is a physical impossibility because it is defined as having an infinite stream of data being inputted. And the physical presence of an infinity of information is a physical impossibility (I also wasn't a physics major, so I'm not sure if this violates physical laws or is just a practical impossibility, but either way it's obviously impossible).

So instead of an infinite stream of input, we usually define something as "Turing complete" if it's possible for it perform arbitrary computations on arbitrary input supplied in real time. CSS3 cannot do this; programming languages with real-time I/O can do this.

So CSS3 is "weakly" Turing-complete because it can perform arbitrary computations on arbitrary data input supplied ahead of time. With an infinite amount of random HTML-formatted data input ahead of time (same as a Turing machine), it can be equivalent to a Turing machine. C or Javascript are "strongly" Turing-complete because they can perform arbitrary computations on arbitrary, properly-formatted data input supplied ahead-of-time or in real time.

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.

Indeed, and if they want to make these claims why aren't they applying the same logic to Coq, Agda and Idris? These languages are often lauded (correctly) for giving up Turing completeness in exchange for improved static safety. But they all can implement rule 110.

Reply on news.ycombinator.com