From: Dan Fabulich (daniel.fabulich@yale.edu)
Date: Fri Dec 15 2000 - 10:53:33 MST
John Clark wrote:
> 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.
Right.
> >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.
I knew that, actually. What I was calling attention to is the fact
that an ACTUAL Turing device would have a finite amount of tape, and
so could only actually test a finite set of numbers.
In an interesting sense, the standard theoretical Turing machine with
an infinite amount of tape really WOULD be an infinite-state machine:
it could put an infinite amount of tape into any of an infinite number
of states.
> 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.
Ah, but if you told me: "Listen, you can never predict when this
Pentium II will stop looking for a counter example to the Goldbach
Conjecture," I could say: "Yes, I can. This machine has 512MB of RAM,
so it can't hold a number greater than 2^(512 * 1024^2 * 8). All I
need is a computer with, say, 1024MB of RAM to check and see whether
your Pentium II machine will halt."
Of course, there's no way to tell if that 1024MB machine will halt
without a bigger machine than it, and so on. So there's no way to
tell if an imaginary Turing machine with an infinite amount of tape
will halt for an arbitrary problem.
-Dan
-unless you love someone-
-nothing else makes any sense-
e.e. cummings
This archive was generated by hypermail 2.1.5 : Fri Nov 01 2002 - 15:32:24 MST