Re:Turing completeness bullshit
by praptak on Wednesday September 28, 2011 @04:14AM
(#3046959)
"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.
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.