[dllthomas]

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.

[brudgers]

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.

[dllthomas]

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.

[brudgers]

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.

[dllthomas]

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.