Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

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.



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


Yes, you're right, I've edited my post a bit to make it clearer that HTML+CSS is not Turing complete.


What Turing complete means is that given an infinite amount of memory and time, a language can simulate anything that is computable.

Change "simulate" to "compute" and I agree fully. I don't think it's necessary to introduce the concept of simulation. If a language (or process, mechanism or whatever) is Turing Complete, then you can use it to express all things computable. Given sufficient resources, that expression could actually do the computation.

edit: I recalled in a sibling post why simulation comes up, and I think it's a source of confusion. The easiest way to prove a formalized process is Turing complete is to simulate a Turing machine. Since a Turing machine can compute all that is computable, and your process can simulate a Turing machine, your process can compute all that is computable. Hence, it is Turing complete.


Looking through the Wikipedia page for LBAs, they're a Turing machine where the tape is limited to a linear function of the size of the input. This is still beyond what realistic computers are since the tape would still need to be infinite to hold as big of an input as you want to feed into it.

Aren't practical computers just simply Finite State Machines?


Aren't you confusing computability with Godel's incompleteness theorem?




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: