Re: Yet another Attempt at Disproving the Halting Problem

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

Date: 02 Aug 2004 16:06:47 -0400

 : > Mitch Harris wrote:
 : > >
 : > > "There is a TM that determines if every TM halts on given
 : > > input" is not a theorem because there is at least one TM for
 : > > which any proposed solution will fail to determine halting.

 : "Aatu Koskensilta" <aatu.koskensilta@xortec.fi> wrote in message news:ceaac3$ppf$1@phys-news1.kolumbus.fi...
 : > This isn't true. There is no TM which every proposed solution fails to
 : > determine the halting of. Rather, for every TM M there is a TM E_M and
 : > input x, for which M does not correctly determine the halting.
 :

"Peter Olcott" <olcott@worldnet.att.net> writes:
 : But the proof only shows that TM E_M and input x does not correctly
 : determine halting for itself.

You are fucking illiterate.
Seriously, the ability to READ accurately is probably THE MOST important
talent a computer programmer can have. And you have not accurately parsed
what you are so ignorantly trying to contradict here. AK did NOT say (as you
so idiotically mis-paraphrased him) that "TM E_M and input x does not
correctly determine halting for itself". It shows that TM *M* (NOT E_M)
does not correctly determine halting for TM *E_M* and input x. NOWHERE here
is anything talking about "itself".

 : TM M can determine if TM E_M halts on x.

No, it can't.
E_M BY DEFINITION is the TM for which there is an x such that M gets it wrong.

 : All that is has to do is to see that it will not make either of the transitions

Antecedent of "it" is ambiguouus in the above. The first "it", which you mis-type
as "is", has "M" as its antecedent. The second "it" is unclear. If it is also
"M" then no TM is going to be able to see about itself what it's going to do.

 : to the (it does halt) and (it does not halt) final states. Since neither of these
 : transitions would be defined for the transition function (in this case)

This is just idiotic bull***.
I'm sorry your textbook told you that TMs halt when there
is an undefined transition. This is not really true.
TMs halt when they halt. That doesn't involve any transition.
If you must have it involve one then you should have it involve
transitioning left from the first cell on the tape. The problem
with your text's formalism is that when it proves that any transition
whatsoever would lead to a logical contradiction, you choose to
interpret that as a proof of halting. IT ISN'T.

 : we would know that TM E_M would halt on x.

No, you don't. 

-- 
 --- 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
Quantcast