6 ms·

The posts like yours are the ones that actually create confusion around this term, because their authors are confused on what the Turing completeness is themsel

by xyzzyz 15y ago

The posts like yours are the ones that actually create confusion around this term, because their authors are confused on what the Turing completeness is themselves, and so they spread their confusion on the others. No, tests and loops are not what make computational stuff Turing complete -- nondeterministic finite automatons have both of them, and yet they're very weak computationally. I/O (assuming that's what you mean by write) is not even relevant. What matters the most is _memory_, and more importantly, _infinite, easily accessible_ memory. Nondeterministic finite automata have only finite amount of memory available, and thus they are very constrained on what they can compute. Nondeterministic pushdown automata, in spite of having infinite amount of memory available, don't have an easy access to it, and so, being stronger than finite automata, they're still weaker than Turing machines. But as soon as you add a second stack to a pushdown automaton, it suddenly becomes Turing complete. Hell, you can do it even with 6 integer variables instead of 2 stacks (I recall from my computation theory course that 3 integer variables are enough to encode a stack, so 6 will give you two stacks. Maybe you can go down even to 5 or 4). However, you absolutely require infinite memory, because, for sane definitions of "memory", every device with finite amount of memory (for instance, x86 PC) will not be able to compute anything more than deterministic finite automaton. From this point of view, all our computers are able to do is to match its input to a long and hairy regular expression. I hope that it will help some people realize how irrelevant is Turing completeness notion when it's used with regard to real life stuff.

alok-g 15y ago
This was helpful! I knew most of the pieces but not about the 3 integers encoding a stack. I presume integers here can be of any size (that is not constrained by number of bits) or else it won't be infinite amount of memory. Nevertheless, could you shed some more light? Is a push operation left shifting the integer and adding the pushed value...?
- xyzzyz 15y ago
  I don't remember the details, but I found this: http://en.wikipedia.org/wiki/Counter_machine#Two-counter_machines_are_Turing_equivalent_.28with_a_caveat.29 http://en.wikipedia.org/wiki/Counter_machine#Two-counter_mac... It seems that even 2 counters are enough for Turing machine. My class only came up with 3 counters for pushdown automaton, but I'm still happy with it, since we did it ourselves :)
  - alok-g 15y ago
    Thanks. Helpful again. My understanding (after reading your first comment; would not have figured it out by myself!) was right (though incomplete still till I read the Wikipedia page).
- jules 15y ago
  One integer variable is enough, because it effectively gives you infinite memory. Three times infinite memory is as much as one times infinite memory. What matters is not the number of integer variables, but which operations you're allowed to do on them. If 3 integer variables i,j,k with operations o1,o2,...,on are enough to encode a stack, then you can do the same with one integer variable x. You just represent i as all the bits in x whose position is 0 mod 3, j as all the bits whose position is 1 mod 3 and k as all the bits whose position is 2 mod 3. Then you just modify operations to only work on those bits that the operation applies to. For example if you have an operation increment_i, and you start with i=j=k=0 then it works like this: ijkijkijk... start: i=0,j=0,k=0 and x = 000000000... increment_i: now i=1,j=0,k=0 and x = 100000000... increment_i: now i=2,j=0,k=0 and x = 000100000... increment_i: now i=3,j=0,k=0 and x = 100100000... increment_i: now i=4,j=0,k=0 and x = 000000100... And if you increment_k then it works on the other bits: ijkijkijk increment_k: now i=4,j=0,k=1 and x = 001000100... increment_k: now i=4,j=0,k=2 and x = 000001100... increment_k: now i=4,j=0,k=3 and x = 001001100... increment_k: now i=4,j=0,k=4 and x = 000000101...
  - xyzzyz 15y ago
    Our model allowed us only to do INC, DEC and ZERO? on a counter, and it's easily seen that you cannot implement 2 counters using 1 counter with only ZERO?, INC and DEC, for instance by noting that you can recognize a^n b^n c^n language using automaton with two counters, you can (trivially) implement automaton with one counter using pushdown automaton, so if you were able to implement 2 counters using 1 counter, you could recognize a^n b^n c^n using pushdown automaton, which is easily seen to be impossible by applying pumping lemma for context free languages and usual characterization of pushdown automatons in terms of context free languages.
djcapelis 15y ago
You're way off the mark. While it annoys me that computers are constantly modeled as Turing Machines when it's much more appropriate that they be modeled as LBAs (Linear Bounded Automata) it does not have a huge bearing on computational feasibility in practice. While LBAs vs. TMs do have entirely different definitions and notions of what is and what is not undecidable (for instance, the halting problem is decidable for computers since they're LBAs. It's just impractical.) this only really becomes a theoretical difference. Suggesting that an x86 PC is limited to the level of computational complexity of regular grammars is just wrong. LBAs are capable of context sensitive grammars and are much more capable than a FSM and absolutely can compute more. In real life, computers can be modeled as turning machines without much issue. Memory is generally Big Enough(tm) that problems undecidable on TMs are terribly infeasible to attempt even though theoretically they are actually decidable. And as long as the problem has a small enough state space, the computational expressiveness is the same. In practice, this occurs often enough that people still call computers turing machines even though they aren't.
- xyzzyz 15y ago
  Of course it makes more sense to model real life computers as LBAs. Still, it does not change the fact that given a computer, it has bounded, and not linearly bounded amount of memory, and that makes them no stronger than regular expressions. Of course that there's no practical difference for programmers. Of course the problem space is usually small enough. But it only proves my point: applying abstract terminology to real-life stuff does not necessarily make sense all the time. It makes more sense to take. say, C or Python programming environment, instead of x86, as a computing model. It's enough to assume that malloc never fails to have genuinely Turing complete device.
  - djcapelis 15y ago
    > and that makes them no stronger than regular expressions Again, no. This is simply not how computational complexity works and this statement is factually incorrect. Please do your research.
    - 15y ago
