Solution to the halting Problem?

[Karl Heinz Buchegger]

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.

 

[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:


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-jj=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.bet/jvxv/Unygvat_ceboyrz>

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

 

[Dave Vandervies]

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

 

[Peter Olcott]

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.

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.


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.

 

[Peter Olcott]

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.

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]

*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.

 

[David Hilsee]

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.

 

[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.

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 (e-mail address removed)
[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

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.

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.

 

[David Hilsee]

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 WillHaltWithReturnValue(string SourceCode, string InputData) {
if (TheProgramWillHalt(SourceCode, InputData))
return TRUE;
else if (TheProgramWillNotHalt(SourceCode, InputData))
return FALSE;
else
return UNKNOWN;
}

bool stops_on_self( char * program ) {
return WillHaltWithReturnValue( 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
WillHaltWithReturnValue function does the same exact thing that your
WillHalt() does except it returns the conclusion. If
WillHaltWithReturnValue() 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.

 

[Peter Olcott]

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.

All syntactically correct programs are valid input.
In theory I could also include syntactically incorrect
programs, and then output compiler error messages.

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 WillHaltWithReturnValue(string SourceCode, string InputData) {
if (TheProgramWillHalt(SourceCode, InputData))
return TRUE;
else if (TheProgramWillNotHalt(SourceCode, InputData))
return FALSE;
else
return UNKNOWN;
}

bool stops_on_self( char * program ) {
return WillHaltWithReturnValue( 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
WillHaltWithReturnValue function does the same exact thing that your
WillHalt() does except it returns the conclusion. If

Nope. Its not like that. My void WillHalt() does determine that the
above sequence of programs will halt. The corrupted version can't
determine whether or not the above sequence will halt, but my
version can always make this determination correctly.

My void WillHalt() is not locked into the double-bind as the
corrupted version is. My version can determine that the corrupted
version will halt, and not have this used to negate the result.

WillHaltWithReturnValue() 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

This is the tricky part. It actually does modify the conclusion that it
reaches. If everything else is the same, except in one case you return
the result to the caller, and in the other case you do not return the result
to the caller, the result differs. The reason that the result differs is that
in one case the result is fed back to the program that you are analyzing,
and in the other case this result is not fed back. This changes the way that
the analyzed program behaves, thus chaning the result of your analysis.

"*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."

No sorry that is merely a false statement.

 

[David Hilsee]

This is the tricky part. It actually does modify the conclusion that it
reaches. If everything else is the same, except in one case you return
the result to the caller, and in the other case you do not return the result
to the caller, the result differs. The reason that the result differs is that
in one case the result is fed back to the program that you are analyzing,
and in the other case this result is not fed back. This changes the way that
the analyzed program behaves, thus chaning the result of your analysis.

I didn't think that I was going to have to post something else to further my
explanation, but I guess I was wrong.

You cannot argue that the result is different. While it is true that the
code is different and the characters written to the screen are different,
the ANSWER (AKA conclusion) is the same for every input. That is, for every
input that WillHalt() displays "The Program Will Halt",
WillHaltWithReturnValue() will return TRUE, and for every input that
WillHalt() displays "The Program Will Not Halt", WillHaltWithReturnValue()
will return FALSE, and for every input that WillHalt() displays "Security
Has Been Breached, Take Corrective Action", WillHaltWithReturnValue() will
return UNKNOWN. If you're trying to say that there is a case where
WillHaltWithReturnValue() and WillHalt() can come to a different conclusion
when passed the same source, then you're either grasping at straws or just
plain wrong. The only way that could be possible is if SecureOutput() does
something that changes the conclusion, and in that case, I would just make
the code that changes the conclusion a part of WillHaltWithReturnValue() so
the return values still match the screen output.

Therefore, since WillHalt() reaches the same conclusion
WillHaltWithReturnValue() does for every input source, and
WillHaltWithReturnValue() can be shown to not work for the input I gave, it
follows that WillHalt() also will not work for the input I gave. In the
original halting problem, WillHalt() failed because its return value could
be shown to contradict itself. In this case, to avoid that contradiction,
the value of WillHaltWithReturnValue() must not match the output that
WillHalt() wrote to the screen, and that is impossible.

 

[Dave Vandervies]

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.[/QUOTE]

You demonstrated the existence of a program and input for which it's
possible to determine that it can halt. You have not proven anything
about any other program or input, or about "programs and input"
in general.

Please apply your solution to the halting program to this program and tell
us whether it halts on the input "1". Assume a correctly implemented
bignum library and the generally accepted mathematical definition of
"perfect number".
--------
#include "bignum.h"

int main()
{
bignum b=read_bignum_from_input();
while(true)
{
if(is_bignum_a_perfect_number(b))
return 0;
b+=BIGNUM_TWO;
}
/*not reached*/
}
--------
If you are not able to do this, you haven't solved the halting problem.
Solutions that only apply to some special case are Not Interesting.


Are you really so thick that you're Not Getting This, or are you just
trolling?


dave

 

[Peter Olcott]

If you are not able to do this, you haven't solved the halting problem.

Solutions that only apply to some special case are Not Interesting.

If you want to be completely precise, then I have not actually
solved the Halting Problem, yet have proven that the original
proof that a solution is impossible, is incorrect.

 

[Peter Olcott]

You cannot argue that the result is different. While it is true that the

code is different and the characters written to the screen are different,
the ANSWER (AKA conclusion) is the same for every input. That is, for every
input that WillHalt() displays "The Program Will Halt",
WillHaltWithReturnValue() will return TRUE, and for every input that
WillHalt() displays "The Program Will Not Halt", WillHaltWithReturnValue()
will return FALSE,

No that is simply not the case.
http://home.att.net/~olcott/halting/example.html
If you walk through an execution trace of the above int WillHalt(LoopIfHalts, LoopIfHalts)
the result is that WillHalt() returns UNKNOWN, thus LoopIfHalt() halts. It returns
UNKNOWN specifically because bool WillHalt() knows that it can't say that LoopIfHalt()
halts, because this makes it not halt. Therefore you fall through to the other conditions.

If you walk through the same execution trace with void WillHalt() you get a
completely different result. You get this different result specifically because
void WillHalt() does not feed its result back to its caller, thus modifying
the behavior of its caller. Since the caller is also the program being analyzed,
then different behavior by the caller entails a different result from the analysis.

 

[David Hilsee]

No that is simply not the case.
http://home.att.net/~olcott/halting/example.html
If you walk through an execution trace of the above int

WillHalt(LoopIfHalts, LoopIfHalts)

the result is that WillHalt() returns UNKNOWN, thus LoopIfHalt() halts. It returns
UNKNOWN specifically because bool WillHalt() knows that it can't say that LoopIfHalt()
halts, because this makes it not halt. Therefore you fall through to the other conditions.

If you walk through the same execution trace with void WillHalt() you get a
completely different result. You get this different result specifically because
void WillHalt() does not feed its result back to its caller, thus modifying
the behavior of its caller. Since the caller is also the program being analyzed,
then different behavior by the caller entails a different result from the

analysis.

Are we talking about the same two functions? Here they are again:

int WillHaltWithReturnValue(string SourceCode, string InputData) {
if (TheProgramWillHalt(SourceCode, InputData))
return TRUE;
else if (TheProgramWillNotHalt(SourceCode, InputData))
return FALSE;
else
return UNKNOWN;
}

void WillHalt(string SourceCode, string InputData)
{
if (TheProgramWillHalt(SourceCode, InputData))
SecureOutput("The Program Will Halt");

else if (TheProgramWillNotHalt(SourceCode, InputData))
SecureOutput("The Program Will Not Halt");

else
SecureOutput("Security Has Been Breached, Take Corrective Action");
}

I am arguing that if both SourceCode parameters are equal to each other and
both InputData parameters are equal to each other, then there is a
one-to-one mapping (in both directions) between TRUE, FALSE, UNKNOWN and
"The Program Will Halt", "The Program Will Not Halt", and "Security Has Been
Breached, Take Corrective Action", respectively. My previous post shows
that if you accept that this is true, then that means that WillHalt() is
using the same exact logic as WillHaltWithReturnValue(), so you must accept
that WillHalt() does not work because WillHaltWithReturnValue() has already
been shown to be wrong. In short, the logic of the functions are unaffected
by the presence of output statements, so, if one's logic is unacceptable,
the other's logic is unacceptable, period.

If you can prove that WillHaltWithReturnValue()'s return codes do not have a
one-to-one mapping (in both directions) to WillHalt()'s output statements,
then please do it. Do not tell me to walk through the execution trace
myself and discover what happens, because I have walked through all of the
possible execution traces and have determined that there is no difference in
the results. Using only the above source, start with a pair of strings as
input parameters, walk through both functions' execution traces using
whatever notation for branches that you wish you use, and prove that there
could be a case where the statement written to the screen does not match the
corresponding return value as I described. If you can do that, then you
have shown that WillHalt() could work where WillHaltWithReturnValue() did
not, and therefore you will have proven that there is a potential solution
to the halting problem. If you cannot do that, then the halting problem
remains as it was before you came up with this "solution."

I'm getting the impression that you don't understand what I'm trying to say,
so the above was an attempt to cut out all of the extraneous talk and focus
on the exact conundrum that must be dealt with. If you refuse to respond
with the example exactly as I requested and instead resort to asserting that
something is different between the two, I will assume that you are trying to
irritate me and I will not respond, except possibly with a short, caustic
(possibly insulting, depending on my mood) message explaining how you did
not satisfy my request. I'm sorry to seem rude, but I have explained
everything in the best way I can, and this discussion is trying my patience.
Looking back, I find it amazing that I have not cursed like a sailor in one
of my posts.

 

[tom_usenet]

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.

This is infuriating, so this will be my last post on this subject.

a) You haven't proved that your "halt analyzer" works for all inputs,
only that the contradiction for the bool returning one doesn't apply.
b) The bool returning WillHalt function *cannot exist* - it is a
logical contradiction. So how can your function determine that it
would halt?

Go and read up on logic and the concept of proof, and stop being such
a fool.

Tom

 

[tom_usenet]

On Thu, 22 Jul 2004 23:08:34 -0400, "David Hilsee"

I suggest you stop here; Olcott is a classic usenet crackpot who
doesn't understand logic. See:

http://www.google.co.uk/groups?safe..._usubject=FastString&as_uauthors=Peter Olcott

Tom

 

[Karl Heinz Buchegger]

If you want to be completely precise, then I have not actually
solved the Halting Problem, yet have proven that the original
proof that a solution is impossible, is incorrect.

You did this by modifying the original proof. Your intention
is clear: You modified the original proof in such a way that
the whole idea of the proof is no longer possible. So what you
showed is: With a modification, the proof is no longer applyable.
Not really an interesting result.

 

[Karl Heinz Buchegger]

On Thu, 22 Jul 2004 23:08:34 -0400, "David Hilsee"

I suggest you stop here; Olcott is a classic usenet crackpot who
doesn't understand logic.

I remember of another 'proof' from him. The proof went along:
Execute the algorithm in question and wait. If the algorithm terminates
in x seconds then it obviously halted. If not, the algorithm will never
halt.