Re: What is the Result from Invoking this Halt Function?

From: tom_usenet (tom_usenet_at_hotmail.com)
Date: 08/10/04 

Date: Tue, 10 Aug 2004 15:15:05 +0100

On Tue, 10 Aug 2004 13:09:52 GMT, "Peter Olcott"
<olcott@worldnet.att.net> wrote:

>
>"tom_usenet" <tom_usenet@hotmail.com> wrote in message news:o1ghh01spd2hv8o623j4do391vd7fkc6j5@4ax.com...
>> On Mon, 09 Aug 2004 23:51:45 GMT, "Peter Olcott"
>> <olcott@worldnet.att.net> wrote:
>>
>> >
>> >"David C. Ullrich" <ullrich@math.okstate.edu> wrote in message news:0uoeh01oaa1j5lspusqduhq86rabq0sd59@4ax.com...
>> >> On Sun, 08 Aug 2004 17:29:47 GMT, "Peter Olcott"
>> >> <olcott@worldnet.att.net> wrote:
>> >
>> >> >No, I don't have any evidence, all that I have is complete proof.
>> >>
>> >> no, you have given no proof at all.
>> >>
>> >> it really is truly awesome how you can make the same error so many
>> >> times.
>> >
>> >Yeah its me that's making the errors, NOT!
>> >Two people agree that I have correctly refuted this statement:
>> >These are the same people that have been arguing all along
>> >that I just couldn't be right.
>> >
>> >No program can ever be written to determine whether any
>> >arbitrary program will halt
>>
>> No TM can ever be written to determine whether any
>> arbitrary TM will halt. That is irrefutably correct, and I hope even
>> you understand that now.
>
>Two people now agree that I have correctly refuted the above statement.

No, they agreed with your refutation of the proof of a definition that
didn't involve Turing Machines (e.g. the pre-update NIST definition),
and they were incorrect to do that. As soon as one proves that a
particular real world machine is equivalent to a turing machine (which
is regularly done, and certainly applies to register based machines),
then one has proven the halting problem for that machine.

>Perhaps you could look at what I am saying a little more closely?

I've very much enjoyed closely reading quite a few of these threads.

>> Now, the exciting question is, does this apply to programs in the real
>> world? I suspect so (since all of your "real world" refutations have
>> "real world" solutions (such as a camera to see or microphone to hear
>> the result of the halting analysis)), but it can't easily be proven in
>> the same way that the Church-Turing thesis can't.
>>
>> e.g.
>>
>> void LoopIfHalts(arg)
>> {
>> while(SimulatorWithCameraPickup(WillHalt, arg, arg));
>> }
>>
>> Even if WillHalt writes the result in a way that appears to make it
>> "write-only", a simulator can easily extract it (even directly, by
>> intercepting the write to video memory, or whatever).
>
>Yet as many people have failed to see, this does not refute that
>my method would work for every possible input. All that it does
>is to break an otherwise correct program.

No, it forms a logical contradiction, thus proving that WillHalt (a
program that determines whether or not an arbitrary program halts)
can't exist, because it can't work for LoopIfHalts, an example of an
arbitrary program. The concept of a halt analyser has to be applied to
something - a particular abstract machine (such as x86 assembler,
Turing Machines, standard C++ with particular implementation defined
properties, a JVM or whatever). Once you've pinned down your
particular abstract machine (which translates to real world ones
pretty well, losing out only on infinite memory, etc.), it's easy to
prove that you can't write a halt analyser for that machine, using the
abilities of that machine (or any other turing-equivalent machine) -
you just reapply Turing's argument.

Incidently, what form does your WillHalt take? Source code in a
particular language? An .exe? Something else?

Tom

Relevant Pages

  • Re: Can a regular Turing Machine provide Protected Memory?
    ... I assume that you believe that you can construct a TM (a computer program) ... that can determine if any arbitrary program with any arbitrary input will ... These are all equivalent to Turing Machines (indeed, ... successfully predicts whether every program they throw at it will halt! ...
    (comp.theory)
  • Re: Can a regular Turing Machine provide Protected Memory?
    ... I assume that you believe that you can construct a TM (a computer program) ... that can determine if any arbitrary program with any arbitrary input will ... These are all equivalent to Turing Machines (indeed, ... successfully predicts whether every program they throw at it will halt! ...
    (sci.logic)
  • Re: What is the Result from Invoking this Halt Function?
    ... No, it forms a logical contradiction, thus proving that WillHalt (a ... program that determines whether or not an arbitrary program halts) ... The concept of a halt analyser has to be applied to ... Turing Machines, standard C++ with particular implementation defined ...
    (comp.theory)
  • Re: Can a regular Turing Machine provide Protected Memory?
    ... >> that can determine if any arbitrary program with any arbitrary input ... any other arbitrary program given any arbitrary input will halt? ... >> Turing Machines). ...
    (comp.theory)
  • Re: Disproof of the Halting Problems Conclusion
    ... >> is incorrect. ... > any arbitrary program will halt. ... - if "WillHalt" of some description existed ...
    (sci.logic)