5 ms·

> No real-world thing can actually be Turing complete But when you say Turing-complete, I assume something along the lines of "a programming language can be bu

by hasenj 16y ago

> No real-world thing can actually be Turing complete But when you say Turing-complete, I assume something along the lines of "a programming language can be built on top of it and you can create interactive applications using such a programming language instead of javascript". It seems like that's not the case at all.

jules 16y ago
Then you assumed a falsehood. Turing completeness is a mathematical concept that has nothing to do with interactive applications.
- 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.
  - 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.
elitheeli 16y ago
When I say "Turing complete", I mean Turing equivalent to a Turing machine. Since there are infinitely many Turing machines but I'm pretty sure humanity has access to a finite amount of state. I mean it strictly in the theoretical sense.
- JonnieCache 16y ago
  >I'm pretty sure humanity has access to a finite amount of state There is at least one man out there who isn't: http://en.wikipedia.org/wiki/Omega_point_(Tipler)#The_Omega_Point http://en.wikipedia.org/wiki/Omega_point_(Tipler)#The_Omega_... I doubt I'll be drinking that koolaid to be honest.
KeithMajhor 16y ago
There's plenty of things that are Turing Complete but that shouldn't be used for interactive applications. http://en.wikipedia.org/wiki/Brainfuck http://en.wikipedia.org/wiki/Brainfuck http://en.wikipedia.org/wiki/Template_metaprogramming http://en.wikipedia.org/wiki/Template_metaprogramming http://en.wikipedia.org/wiki/Turing_machine http://en.wikipedia.org/wiki/Turing_machine and now apparently HTML + CSS
- JonnieCache 16y ago
  Model railways are turing complete. http://www.monochrom.at/turingtrainterminal/pictures_eng.htm http://www.monochrom.at/turingtrainterminal/pictures_eng.htm
- hasenj 16y ago
  Is it not possible to write a C compiler that outputs Brainfuck code that can be executed inside a Brainfuck interpreter?
amalcon 16y ago
What people usually mean by "Turing complete" is "would be Turing complete if it were infinite." That does imply that a programming language can be built on top of it, and that programming language is fully capable of performing any given algorithm. It says nothing about interactivity, which is a function of ability to (directly or indirectly) access I/O hardware.
lukeschlather 16y ago
Everyone's being a little cagey about what Turing Completeness really means, in layman's terms, because I think the assumption is that if you're here, you should already have a deep understanding of it. So no, as others have said, you are completely off base as to what the significance of being Turing complete is. What Turing complete means is that given an infinite amount of memory and time, a language can simulate anything that is computable. (I won't get into what computable means, for that you will need to read and reread the relevant Wikipedia articles, along with a good book on Theory of Computation and probably a good one on Abstract Algebra.) But the real significance of this is that you cannot write a program that can tell you meaningful facts about the behavior of an arbitrary Turing machine. For any program you write to determine the behavior of HTML + CSS, I could write a piece of HTML + CSS that your program will be unable to say anything about. However, this particular proof actually only shows HTML + CSS is equivalent to a Linear Bounded Automaton, which unlike a Turing Machine can be predicted. And strictly speaking, even if you have a Turing-machine-equivalent language like C++, you can theoretically make some predictions about programs provided you can bound its memory, i.e., on a machine with less than 4 GB of memory, it is equivalent to a Linear Bounded Automaton. Now, of course actually writing a second program to do this may be impossible to do before the heat death of the universe, because Linear Bounded Automatons are still very powerful computing objects.
- shasta 16y ago
  "But the real significance of this is that you cannot write a program that can tell you meaningful facts about the behavior of an arbitrary Turing machine. For any program you write to determine the behavior of HTML + CSS, I can write a piece of HTML + CSS that your program will be unable to say anything about." Sorry, but this is false and for similar reasons is not reasonably considered Turing complete. The encoding presented here produces, for any particular HTML + CSS, a finite number of cells of an automata (and not only that, the number of cells is linear in code size). That means that deciding any property about a given piece of code amounts to search over a finite space. This is very different from true Turing completeness where a small set of rules might require unbounded space and computation to decide, and in general will not even be decidable. Now, the author of this code says in a parent post that we can't build a real Turing machine. That's true, but doesn't mean that we can't specify a real Turing complete process; it just means that for some executions we have to give up on running them. In some cases, it makes sense to consider languages that are not actually Turing complete as approximately Turing complete. For example, if you take the C programming language, with a 64 bit memory space, then again there's technically only a finite space of possible program states. But in that case, you can have a 100 line C program that can generate 2^64 possible program states. Turing completeness is a reasonable approximation. If you had to allocate every bit of memory explicitly with a unique line of C code, it would no longer be very reasonable to consider C approximately Turing complete.