RockyMcNuts 15y ago
fair enough - sufficiently large memory is also necessary. For that reason you couldn't write a Lisp interpreter on the 12C, although you could write one in the 12C language. The point I was trying to make is that the simplest languages are Turing equivalent (given sufficient memory), because they have the necessary tests and control flow. The TFA goes a bit astray IMHO when it says Turing completeness is not necessary for a language to be useful. Turing completeness is a low bar and even SQL as generally implemented hurdles it. sorry, I wasn't incredibly rigorous or clear.

by xyzzyz 15y ago

alok-g 15y ago

This was helpful! I knew most of the pieces but not about the 3 integers encoding a stack. I presume integers here can be of any size (that is not constrained by number of bits) or else it won't be infinite amount of memory. Nevertheless, could you shed some more light? Is a push operation left shifting the integer and adding the pushed value...?

xyzzyz 15y ago
I don't remember the details, but I found this: http://en.wikipedia.org/wiki/Counter_machine#Two-counter_machines_are_Turing_equivalent_.28with_a_caveat.29 http://en.wikipedia.org/wiki/Counter_machine#Two-counter_mac... It seems that even 2 counters are enough for Turing machine. My class only came up with 3 counters for pushdown automaton, but I'm still happy with it, since we did it ourselves :)
- alok-g 15y ago
  Thanks. Helpful again. My understanding (after reading your first comment; would not have figured it out by myself!) was right (though incomplete still till I read the Wikipedia page).
jules 15y ago
One integer variable is enough, because it effectively gives you infinite memory. Three times infinite memory is as much as one times infinite memory. What matters is not the number of integer variables, but which operations you're allowed to do on them. If 3 integer variables i,j,k with operations o1,o2,...,on are enough to encode a stack, then you can do the same with one integer variable x. You just represent i as all the bits in x whose position is 0 mod 3, j as all the bits whose position is 1 mod 3 and k as all the bits whose position is 2 mod 3. Then you just modify operations to only work on those bits that the operation applies to. For example if you have an operation increment_i, and you start with i=j=k=0 then it works like this: ijkijkijk... start: i=0,j=0,k=0 and x = 000000000... increment_i: now i=1,j=0,k=0 and x = 100000000... increment_i: now i=2,j=0,k=0 and x = 000100000... increment_i: now i=3,j=0,k=0 and x = 100100000... increment_i: now i=4,j=0,k=0 and x = 000000100... And if you increment_k then it works on the other bits: ijkijkijk increment_k: now i=4,j=0,k=1 and x = 001000100... increment_k: now i=4,j=0,k=2 and x = 000001100... increment_k: now i=4,j=0,k=3 and x = 001001100... increment_k: now i=4,j=0,k=4 and x = 000000101...
- xyzzyz 15y ago
  Our model allowed us only to do INC, DEC and ZERO? on a counter, and it's easily seen that you cannot implement 2 counters using 1 counter with only ZERO?, INC and DEC, for instance by noting that you can recognize a^n b^n c^n language using automaton with two counters, you can (trivially) implement automaton with one counter using pushdown automaton, so if you were able to implement 2 counters using 1 counter, you could recognize a^n b^n c^n using pushdown automaton, which is easily seen to be impossible by applying pumping lemma for context free languages and usual characterization of pushdown automatons in terms of context free languages.

djcapelis 15y ago

You're way off the mark. While it annoys me that computers are constantly modeled as Turing Machines when it's much more appropriate that they be modeled as LBAs (Linear Bounded Automata) it does not have a huge bearing on computational feasibility in practice. While LBAs vs. TMs do have entirely different definitions and notions of what is and what is not undecidable (for instance, the halting problem is decidable for computers since they're LBAs. It's just impractical.) this only really becomes a theoretical difference. Suggesting that an x86 PC is limited to the level of computational complexity of regular grammars is just wrong. LBAs are capable of context sensitive grammars and are much more capable than a FSM and absolutely can compute more. In real life, computers can be modeled as turning machines without much issue. Memory is generally Big Enough(tm) that problems undecidable on TMs are terribly infeasible to attempt even though theoretically they are actually decidable. And as long as the problem has a small enough state space, the computational expressiveness is the same. In practice, this occurs often enough that people still call computers turing machines even though they aren't.

xyzzyz 15y ago
Of course it makes more sense to model real life computers as LBAs. Still, it does not change the fact that given a computer, it has bounded, and not linearly bounded amount of memory, and that makes them no stronger than regular expressions. Of course that there's no practical difference for programmers. Of course the problem space is usually small enough. But it only proves my point: applying abstract terminology to real-life stuff does not necessarily make sense all the time. It makes more sense to take. say, C or Python programming environment, instead of x86, as a computing model. It's enough to assume that malloc never fails to have genuinely Turing complete device.
- djcapelis 15y ago
  > and that makes them no stronger than regular expressions Again, no. This is simply not how computational complexity works and this statement is factually incorrect. Please do your research.
  - 15y ago

RockyMcNuts 15y ago

fair enough - sufficiently large memory is also necessary. For that reason you couldn't write a Lisp interpreter on the 12C, although you could write one in the 12C language. The point I was trying to make is that the simplest languages are Turing equivalent (given sufficient memory), because they have the necessary tests and control flow. The TFA goes a bit astray IMHO when it says Turing completeness is not necessary for a language to be useful. Turing completeness is a low bar and even SQL as generally implemented hurdles it. sorry, I wasn't incredibly rigorous or clear.