Re: Alan Turing's Halting Problem is Incorrect (FINAL PART)
From: Martin Shobe (mshobe_at_sbcglobal.net)
Date: 07/09/04
- Next message: Barbara Schwarz: "Re: Harassed by remote voice to skull. Yikes!"
- Previous message: The Ghost In The Machine: "Re: limitation to induction on finite bounds"
- In reply to: Peter Olcott: "Re: Alan Turing's Halting Problem is Incorrect (FINAL PART)"
- Next in thread: Peter Olcott: "Re: Alan Turing's Halting Problem is Incorrect (FINAL PART)"
- Reply: Peter Olcott: "Re: Alan Turing's Halting Problem is Incorrect (FINAL PART)"
- Messages sorted by: [ date ] [ thread ]
Date: Fri, 09 Jul 2004 17:50:01 GMT
On Fri, 09 Jul 2004 12:22:01 GMT, "Peter Olcott"
<olcott@worldnet.att.net> wrote:
>> Of course I'm including hypothetical and theoretical programs. If you
>> want to know if something is possible, you *have* to include them.
>> Otherwise, you're just talking about what has already been done.
>>
>> And who's to say what will constitute real work twenty years from now?
>> It has certainly changed enough in the last twenty years.
>>
>> Martin
>
>Yet it still seems unreasonable to include programs that are
>designed with the specific intention of making something impossible,
>especially when there are no other types of programs that produce
>this same result.
Yet you can't just rule them out, because someone might accidently
supply such a program. (In fact, one cannot, in general, determine if
some arbitrary program is a counter-example.) And you certainly don't
want the Halt program to return a wrong answer.
Also (and possibly more importantly) it seem
>(try and find an error, there might be one). that the conclusion
>derived is also incorrect. If one expands the problem definition just
>a little, and eliminates the restriction to Boolean result, then the
>impossible now becomes possible.
Not really. Any encryption/encoding that a Turing machine can
produce, can also be undone by a Turing machine. This leaves you
right back where you started. Adding extra information doesn't help
as that can be ignored. The closest I can think of is to add a "can't
tell" output. But this doesn't really make the impossible possible,
it just lets you answer the question some of the time. Though that
*might* be enough to make the impossible practicle.
As long as the encoding of
>the result is unknown to the counter-example program, then
>the counter-example program can not possibly thwart the
>WillHalt() function. This SOLUTION to the Halting Problem
>only requires the assumption that one program's output can be
>secure from another. I think that PGP ensures that.
A Turing machine can unencrypt PGP. If I remember correctly, It
doesn't even need the key (as long as you're willing to wait). Not
that it really matters since the key *is* available to some of the
counter-examples for that particular solution.
You can have something that is more powerful than a Turing machine
(like an Oracle) produce output that a Turing machine can't decode.
At that point, you might as well just have this machine give the
correct Halts/Doesn't halt answer, since an Oracle can give the
correct Halts/Doesn't halt for all Turing machines.
Martin
- Next message: Barbara Schwarz: "Re: Harassed by remote voice to skull. Yikes!"
- Previous message: The Ghost In The Machine: "Re: limitation to induction on finite bounds"
- In reply to: Peter Olcott: "Re: Alan Turing's Halting Problem is Incorrect (FINAL PART)"
- Next in thread: Peter Olcott: "Re: Alan Turing's Halting Problem is Incorrect (FINAL PART)"
- Reply: Peter Olcott: "Re: Alan Turing's Halting Problem is Incorrect (FINAL PART)"
- Messages sorted by: [ date ] [ thread ]
Relevant Pages
|
