Solution to the halting Problem?

[Peter Olcott]

www.halting-problem.com

[Karl Heinz Buchegger]

Peter Olcott wrote:

Since it is possible to write X that does not return a value to its caller, then
its possible to prevent the basis for proving that solving the Halting Problem
is impossible to exist.

Hmm.

There is a wall in front of me. I can see it. But if I close my eyes, the wall
vanishes and thus I have proven that there is no wall.

--
Karl Heinz Buchegger
kb******@gascad .at

[Peter Olcott]

> There is no way to put this nicely: you are completely, 100% incorrect.

The nature of a formal proof is such that a single counterexample
disproves it.

It would be like trying to prove that no cars run by taking one car
and driving it into a tree, so that it does not run. What about all the
cars that were not driven into trees? Don't all these other cars prove
that cars run?
If the thesis was "All cars run correctly." then finding a single broken
car disproves the thesis, even in the presence of an infinite number of
similar, working cars. The halting problem is similar: "There is[0] an
algorithm that can determine if any given algorithm will halt, that will
also itself halt for all possible inputs."[1]

I am not claiming that every implementation of a Halt() analyzer always
works correctly. If I was claiming this then finding a single instance of
a Halt analyzer that does not work correctly would refute my claim.
I am claiming that the Halt analyzer that is implemented according to
my method would work correctly all the time. As proof of this, this
method would correctly process the original Halting Problem, and
determine that it would halt. I will post this example later on.
You refer in your proof to memory protection and specific hardware
devices; none of these are relevant to the halting problem, which deals
solely with algorithms and their inputs and outputs -- usually, the
initial and final states of an ideal Turing machine.
Under the assumption that "any computation that can be carried out
by mechanical means can be carried out by some Turing Machine."
I don't think that it says anywhere in the literature that a solution to
the Halting Problem that can not be implemented as a Turing Machine
doesn't count.

Also sprach Peter Olcott:

In all thoses instances where you do not return the result to the
caller, you have solved the Halting Problem.
Then it's not a general solution to the halting problem, is it? It's a
solution that applies to a subset of possible algorithms.

Not at all. The algorithms that test the return value of the Halt analyzer
are no longer in the set of possible algorithms. They become syntactically
incorrect once the Halt analyzer is changed from returning bool, to returning
void (nothing).
And now, a practical example. Does the following algorithm, as
expressed in C, halt (terminate)? Would it halt if the maximum value of a
long was unbounded (this is, after all, merely a C implementation of an
algorithm written with no respect for bytes)?

int main () {
long i, j, k;
for(i=j=k=1;--j||k;k=j?i%j?k: k-j:(j=i+=2));
}
This is not the Halting Problem. Also from what I understand this does
not form an analytical impossibility.
Spoiler:
Guvf cebtenz frnepurf hagvy vg svaqf na bqq cresrpg ahzore, gura unygf. Vg
unygf vs naq bayl vs fhpu n ahzore rkvfgf, juvpu vf n znwbe bcra dhrfgvba
va zngurzngvpf. Fb, nsgre praghevrf bs jbex, zngurzngvpvnaf unir lrg gb
qvfpbire jurgure n fvzcyr P cebtenz unygf.
<uggc://ra.jvxvcrqvn.be t/jvxv/Unygvat_ceboyrz >

[0] Read as 'Define', if you like.
[1] Actually, it also covers knowing the input to the algorithm under test.

--
Some say the Wired doesn't have political borders like the real world,
but there are far too many nonsense-spouting anarchists or idiots who
think that pranks are a revolution.

[Dave Vandervies]

In article <u-*************** *****@comcast.c om>,
David Hilsee <da************ *@yahoo.com> wrote:

"Peter Olcott" <ol****@worldne t.att.net> wrote in message
news:Ly******* *************@b gtnsc04-news.ops.worldn et.att.net...

Providing one specific instance where the method can be made to fail
does not at all refute that the method works correctly in general.
The challenge is not to produce a program that works correctly in general.
The phrase "in general" really means "some of the time,"

No.

A "general solution" to a problem is a solution that works *all* *the*
*time*. Artificially restricting the set of problems you might be able
to solve means you're only solving it for a set of special cases; this
is rarely interesting.
and it's easy to
produce a program that sometimes works. The challenge is to produce a
program that works on all input programs. That is, it always works, no
matter what.

Yes. This is what's referred to in mathese as a "general solution".
dave

--
Dave Vandervies dj******@csclub .uwaterloo.ca
[This] is otherwise known as 'learning by experience'. I don't often
come across people who publicly state they're not interested in that.
--Arthur van der Harg in the scary devil monastery

[Peter Olcott]

"David Hilsee" <da************ *@yahoo.com> wrote in message news:u-*************** *****@comcast.c om...

"Peter Olcott" <ol****@worldne t.att.net> wrote in message
news:Ly******** ************@bg tnsc04-news.ops.worldn et.att.net...

