Re: Can you find anything wrong with this solution to the Halting Problem?

From: Chairman of the Ozzy Osbourne Appreciation Society (mathgeekxxxxii_at_hotmail.com)
Date: 07/14/04 

Date: Wed, 14 Jul 2004 14:47:06 GMT

Peter Olcott wrote:
>>Again, you've failed to understand the meaning of "proof by contradiction".
>>Saying, "I am right and you are wrong" doesn't change this fact.
>
>
> You can not even correctly make this assessment without
> first reading what I have said.
>
> http://home.att.net/~olcott/halts.html
>

Actually, he can correctly make that assessment without reading
anything you have to say. What you're missing is that since
it's been proven that the hypothesis:

     "A Turing machine exists which solves the halting problem"

results in a contradiction, there's no question that the
_hypothesis_ is false.

I briefly checked your web site, and your main concern with
the halting proof seems to be that

(1) You conceptualize a Turing machine as a scheduled process
     on a modern OS.
(2) You conceptualize the program that confounds the supposed
     TM that solves the halting problem as a similar process
     which does some form of IPC to determine its behavior.
(3) You conclude: if we block all forms of IPC, then the
     counter example program can't function properly, and
     the proof fails.

But, this is not the case.

Since we have supposed the existence of a TM which solves
the halting problem we know it exists, and must have
an encoding, or to continue the analogy with real-world
programs, source code. I'll refer to the supposed program
that solves the halting problem as TM1.

Given the source code for TM1, it's no problem at all
to construct or write a second program which bases its
behavior on TM1 simply by embedding the source code
or text of the first program into that of the second.
Thus, the absence of IPC during execution of TM1 is
immaterial. The behavior of the counter-example program
isn't based on run-time IPC but based on the static
encoding, or source code of TM1.

This shouldn't seem mysterious or abstract at all,
I often rip out portions of C++ code from one project
and insert it into a second project. If a program
existed which "solved" the halting problem, in addition
to being able to examine its source code I could embed
either all of it or portions of it into a project of
my choosing.

Regarding your posting style: It helps readability if
you don't snip the names of the posters to whom you're
responding. 

--
Roman to Arabic to reply by email

Relevant Pages

  • Re: WriteProcessMemory and ReadProcessMemory
    ... answer questions with full knowledge of their software (including source code ... > to use WriteProcessMemory/ReadProcessMemory for IPC. ... > In addition to Administrators, developers also need debug privilege, but you ... >> If you want to use the memory for IPC communication than use SHARED MEMORY ...
    (microsoft.public.platformsdk.security)
  • Re: [Lit.] Buffer overruns
    ... >>If we turn the program loose on its own source code, ... > I am quite familiar with the halting problem and Rice's theorem, ... But this leaves out the issue of the analyzee programs input. ... But if the analyzee is a language interpreter, ...
    (sci.crypt)
  • Re: Can you find anything wrong with this solution to the Halting Problem?
    ... > Given the source code for TM1, ... > to construct or write a second program which bases its ... Even the statically encoded source code proves that I ...
    (comp.theory)
  • Re: New Binary Bruteforcing Method Discovered
    ... I was far from claiming it as "my technique". ... > Knowing the way to solve the halting problem for infinite Turing machines ... can oversee all functions in source code (this problem seems to be a white-box ...
    (Vuln-Dev)
  • Re: Alan Turings Halting Problem is Incorrect (PART-THREE)
    ... When I ask if the program Halts, I am not asking what other ... If I was playing the same game as you, then the Halting Problem ... TM1 says no, TM2 toggles this to yes, and then ...
    (sci.logic)