On Nov 6, 2006, at 12:20 PM, Michael L Torrie wrote:
The mistake you are making is that although in theory an infinite
string
will require infinite time to process, we can prove inductively
that it
will in fact reach the end of the input, even if the end is infinity.
This is different from the halting problem as the halting problem
describes a set of problems where the input string may be fixed but
the
turing machine head is going back and forth (not quite the right words
here) but we cannot prove whether it will ever reach the end of the
string or just loop forever.
Actually, after re-reading things, I don't think that's what he was
thinking of at all. Let me take a crack at it, and we'll see if
Daniel thinks I've characterized the article well.
When programming in C, C++, or Java (among others), standard numeric
variables have a fixed size and roll over when they overflow.
Therefore, an algorithm that relies on one of these variables to work
will invariably fail when the capacity of that variable is exhausted
and it rolls over. So a naive algorithm that would work on a Turing
machine breaks down in the real world not due to exhausting the
memory on the machine, but simply exhausting the bits available in a
variable.
This really has very little to do with Turing machines, and a lot to
do with computer languages and their semantics. The above languages
are based on the semantics of the underlying computer (which, though
capable of solving the same set of problems as a Turing machine given
the proper programming and enough storage, are not the same) and so
programs written naively in them have the same limitations of the
underlying machine.
When matching of truly arbitrary strings is required, one can step up
to using math libraries that support unbounded numbers for the
parentheses count, and the problem goes away until the memory of the
computer is completely exhausted, at which point you get a memory
exhaustion error instead of an incorrect answer.
Or, one could use a language with different default semantics for
numeric variables. Common Lisp, for example, automatically promotes
a fixed-size numeric variable to an arbitrary-size one when it
overflows its bits. This can cause an unexpected decrease in
performance if you cause the promotion to happen with a big input
string, but you never get a bogus answer due to variable overflow.
--Levi
/*
PLUG: http://plug.org, #utah on irc.freenode.net
Unsubscribe: http://plug.org/mailman/options/plug
Don't fear the penguin.
*/