Providing one specific instance where the method can be made to fail
does not at all refute that the method works correctly in general.
The challenge is not to produce a program that works correctly in general.
The phrase "in general" really means "some of the time," and it's easy to
produce a program that sometimes works.
The challenge is to produce a program that works on all input programs.
That is, it always works, no matter what.

Big difference between the former and the latter. My method works
on the former, yet will not work if you smash the machine that it is
working on, this could be construed to be included in the latter.

It would be like trying to prove that no cars run by taking one car
and driving it into a tree, so that it does not run. What about all the
cars that were not driven into trees? Don't all these other cars prove
that cars run?

Sticking with the car analogy, if I challenge you to produce a car that
always worked if I drove it into any tree, and you produced a car that works

That its not my claim, it is for any input. To be analogous, any grade
or brand of gasoline.
when one drives it into oak trees but not when one drives it into pine
trees, then you have not met my challenge. The challenge is not to produce
a car that runs after driving it into certain trees, so the car does not
meet the requirements described in the challenge.

It does work for any arbitrary program as its input parameter.
There is no program that it can not correctly determine halting
status. It even works for the original Halting Problem example,
as input.
You already said that it does not work for a specific instance, so it does

It works for all inputs. It does not work in all instances such as destroying
the machine that is is running on.
not work for any arbitrary program. To work for an arbitrary program it
must work for all programs, including the "one specific instance" that, by
your own admission above, it fails to handle correctly.

--
David Hilsee

[Peter Olcott]

"Karl Heinz Buchegger" <kb******@gasca d.at> wrote in message news:40******** *******@gascad. at...

Peter Olcott wrote:

Since it is possible to write X that does not return a value to its caller, then
its possible to prevent the basis for proving that solving the Halting Problem
is impossible to exist.

Hmm.

There is a wall in front of me. I can see it. But if I close my eyes, the wall
vanishes and thus I have proven that there is no wall.

--
Karl Heinz Buchegger
kb******@gascad .at

It is not merely an input restriction, if this is all that it is, then I would have
shown nothing of consequence. I have changed the Halt analyzer such that
programs that check its return value can not exist. They can not exist because
they become syntactically incorrect. My idea works for all programs that
can exist.

[Peter Olcott]

"tom_usenet " <to********@hot mail.com> wrote in message news:j8******** *************** *********@4ax.c om...

On Thu, 22 Jul 2004 00:35:24 GMT, "Peter Olcott"
<ol****@worldne t.att.net> wrote:

In case you are unfamiliar, the LoopIfHalts() function is the
counter-example used to prove that the Halting Problem
can not be solved. By making LoopIfHalts() impossible
to construct, the original basis of the halting Problem ceases
to exist.
*If* a solution to the halting problem exists, *then* it *must* be
possible to write WillHalt such that it returns to a caller whether
the passed program halts or not. The fact that you can write a
function that doesn't return the result to the caller is of no
relevance whatsoever. The rest follows directly from there.

You can do this, and my original unmodified halt analyzer can determine
that this function would halt, even though it could not make this determination
itself. My uncorrupted halt analyzer still works for all inputs.
If you can't see it, it's really not worth discussing further; if your
logic is that far off track then I'd just be banging my head against a
brick wall.

Tom

[David Hilsee]

"Dave Vandervies" <dj******@csclu b.uwaterloo.ca> wrote in message
news:cd******** **@rumours.uwat erloo.ca...

In article <u-*************** *****@comcast.c om>,
David Hilsee <da************ *@yahoo.com> wrote:

"Peter Olcott" <ol****@worldne t.att.net> wrote in message
news:Ly******* *************@b gtnsc04-news.ops.worldn et.att.net...

Providing one specific instance where the method can be made to fail
does not at all refute that the method works correctly in general.

The challenge is not to produce a program that works correctly in general.The phrase "in general" really means "some of the time,"

No.

A "general solution" to a problem is a solution that works *all* *the*
*time*. Artificially restricting the set of problems you might be able
to solve means you're only solving it for a set of special cases; this
is rarely interesting.

This is the second time in the past few days that someone has taken
something that I said using common parlance as something completely
different. I must be really good at confusing people.

The meaning I was using is the common, everyday meaning. Example usage: "In
general, I like cake, but I don't like carrot cake." In that case, it
should be taken to mean "usually" or "generally. " If one were trying to say
that a solution was a general solution, they should probably avoid using the
phrase "in general" because that can mean something completely different. I
assumed that Peter meant "usually" because otherwise the statement that he
made wouldn't make sense. Also, he wasn't using a whole lot of "mathese,"
or at least nothing on the level of "general solution," so I had no reason
to suspect that he meant something other than "usually." I'm pretty sure
that he was not restricting the set of problems because he had already said
that he is considering the entire set of all possible programs as input.

