Re: Daryl, Dave, Barb and the Georges' source of Confusion

From: |-|erc (gotcha_at_beauty.com)
Date: 07/03/04 

Date: Sat, 03 Jul 2004 11:18:34 GMT

"Peter Olcott" <olcott@worldnet.att.net> wrote in
> > >> : I do not accept the validity of this counter-example program.
> > >> No program just halts or just doesn't halt:
> > >> EVERY program has INFINITELY MANY DIFFERENT cases of halting or non-
> > >> halting, because it can have infinitely many DIFFERENT INPUTS.
> > >
> > > That is why I greatly simplified it with my version
> > > of the counter-example prrogram, there are only
> > > three possible inputs;
> > > "Y"
> > > "N"
> >
> > Actually, there are only two acceptable inputs, there is still an infinity
> > of possible inputs; none of which will make the program loop by the way.
>
> Categorically there are only three possible categories of inputs:
> (1) "Y" ypou say it halts, and it fails to halt.
> (2) "N" You say that it will not halt, and it halts.
> (3) Everything else, in which case you have failed to correctly
> answer the question of whether or not it halts.
>
> CECE Within a (categorically exhaustive complete enumeration),
> each any every possible answer fails to correctly determine if
> the program will halt.
>

Peter seems correct to me because the Halting proof, although it does prove
an absolute limit on a level playing field, is a poor representation of this question.

Is there a program that can systematically determine whether any given
program will halt or not?

|-|erc wrote:
> As Peter originally put it, the output of halt should reasonably be
> expected to have 3 options :
>
> 1 / the input halts
> 2 / the input wont halt
> 3 / the input contains a reference to Halt()
>
> Isn't this exactly what Peter is saying?
> Does it stand up against the halting proof? Why?

   "Does a program exist that can systematically tell me whether a given input program will halt?"

That is the question, halting proof is an ill conceived representation of the question,
since it answers NO.

The correct answer is, COULD BE, as long as it doesn't analyse itself.

A trillion dollar software industry suggests it could be an interesting problem.

Would this function be computable?

> output expected to have 3 options :
>
> 1 / the input halts
> 2 / the input wont halt
> 3 / the input contains a reference to Halt()

the basic principle is like so.

function f1 (x)
  return x + 3
end

function f2 (x)
  while true
  wend
end

function f3 (x)
  if halt(x,x) then
     while true
     wend
  endif
end

halt(f1, 1) = "halts"
halt(f2, 1) = "nothalts"
halt(f3, 'f3') = "reference_to_halt"

where is the contradiction?
Herc

Relevant Pages