I may have the wrong word for it, but the language of matched
parentheses is not decideable with a Turing machine. That is, there
is no possible (real) Turing machine that can decide every string of
matched parentheses, because a string can be infinitely long and a
real Turing machine has finite storage space. For ease of example,
say the biggest Turing machine on earth can hold four parentheses,
after which it rolls over. Now look at this string:
((((()
It's going to say that that string is in the language of matched
parentheses when it's not, because when it hits the fifth "(" it'll
roll over and count that as the first one. (May be off by one here)
and see one ")" and go "Yep, they match." No matter how big your
Turing machine gets, char-storage-wise, you can always add one more
"(" and make it fail.
That's what I meant.
Dan
On 11/6/06, Steve <[EMAIL PROTECTED]> wrote:
How is that turing incomplete?
Look at the first requirement...
Is this list of parenthesis balanced?
/*
PLUG: http://plug.org, #utah on irc.freenode.net
Unsubscribe: http://plug.org/mailman/options/plug
Don't fear the penguin.
*/