--
David Hilsee

[Peter Olcott]

> A "general solution" to a problem is a solution that works *all* *the*

*time*. Artificially restricting the set of problems you might be able
to solve means you're only solving it for a set of special cases; this
is rarely interesting.

and it's easy to
produce a program that sometimes works. The challenge is to produce a
program that works on all input programs. That is, it always works, no
matter what.

My solution works on all inputs. It even determines that the original
halting problem will halt. It does not work under all conditions. It
does not work:
(1) If you destroy the computer.
(2) Turn the computer off
(3) Unplug the computer
(4) Erase the software
(5) Modify the executable adding bugs.

Since it does work on ALL INPUTS it is a general solution
to the Halting Problem.
Yes. This is what's referred to in mathese as a "general solution".
dave

--
Dave Vandervies dj******@csclub .uwaterloo.ca
[This] is otherwise known as 'learning by experience'. I don't often
come across people who publicly state they're not interested in that.
--Arthur van der Harg in the scary devil monastery

[Peter Olcott]

> > Since it is possible to write X that does not return a value to its

caller, then its possible to prevent the basis for proving that
solving the Halting Problem is impossible to exist.
That doesn't follow. If it's possible to write a function that
calculates X, how can it be impossible to modify it so that it returns
X? Can you supply an example of such a function?

The function that does not return a value does correctly determine
halting for all inputs, including the function that does return this value.
There is no possible case where the original Halting Problem can
arise with the corrected function. You can make it not work by
adding bugs to its code. You can also make it not work by
destroying the computer that it is running on. Neither of these
refute the fact that it solves the Halting Problem. The only thing
that would refute that it solves the Halting Problem would be to
find any program that it can not correctly determine halting for.
Since it can correctly determine halting for the original Halting
Problem, the original Halting Problem is completely refuted.

In all thoses instances where you do not return the result to the
caller, you have solved the Halting Problem.

No I haven't. Disproving the validity of a proof is very different from
disproving the original theorem. The people who found fault in the many

A single valid counter-example is all that is required. I provided that.
attempted proofs of Fermat's Last Theorem didn't succeed in discovering
that Fermat's Last Theorem is actually false.

The statement "it is possible to write X that does not return a value to
its caller" depends on the statement "it is possible to write X". I.e.
we need to come up with the algorithm itself, before we can write it to
either return its result or not return its result.
This is not true. This is not required. I did not prove that a program
that can determine whether or not any arbitrary program halts must
exist. All that I did was show that the original proof was in error in
concluding that it can't exist.
Stewart.

--
My e-mail is valid but not my primary mailbox, aside from its being the
unfortunate victim of intensive mail-bombing at the moment. Please keep
replies on the 'group where everyone may benefit.

[David Hilsee]

"Peter Olcott" <ol****@worldne t.att.net> wrote in message
news:yn******** *************@b gtnsc04-news.ops.worldn et.att.net...

You already said that it does not work for a specific instance, so it

does
It works for all inputs. It does not work in all instances such as destroying the machine that is is running on.

I think I get what you're saying now. That paragraph (which has now changed
to provide better wording) claiming that one can make a LoopIfHalts that
fails is not about creating new input source, it is about modifying (on the
page, it is referred to as "corrupting ") the example so it no longer works.
Originally, it sounded like the claim was that a modified version of the
source you provided is somehow invalid input and can be ignored.

For example, I thought you were saying that the following program "doesn't
count."

// Some source taken from http://www.cgl.uwaterloo.ca/~csk/halt/

int WillHaltWithRet urnValue(string SourceCode, string InputData) {
if (TheProgramWill Halt(SourceCode , InputData))
return TRUE;
else if (TheProgramWill NotHalt(SourceC ode, InputData))
return FALSE;
else
return UNKNOWN;
}

bool stops_on_self( char * program ) {
return WillHaltWithRet urnValue( program, program ) == TRUE;
}

bool bobs_yer_uncle( char * program ) {
if( stops_on_self( program ) ) {
while( 1 ) {}
return false;
} else {
return false;
}
}

Now you can apply the same reasoning from the link I provided to show that
your program does not work for this case, because the new
WillHaltWithRet urnValue function does the same exact thing that your
WillHalt() does except it returns the conclusion. If
WillHaltWithRet urnValue() can be proven to not work (and it can, as shown in
the link I provided), then that means that WillHalt() does not work because
the modifications made do not affect the conclusion that the function
reaches. This code was partially inspired by tom_usenet's comment that
"*If* a solution to the halting problem exists, *then* it *must* be possible
to write WillHalt such that it returns to a caller whether the passed
program halts or not." Throughout the discussion, I thought you had already
considered the above source as an input, but for some reason you were
refusing to accept it as valid. Tom's comment triggered a thought that this
might not be the case, so I decided to explain his statement in more detail.

--
David Hilsee