6 ms·

No, mathematically nothing is "Turing Complete". The only usefulness of saying that something is "Turing Complete" is in knowing that you can treat it as if it

by hasenj 16y ago

No, mathematically nothing is "Turing Complete". The only usefulness of saying that something is "Turing Complete" is in knowing that you can treat it as if it was a normal computer for all intents and purposes. So mathematically a laptop is not Turing Complete, but for all practical purposes, it is.

jules 16y ago
Also incorrect. Counterexample: Turing machines are Turing complete. You are correct that a laptop is not Turing complete, though.
- hasenj 16y ago
  Seriously? It's obvious I meant "nothing real is mathematically Turing complete".
  - jules 16y ago
    I know, I answered (incorrect) nitpicking with (correct) nitpicking.
jng 16y ago
Nope. The common usefulness is to determine whether a given computation-describing system reaches the threshold of universal computability. Modulo finite size is assumed, else there is no usefulness of the concept given finite resources. For example, SKI combinators are Turing-equivalent. Regular expressions aren't. The lambda-calculus is. Context-independent grammars probably are. Most data description languages are not. This is worthy of an HN post because a style-description language would not normally be expected to be Turing-equivalent. When it became widely known that the C++ template system was Turing-equivalent, it was a shock to many. These meant that the C++ compiler code itself could be exploited to compute arbitrary things such as factorials, or shortest-paths in graphs using A*. Actually, as the SKI system demonstrates, the threshold is quite low. The core needed components are just "constant" or "if" (they are often equivalent), and "repeat" (equivalent to both "iterate" and "recurse").
- timtadh 16y ago
  >Context-independent grammars probably are. No they are not. Recursively Enumerable grammars are however. A context free grammar can't be turning complete because it can be decided with only a PDA.
  - deleted 16y ago
    [deleted]
- bzbarsky 16y ago
  > because a style-description language would not normally be > expected to be Turing-equivalent. Wouldn't it? XSLT, the only other style-description language in anything like common use on the web, has been Turing-complete for a while now (possibly since it started existing; I'm not familiar with the history)...
  - arethuza 16y ago
    XSLT is the transformation part of XSL (hence the T), meant for transforming XML into other formats, including things like XSL-FO which is the formatting part of XSL. As it is a general purpose language (with iteration, recursion and conditionals) it's not that surprising that it is Turing-equivalent. XSL-FO is the formatting part of XSL (i.e. the bit most like CSS) - I'd be pretty surprised if this was shown to be Turing-equivalent.
  - chwahoo 16y ago
    XSLT performs transformations (i.e., takes input and produces output). This sounds to me like a "program" so I wouldn't be surprised that a language like XSLT might be Turing complete. HTML and CSS are much more "static" in flavor (hence the OP's use of the term "descriptive") and so it might be more unexpected that they can perform universal computation.
- samuizo 16y ago
  I could be mistaken, but I think there's a fundamental distinction between the computing power required to recognize a language and the kinds of functions a language can compute. AFAIK (which isn't much), usually the distinction between regular, context-free, context-sensitive and recursively-enumerable languages turns on the power of the recognizer rather than the power of the language to express functions. In other words, the languages are limited in their syntactic expressivity but not their semantic expressivity. I've always understood the latter to be the key to determining the computational power. Take lambda calculus as an example. It is Turing complete, but it is amenable to a context-free syntactic implementation (see http://www.soe.ucsc.edu/classes/cmps112/Spring03/readings/lambdacalculus/syntax.html http://www.soe.ucsc.edu/classes/cmps112/Spring03/readings/la...). For C++, I always thought it was that not only is it capable of expressing semantically any computable function, but that a [EDIT: Turing Complete] parser was required to parse C++ strings.
scott_s 16y ago
The concept of Turing Complete does not apply to a laptop because the laptop itself is not a means to express computation. It is a means to execute computations. There is a difference. Turing Complete is a statement about the computational generality of languages. (Or, even more general, formalized processes.) What you mean to say is that a laptop is not an actual Turing machine, but for all intents and purposes, it is. On that point, I agree.

by hasenj 16y ago

jules 16y ago

Also incorrect. Counterexample: Turing machines are Turing complete. You are correct that a laptop is not Turing complete, though.

hasenj 16y ago
Seriously? It's obvious I meant "nothing real is mathematically Turing complete".
- jules 16y ago
  I know, I answered (incorrect) nitpicking with (correct) nitpicking.

jng 16y ago

Nope. The common usefulness is to determine whether a given computation-describing system reaches the threshold of universal computability. Modulo finite size is assumed, else there is no usefulness of the concept given finite resources. For example, SKI combinators are Turing-equivalent. Regular expressions aren't. The lambda-calculus is. Context-independent grammars probably are. Most data description languages are not. This is worthy of an HN post because a style-description language would not normally be expected to be Turing-equivalent. When it became widely known that the C++ template system was Turing-equivalent, it was a shock to many. These meant that the C++ compiler code itself could be exploited to compute arbitrary things such as factorials, or shortest-paths in graphs using A*. Actually, as the SKI system demonstrates, the threshold is quite low. The core needed components are just "constant" or "if" (they are often equivalent), and "repeat" (equivalent to both "iterate" and "recurse").

timtadh 16y ago
>Context-independent grammars probably are. No they are not. Recursively Enumerable grammars are however. A context free grammar can't be turning complete because it can be decided with only a PDA.
- deleted 16y ago
  [deleted]
bzbarsky 16y ago
> because a style-description language would not normally be > expected to be Turing-equivalent. Wouldn't it? XSLT, the only other style-description language in anything like common use on the web, has been Turing-complete for a while now (possibly since it started existing; I'm not familiar with the history)...
- arethuza 16y ago
  XSLT is the transformation part of XSL (hence the T), meant for transforming XML into other formats, including things like XSL-FO which is the formatting part of XSL. As it is a general purpose language (with iteration, recursion and conditionals) it's not that surprising that it is Turing-equivalent. XSL-FO is the formatting part of XSL (i.e. the bit most like CSS) - I'd be pretty surprised if this was shown to be Turing-equivalent.
- chwahoo 16y ago
  XSLT performs transformations (i.e., takes input and produces output). This sounds to me like a "program" so I wouldn't be surprised that a language like XSLT might be Turing complete. HTML and CSS are much more "static" in flavor (hence the OP's use of the term "descriptive") and so it might be more unexpected that they can perform universal computation.
samuizo 16y ago
I could be mistaken, but I think there's a fundamental distinction between the computing power required to recognize a language and the kinds of functions a language can compute. AFAIK (which isn't much), usually the distinction between regular, context-free, context-sensitive and recursively-enumerable languages turns on the power of the recognizer rather than the power of the language to express functions. In other words, the languages are limited in their syntactic expressivity but not their semantic expressivity. I've always understood the latter to be the key to determining the computational power. Take lambda calculus as an example. It is Turing complete, but it is amenable to a context-free syntactic implementation (see http://www.soe.ucsc.edu/classes/cmps112/Spring03/readings/lambdacalculus/syntax.html http://www.soe.ucsc.edu/classes/cmps112/Spring03/readings/la...). For C++, I always thought it was that not only is it capable of expressing semantically any computable function, but that a [EDIT: Turing Complete] parser was required to parse C++ strings.

scott_s 16y ago

The concept of Turing Complete does not apply to a laptop because the laptop itself is not a means to express computation. It is a means to execute computations. There is a difference. Turing Complete is a statement about the computational generality of languages. (Or, even more general, formalized processes.) What you mean to say is that a laptop is not an actual Turing machine, but for all intents and purposes, it is. On that point, I agree.