4 ms·

If you can do a test, a loop, and a write, you're Turing complete IIRC. Hell, the DOS shell is Turing complete, your HP-12C is Turing complete. So ANSI SQL wit

If you can do a test, a loop, and a write, you're Turing complete IIRC. Hell, the DOS shell is Turing complete, your HP-12C is Turing complete. So ANSI SQL with selects only may not be Turing complete, but pretty much all SQL implementations are, since they added loops, not to mention stored procedures etc. All languages are Turing complete and equivalent from a computability standpoint. That's the sense in which it means nothing for a language to be Turing complete - they all are. They are different in terms of expressive power, computational efficiency for different problems. Can you do closures in HP-12C assembler? Of course! just write a Lisp interpreter in assembler, and there you go.

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...
praptak 15y ago
"If you can do a test, a loop, and a write, you're Turing complete IIRC." No. What you got is a while-program. The main limitation of a while-program is the finite number of variables it has. Its computational power therefore depends on the data types it can work on. Of course if you have stacks, dynamic arrays or equivalent then you're basically Turing-complete. Even if all you have is unbound integer arithmetic, you can emulate the infinite tape on the bits of a large integer. If you only have finite types, then the while-program obviously has a finite number of states, so it's equivalent to an FSM.
0x12 15y ago
Your understanding is limited and confuses rather than enlightens. A test, loop and write are not the definition of Turing complete. See: http://en.wikipedia.org/wiki/Turing_complete http://en.wikipedia.org/wiki/Turing_complete And for a very interesting take on this: http://en.wikipedia.org/wiki/Rule_110 http://en.wikipedia.org/wiki/Rule_110 And http://en.wikipedia.org/wiki/One_instruction_set_computer http://en.wikipedia.org/wiki/One_instruction_set_computer

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

praptak 15y ago

"If you can do a test, a loop, and a write, you're Turing complete IIRC." No. What you got is a while-program. The main limitation of a while-program is the finite number of variables it has. Its computational power therefore depends on the data types it can work on. Of course if you have stacks, dynamic arrays or equivalent then you're basically Turing-complete. Even if all you have is unbound integer arithmetic, you can emulate the infinite tape on the bits of a large integer. If you only have finite types, then the while-program obviously has a finite number of states, so it's equivalent to an FSM.

0x12 15y ago

Your understanding is limited and confuses rather than enlightens. A test, loop and write are not the definition of Turing complete. See: http://en.wikipedia.org/wiki/Turing_complete http://en.wikipedia.org/wiki/Turing_complete And for a very interesting take on this: http://en.wikipedia.org/wiki/Rule_110 http://en.wikipedia.org/wiki/Rule_110 And http://en.wikipedia.org/wiki/One_instruction_set_computer http://en.wikipedia.org/wiki/One_instruction_set_computer