Dan Fabulich <daniel.fabulich@yale.edu> From:
> Wellll... If it only has a finite amount of tape,
A Turing machine has an unlimited amount of tape, that is, it has
as much as is needed, but provided it only runs for a finite amount
of time it will only use a finite amount of tape.
>and it halts when it runs out of tape, you should be able to figure it out.
Nope, the simple little problem I gave the Turing Machine is called the
Goldbach Conjecture, nobody has a proof to show it correct and nobody
has found a counterexample to prove it wrong , and it has been tested to
about a trillion, of course it might fail at a trillion +2. If you knew if this
simple little machine would eventually stop then that would mean you've proven
the conjecture false, if you knew it would never stop then you'd have proven it true.
But Brilliant minds have worked on this problem for centuries and we
still don't know if it's true or not, and if it's Turing undecidable we will never
know. And if it is Turing undecidable we will never know that either, for
billions of years we would just keep trying, unsuccessfully, to prove it right, and
keep trying out numbers looking, unsuccessfully, for a counterexample to prove
it wrong. You can't predict what a finite state machine will do.
John K Clark jonkc@att.net
This archive was generated by hypermail 2b30 : Mon May 28 2001 - 09:50:36 MDT