by hasenj 16y ago

jules 16y ago

Then you assumed a falsehood. Turing completeness is a mathematical concept that has nothing to do with interactive applications.

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.
- 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.

elitheeli 16y ago

When I say "Turing complete", I mean Turing equivalent to a Turing machine. Since there are infinitely many Turing machines but I'm pretty sure humanity has access to a finite amount of state. I mean it strictly in the theoretical sense.

JonnieCache 16y ago
>I'm pretty sure humanity has access to a finite amount of state There is at least one man out there who isn't: http://en.wikipedia.org/wiki/Omega_point_(Tipler)#The_Omega_Point http://en.wikipedia.org/wiki/Omega_point_(Tipler)#The_Omega_... I doubt I'll be drinking that koolaid to be honest.

KeithMajhor 16y ago

There's plenty of things that are Turing Complete but that shouldn't be used for interactive applications. http://en.wikipedia.org/wiki/Brainfuck http://en.wikipedia.org/wiki/Brainfuck http://en.wikipedia.org/wiki/Template_metaprogramming http://en.wikipedia.org/wiki/Template_metaprogramming http://en.wikipedia.org/wiki/Turing_machine http://en.wikipedia.org/wiki/Turing_machine and now apparently HTML + CSS

JonnieCache 16y ago
Model railways are turing complete. http://www.monochrom.at/turingtrainterminal/pictures_eng.htm http://www.monochrom.at/turingtrainterminal/pictures_eng.htm
hasenj 16y ago
Is it not possible to write a C compiler that outputs Brainfuck code that can be executed inside a Brainfuck interpreter?

amalcon 16y ago

What people usually mean by "Turing complete" is "would be Turing complete if it were infinite." That does imply that a programming language can be built on top of it, and that programming language is fully capable of performing any given algorithm. It says nothing about interactivity, which is a function of ability to (directly or indirectly) access I/O hardware.

lukeschlather 16y ago

Everyone's being a little cagey about what Turing Completeness really means, in layman's terms, because I think the assumption is that if you're here, you should already have a deep understanding of it. So no, as others have said, you are completely off base as to what the significance of being Turing complete is. What Turing complete means is that given an infinite amount of memory and time, a language can simulate anything that is computable. (I won't get into what computable means, for that you will need to read and reread the relevant Wikipedia articles, along with a good book on Theory of Computation and probably a good one on Abstract Algebra.) But the real significance of this is that you cannot write a program that can tell you meaningful facts about the behavior of an arbitrary Turing machine. For any program you write to determine the behavior of HTML + CSS, I could write a piece of HTML + CSS that your program will be unable to say anything about. However, this particular proof actually only shows HTML + CSS is equivalent to a Linear Bounded Automaton, which unlike a Turing Machine can be predicted. And strictly speaking, even if you have a Turing-machine-equivalent language like C++, you can theoretically make some predictions about programs provided you can bound its memory, i.e., on a machine with less than 4 GB of memory, it is equivalent to a Linear Bounded Automaton. Now, of course actually writing a second program to do this may be impossible to do before the heat death of the universe, because Linear Bounded Automatons are still very powerful computing objects.

shasta 16y ago
"But the real significance of this is that you cannot write a program that can tell you meaningful facts about the behavior of an arbitrary Turing machine. For any program you write to determine the behavior of HTML + CSS, I can write a piece of HTML + CSS that your program will be unable to say anything about." Sorry, but this is false and for similar reasons is not reasonably considered Turing complete. The encoding presented here produces, for any particular HTML + CSS, a finite number of cells of an automata (and not only that, the number of cells is linear in code size). That means that deciding any property about a given piece of code amounts to search over a finite space. This is very different from true Turing completeness where a small set of rules might require unbounded space and computation to decide, and in general will not even be decidable. Now, the author of this code says in a parent post that we can't build a real Turing machine. That's true, but doesn't mean that we can't specify a real Turing complete process; it just means that for some executions we have to give up on running them. In some cases, it makes sense to consider languages that are not actually Turing complete as approximately Turing complete. For example, if you take the C programming language, with a 64 bit memory space, then again there's technically only a finite space of possible program states. But in that case, you can have a 100 line C program that can generate 2^64 possible program states. Turing completeness is a reasonable approximation. If you had to allocate every bit of memory explicitly with a unique line of C code, it would no longer be very reasonable to consider C approximately Turing complete.