Hacker News Reader

Comment by jp_rider | Hacker News Reader

As an aside, HTML5 and CSS3 are [turing complete](http://lambda-the-ultimate.org/node/4222).

I wouldn't count that as Turing-completeness. It requires the user to repeatedly press the tab and space keys to advance the computation; the amount of computation that the CSS is doing for each press of the tab and space keys is trivial. Many systems that are not normally considered "Turing-complete" have the same property. For example, one can construct a finite state transducer that takes a Turing machine state as input and produces the next state of the Turing machine as output. Repeatedly applying this transducer to some input string will simulate a Turing machine, but finite state transducers are not considered Turing complete.

Can you explain why you feel that disqualifies it? The required input doesn't make any decisions, or hold any state as in your example; it's just "turning the crank" so to speak. Even a CPU needs a clock, right?

I'd say that a CPU that needs a clock but does not have one is not Turing-complete. CSS plus an infinite stream of user input is Turing-complete, but CSS itself is not Turing-complete. I should make it clear that I'm not saying, "my definition is the one true definition of Turing-completeness"; just that I prefer this definition. One reason I prefer this definition is that the claim "CSS is Turing-complete" makes it sound like browsers could take unbounded time to render a webpage that only used HTML and CSS, which as far as I can tell is not true.

That does seem sensible. I'll agree to a weaker, more specific claim like: HTML5 + CSS can simulate a Turing machine in Rule 110, but browsers aren't set up to do that without user input. Turing completeness level: eh.

The CPU clock is part of the CPU. That doesn't mean a CPU without a clock is Turing-complete. An ALU with access to a couple registers is not Turing-complete. "Turing-complete as long as something else provides the power to loop endlessly" is not Turing-completeness.

Anything without infinite memory is simulating a Turing Machine. That doesn't mean they aren't useful.

Whether something is useful is a different question than whether something is Turing complete. Brainfuck is Turing complete and eminently useless. CSS is not Turing complete, and arguably useful. How do I know that CSS is not Turing complete? Because I believe that - without Javascript - any given page render will finish. Presuming that's the case, CSS cannot be Turing complete. Of course it can be part of a larger system which is. A finite state machine is not Turing complete; an infinite tape is not Turing complete; but when you combine them, you get a Turing machine.

Brainfuck etc, don't guarantee infinite storage. Therefore, they cannot compute everything computable. Hence, they are are limited to only computing some things but not others. Hence they are not Turing Complete.

Don't get me wrong, I'm fine with lowering the bar and calling them "Turing Complete" as a practical matter. I'm against then turning around and raising the bar and pretending Turing Completeness is implantable when it comes to defining "programming languages."

"Programming language" is an engineering term not a mathematical one.

I think you're making this distinction wrongly.

"Brainfuck etc" - by which we mean not just joke programming languages but most (all?) programming languages generally considered to be Turing complete - don't prohibit infinite storage, and tell you how they would behave if somehow they were run in an environment where they did have infinite storage available.

In that sense, I think it is extremely reasonable to say "the language is Turing complete", without any lowering of the bar.

Any individual finite realization of that language will, of course, be theoretically a finite state machine. But you can't reason about how that restriction of the language will behave (for instance, whether it will halt for all inputs) in the general case without naming the particular resources available. And at that point, it's still not a convenient form for those kinds of questions.

1. Machine/Assembly languages are not theoretically able to access unlimited memory. Hard limits are hardwired into the core of the language A0 is only so big. That we consider such languages as MIX to be Turing Complete is an engineering decision not something amenable to mathematical proof.

2. Let us assume that Turing Completeness is an essential property [in the medieval sense of "essential property"] of programming languages. Using a Turing Complete programming language called "TC" I write a Domain Specific Language called "DFA" for constructing Deterministic Finite Automata. Because Deterministic Finite Automata are "sub-Turing Complete", DFA is not Turing Complete and hence statements in DFA are not written in a programming language. But being isomorphic with statements in the "TC" they must be written in a programming language. Reductio ad Absurdum.

3. It is Turing Complete languages that are hard to reason about. That's why we have the Halting Problem. Deterministic Finite Automata always finish. What makes programming in HTML useful is that whole categories of problems are precluded.

Regarding 1, I agree that machine code (and machine-code equivalents) for probably all architectures are not Turing Complete if we are to be rigorous.

In that case, regarding 2, any encoding from a Turing Complete language into machine code must inevitably be an approximation. That says nothing about the source language.

Regarding 3, I mostly agree - if you can comfortably accomplish your task in a language that is not Turing complete, then making the language Turing complete is a bug not a feature. That is true whether the task is programming or markup.

I would say that HTML is not a programming language because it is not very good for programming; it is a markup language, because it was designed for markup and is much better for markup than for programming or most other tasks. Turing completeness is irrelevant.

Reply on news.ycombinator.com