Re: Yet another Attempt at Disproving the Halting Problem

From: George Greene (greeneg_at_greeneg-cs.cs.unc.edu)
Date: 08/08/04 

Date: 08 Aug 2004 08:24:48 -0400

"Peter Olcott" <olcott@worldnet.att.net> writes:
 : Turing contructed a paradox to show that creating a Halting Analyzer
 : is not possible.

Right.

 : If the halt analyzer simply refrains from ever providing its result to any
 : program that is being analyzed,

This is NOT POSSIBLE.
The halt analyzer ALWAYS PROVIDES
a result, WHENEVER it is called.
BY DEFINITION. IT MUST ALWAYS PROVIDE A RESULT.
For a TM, "to provide a result" means "to halt".
ALL TMs, by definition, provide, as their result, whatever the contents of
their output tape is, when they halt. THE ONLY way in which ANY TM CAN EVER FAIL
to provide a result is by not halting.

 : then this paradox becomes completely
 : impossible to construct. That's exactly all that it takes, it takes nothing
 : at all more than this. It really is just as simple as that.

Agreed that it takes nothing more than that.
The problem is, you can't HAVE even AS MUCH AS that.
Your "analyzer" (call it H), when IT gets called
with H(M,w), CANNOT KNOW "who" is calling it or
"who" it might be giving its result to. What H(M,w) is, and
indeed, what TM(s,d) is, for ANY TM with ANY two input parameters,
IS ALWAYS FULLY DETERMINED, WITHOUT any reference to "what program"
might be "calling" H or TM. And H, in particular, is DEFINED
as needing to work ON ALL programs with ALL input-strings.
So what you are talking about is just bullshit.

Maybe an analogy will help:
the usual arithmetic "plus" is, like H, a binary function of
2 arguments. 2+3=5. ALL THE TIME. You cannot say
"I'm talking about a + that refuses to return its result to
a program that gimbles". +(2,3) is *5*. ALWAYS. ALL THE TIME.
COMPLETELY IRRESPECTIVE of what "program" the "call to +" may
be occurring in. There is no way for + to "Withhold" its answer
because the wrong program wants to know.
ALL TURING MACHINES IN GENERAL ARE LIKE THAT.
THEY DO *NOT* *HAVE* CALLER-ID! 

-- 
 --- The history of our nation has demonstrated that separate is seldom, if ever, equal.
 --- (Feb.3,2004) Supreme Judicial Court of Massachusetts (4-3), adv.Sen.#2175

Relevant Pages