mozy contest: problem 1 PHP solution

Daniel C. dcrookston at gmail.com
Mon Nov 6 11:09:10 MST 2006


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 <smorrey at gmail.com> wrote:
> How is that turing incomplete?
> Look at the first requirement...
> Is this list of parenthesis balanced?



More information about the PLUG mailing list