Re: Disproof of the Halting Problem's Conclusion

From: Kevin Stern (K-Stern_at_neiu.edu)
Date: 07/22/04 

Date: 22 Jul 2004 05:30:22 -0700

I'm disappointed that you did not respond to the remainder of my post
- that's really where the meat is. Did you get a chance to read it?

Regarding the response that you did provide: this is what I said,
sir, I said that you've defined a programming language that allows
only a subset of all possible programs. In particular, assuming that
Halt(x, y) is recursive, you do not allow the very obviously recursive
program:

Counter{
  if Halt(Counter, '') then Loop
  else stop
}

(if you do allow this program then you would not be saying that Halt
is recursive - because you'd immediately realize that this program,
and this program alone, is enough to show that Halt is not recursive).

You see, in the theory of computing, if Halt is recursive then Counter
is recursive - there is no restriction to this whatsoever. For a nice
real world example we can think of Virus(x) as a program that looks at
x and determines if it is the encoding of a computer virus. When
someone comes out with such a program, I'd very much like to add the
following to all of my programs:

ArbitraryProgram {
  If Virus(ArbitraryProgram) then stop
  else ArbitraryProgram();
}

Again, please read my explanation below and see if it makes sense.

"Peter Olcott" <olcott@worldnet.att.net> wrote in message news:<yJDLc.120796$OB3.55058@bgtnsc05-news.ops.worldnet.att.net>...
> > I have read your website and I understand what you are saying. You
> > are working within a programming language (call it PeterLanguage) that
> > allows only a subset of all possible programs. You are showing that,
> > perhaps, it is possible to determine whether or not a particular set
> > of programs halt, but your set does not contain all possible programs
> > and the Halting Problem asks in terms of all possible programs.
> > Please let me know if you understand this?
>
> No this is not quite it.
> I have redefined the Halting analyzer such that the counter-example
> program that shows that solving the Halting Problem is impossible
> can not exist.
>
> The basic way of doing this is essentially changing the halting analyzer
> from returning Boolean to its caller, to returning nothing to its caller.
>
> > I've presented the standard recursion theoretic proof of the halting
> > problem below, which I hope will clear things up a bit. I assume that
> > you've seen Cantor's proof that the Reals are uncountable? This is a
> > similar diagonalization argument (I will go over it again):
> >
> > We enumerate all possible Turing machine (this can be done because a
> > TM is simply a finite string over a finite alphabet. These are, now,
> > all possible computer programs - the whole kaboodle:
> >
> > tm_1 tm_2 tm_3 [...]
> > tm_1 1 0 1 [...]
> > tm_2 0 0 1 [...]
> > tm_3 1 1 0 [...]
> > [...]
> >
> > In addition, (x, y) = 1 if tm_x(tm_y) halts and it is 0 if tm_x(tm_y)
> > does not halt. Again, these are the only two possibilities, something
> > cannot sort-of halt ... in fact, let's DEFINE 'does not halt' as
> > follows:
> >
> > A TM does not halt if it is not the case that it halts.
> >
> > It should be excrutiatingly clear that a TM either halts or not ...
> >
> > If the halting problem is solvable (as you claim it is), then
> > certainly this program is solvable:
> >
> > D(x) {
> > if Halt(x, x) = 'No' then Halt
> > else Loop Forever
> > }
> >
> > Now the question becomes, is this a TM?
> >
> > Well, we have a list of TMs, let's see if it's in the list:
> >
> > Is it TM_1? Well, it cannot be, because
> >
> > D(TM_1) = if Halt(TM_1, TM_1) = 'No' then Halt else Loop Forever
> >
> > And we can clearly see that TM_1(TM_1) halts (from the graph that I've
> > constructed), so D(TM_1) does not halt.
> >
> > Is it TM_n? Well, it cannot be, because
> >
> > D(TM_n) = if Halt(TM_n, TM_n) = 'No' then Halt else Loop Forever
> >
> > And we can clearly see that if TM_n(TM_n) halts then D does not halt
> > and if TM_n(TM_n) does not halt then D halts.
> >
> > It, therefore, cannot be any Turing Machines in the list of all Turing
> > Machines. D is not a Turing Machine and, therefore, Halt is not a
> > Turing Machine.
> >
> > I will try to anticipate your reply (I hope that I am wrong):
> >
> > We cannot compile a program with the line D(TM_n) if we cannot
> > determine whether or not TM_n halts. This is fine, no problem, REMOVE
> > a finite number of TMs from the list that you don't like ... certainly
> > none of them are the HALT program that you're looking for since you've
> > hand picked them as ones that you don't like because they 'use' the
> > halt program to cause a paradox (in fact you will remove no TMs from
> > the list because there is no Halt program and, therefore, there is no
> > paradox to be caused). Please, again, let me know if this makes any
> > sense. Please do not simply write one line and tell me that I am
> > wrong - let me know if you understand my argument and, if not, where
> > it is confusing. Once you understand my argument then we can talk
> > more about whether or not you've solved the halting problem.
> >
> > Kevin
> >
> > "Peter Olcott" <olcott@worldnet.att.net> wrote in message news:<0eiLc.292197$Gx4.51255@bgtnsc04-news.ops.worldnet.att.net>...
> > > "Kevin Stern" <K-Stern@neiu.edu> wrote in message news:ca77e32d.0407191227.2715e440@posting.google.com...
> > > > void LoopIfHalts(string SourceCode, string InputData)
> > > > {
> > > > if (WillHalt(SourceCode, InputData) == TRUE)
> > > > while (TRUE) // loop forever
> > > > ;
> > > > else
> > > > return; // FALSE or UNKNOWN
> > > > }
> > > >
> > > > This code has nothing to do with the halting problem. If you notice:
> > > >
> > > > LoopIfHalts(LoopIfHalts, LoopIfHalts) calls WillHalt(LoopIfHalts,
> > > > LoopIfHalts) which, I assume, tests whether LoopIfHalts(LoopIfHalts)
> > > > halts. But this is the one parameter version of LoopIfHalts (a
> > > > completely different program ... you have the two parameter version
> > > > above, which will pose no problems whatsoever (either that or you'll
> > > > get a syntax error because you're only providing one parameter for a
> > > > two parametered function).
> > >
> > > http://home.att.net/~olcott/halting/example.html
> > > examine this and get back to me
> > >
> > >
> > > > This may help: It is not the Halt portion of the halting problem that
> > > > causes problems, it's the NoHalt portion. Halt is recursively
> > > > enumerable ... we can confirm that a program halts within a finite
> > > > amount of time - we cannot decide which programs fail to halt within a
> > > > finite amount of time, though.
> > > >
> > > > Let's say that we can ... NoHalt(x, y) is the program that we want.
> > > >
> > > > Well then what of D(x) = return NoHalt(x, x)?
> > > >
> > > > This is the anti-diagonal of the following enumeration of all Turing
> > > > Machines:
> > > >
> > > > tm_1 tm_2 tm_3 [...]
> > > > tm_1 1 0 1 [...]
> > > > tm_2 0 0 1 [...]
> > > > tm_3 1 1 0 [...]
> > > > [...]
> > > >
> > > > where row_x col_y = 1 if tm_x halts on input 'tm_y' and 0 otherwise.
> > > >
> > > > so, specifically, there can be no row that outputs the correct
> > > > sequence of 1's and 0's and, interestingly, the conclusion is that no
> > > > row represents D - D is not a TM.
> > > >
> > > > Kevin
> > > >
> > > > "Peter Olcott" <olcott@worldnet.att.net> wrote in message news:<xCOKc.111569$OB3.81647@bgtnsc05-news.ops.worldnet.att.net>...
> > > > > "Kenneth Doyle" <nobody@notmail.com> wrote in message news:Xns952B8AF6F38FCnobodynotmailcom@61.9.191.5...
> > > > > > "Peter Olcott" <olcott@worldnet.att.net> wrote in
> > > > > > news:UHwKc.277072$Gx4.4006@bgtnsc04-news.ops.worldnet.att.net:
> > > > > >
> > > > > > > No. as long as a single unmodified copy of the my original program
> > > > > > > exists then this single copy still represents the required single
> > > > > > > counter-example to disprove the statement:
> > > > > > > No program can ever be written to determine whether any arbitrary
> > > > > > > program will halt
> > > > > > >
> > > > > >
> > > > > > Your original program? You mean the one that pretends that the two letters
> > > > > > 'Y' and 'N' are complete programs? You just said, in a recent posting,
> > > > >
> > > > > No these are the two sets of programs that I am talking about now.
> > > > > http://home.att.net/~olcott/halting/example.html
> > > > > I haven't been talking about that other program for more than a week.
> > > > > Read this whole link, and you will see what I mean.
> > > > >
> > > > > > that the input must be a program's code. You said that if the input string
> > > > > > was an english poem, then it wouldn't count. Or are you talking about your
> > > > > > other original program?
> > > > > >
> > > > > >
> > > > > > --
> > > > > > CodeCutter - good, fast and cheap; pick two.

Loading