David Monroe

David H. Monroe, M.S.P.H., Ph.D. Toxicologist, Monroe Toxicology Consultant in Toxicology and Risk Assessment. Litigation support and expert witness. monroe_toxicology@hotmail.com (571)221-8538

My current views on the HaltingProblem:

It does seem to me that the example programs given as "proof" of the HaltingProblem either infinitely repeat the calling up of a program or end with a program trying to execute with no input.

Does trouble(t) halt? (where string t represents the algorithm trouble)

function trouble(string s)

     if halt(s, s) = false
         return true
     else
         loop forever

Doesn't trouble(t) just infinitely repeat "if halt(t,t); if halt(t,t)...?"

Question: Can anyone write a simple program (that would actually run ) as an example of the halting problem, that doesn't just boil down to the illogical statement:

 "IF P(Q)=no, P(Q)=yes", 

or a quest for a mathematical unknown?

The "proof" of the halting problem given in section 2 of the HaltingProblem page has a problem: "program P that can tell you whether any program halts or not for given input data." and "program Q based on P which, if P says its input program doesn't halt, immediately halts, and if P says the program halts, goes into an infinite loop.* Feeding Q(Q) to P..."

When you feed Q(Q) to P, P begins to execute Q(Q), which makes Q begin to execute P(Q), which makes P begin to execute Q, which makes P begin to execute with no input.

It seems to me that all you need to do is add one more line of code to program P that reads something like "If P has no input, output=ILLOGICAL PROGRAM, halt.

See also: http://en.wikipedia.org/wiki/Halting_problem

-- DavidMonroe (yes, I'm an amateur programmer, but expert toxicologist at the US EPA)

---

Hi David. Your first mistake is that P would "execute" Q. To begin with, if P were to execute the programs it tries to decide P would fail for tons of programs (precisely all programs that dobn't halt) not only a carefully crafted counter-example. The second mistake is that if P is defined as

 P(program, input) = 
   exec program(input);
   // we arrived here therefore program(input) finished
   return true

Then upon feeding it with the Q above the call stack will look like

 P(Q,Q)
  --> Q(Q)
      --> P(Q,Q)
             --> Q(Q)
                 --> P(Q,Q) ...

But then again imagining that P will try to execute the programs given to it is just a misleading intuition, a a better intuitive image would be that P is an AI program that will try to prove a theorem about program(input) -- whether it halts or not. The HaltingProblem tells us that there will never be such an intelligent machine, which is almost the same as with Godel's theorem which tells us that that we cannot know everything (or at least that there are mathematical puzzles that cannot be solved).