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.
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.
Again, no. This is simply not how computational complexity works and this statement is factually incorrect. Please do your research.
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...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 :)
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.
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.