Solution to the halting Problem?

[Peter Olcott]

If it does not return a value to the calling function, then in what sense
can it be said to be determining whether Program(input) will halt?

There are a multitude of other ways that the function could provide results.
Returning the result to the calling function is not at all the only possible way.
It is the only way that the Halting Problem is created, thus if this one way
is eliminated, then the Halting Problem ceases to be a problem.

 

[Peter Olcott]

Peter Olcott wrote:



I'm still waiting to see your example of a function that can't possibly
be modified to return its result.

Stewart.

I can't see why everyone continues to bring up this same point.
It is not any form a valid refutation. It is exactly and precisely
like saying that since it is possible to smash a computer with a
sledge hammer, therefore no computer can be said to ever run
any programs. If you don't see that this is exactly the same reasoning
then please provide the precise point where the analogy fails to
coincide, and why it fails to coincide.

As soon as you begin providing the results to the calling function,
you have added an error to the original program.

 

[Peter Olcott]

It doesn't matter what you buy or what you don't buy.
After all the proof doesn't even need to run on a computer.
Forget the physical implementation on a computer, it is not
important in algorithm theory (and BTW cannot be done). The proof
works in a thinking model without the need for actual hardware
like video screens or memory.

These details are crucial, and if abstracted away cease to correspond
to the actual reality of the posed problem. For example: a separate
memory space could be the mechanism by which the results are kept
from the program being analyzed. At the higher level of abstraction
of pure mathematics, things such as separate memory spaces are
considered to be irrelevant. If they change the outcome of the analysis,
then it is an error to consider them irrelevant.

 

[David Hilsee]

I can't see why everyone continues to bring up this same point.
It is not any form a valid refutation. It is exactly and precisely
like saying that since it is possible to smash a computer with a
sledge hammer, therefore no computer can be said to ever run
any programs. If you don't see that this is exactly the same reasoning
then please provide the precise point where the analogy fails to
coincide, and why it fails to coincide.

As soon as you begin providing the results to the calling function,
you have added an error to the original program.

Everyone keeps bring up that point because your last assertion is bollocks.
To produce the contradictory input source, one can take the logic from the
source code of the analyzer and use it to construct input that will cause it
to contradict its own logic. You have supposedly taken the ability to
construct that source away by making trivial modifications to the analyzer
and claiming that removing them causes the contradiction to not hold, as if
it were necessary for the input to contain a verbatim copy of the analyzer's
source code to show the contradiction.

In other words, nobody in their right mind would claim that the transition
from

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 // This code never gets executed if the solution is properly
implemented
SecureOutput("Security Has Been Breached, Take Corrective Action");
}

to

int WillHalt(string SourceCode, string InputData)
{
if (TheProgramWillHalt(SourceCode, InputData)) {
SecureOutput("The Program Will Halt");
return TRUE;
}

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

else { // This code never gets executed if the solution is properly
implemented
SecureOutput("Security Has Been Breached, Take Corrective Action");
return UNKNOWN;
}
}

somehow adds an error into the analyzer that causes the return values to not
correlate with the output statements from the previous version.

Your sledgehammer analogy is flawed because the modification does not cause
your analyzer to malfunction.

BTW, the answer to (3) on halting-problem.com makes little sense to me.
Perhaps supplying an introduction and using two different names for the
bool-returning and void-returning method would be better.

 

[Karl Heinz Buchegger]

There are a multitude of other ways that the function could provide results.
Returning the result to the calling function is not at all the only possible way.
It is the only way that the Halting Problem is created, thus if this one way
is eliminated, then the Halting Problem ceases to be a problem.

You constantly mix up the Halting Problem theorem with its proof.

The proof is where the loop construction takes place. So even if you
are right, then it would be this specific proof that vanishes into
air. But this does not mean that the theorem itself vanishes.

BTW: You are wrong. At the moment the function produces a result
there are ways to feed those results back to the caller. You can't
close that door unless you output no result at all.

 

[Karl Heinz Buchegger]

I can't see why everyone continues to bring up this same point.
It is not any form a valid refutation. It is exactly and precisely
like saying that since it is possible to smash a computer with a
sledge hammer, therefore no computer can be said to ever run
any programs.

Not at all.
The exact equivalent is:

Claim: All computers will run all programs
Disproov: It is possible to smash a computer with a hammer, thus
not all computers can run all programs. At least smashed
computers won't do that.

 

[Karl Heinz Buchegger]

These details are crucial,

Only in your dreams.
In which way is Euclid's proof dependent on the type of paper
I write it on?
Same here.

 

[Peter Olcott]

You constantly mix up the Halting Problem theorem with its proof.

The proof is where the loop construction takes place. So even if you
are right, then it would be this specific proof that vanishes into
air. But this does not mean that the theorem itself vanishes.

When the Proof of the Halting Problem fails to prove that the Halting Problem
is a problem, then it ceases to be a problem.

BTW: You are wrong. At the moment the function produces a result
there are ways to feed those results back to the caller. You can't
close that door unless you output no result at all.

Feeding the results back to the caller does not show that no correct
halt function can possibly be created. It only shows that one of the
ways to attempt to solve the problem does not always work.
Because it is possible to change a program to cause it to cease
to function correctly, in no way shows that the unmodified program
does not work correctly in every case.

 

[Peter Olcott]

Not at all.
The exact equivalent is:

Claim: All computers will run all programs
Disproov: It is possible to smash a computer with a hammer, thus
not all computers can run all programs. At least smashed
computers won't do that.

But the claim that the Halt function will work under all possible conditions
(including smashing its computer) is not the relevant claim. The relevant
claims is simply will the halt function work for every possible input? If it
fails this claim then the Halting Problem continues to exist. If it passes this
claim, then the Halting Problem ceases to exist. It does pass this claim.

 

[Peter Olcott]

Only in your dreams.
In which way is Euclid's proof dependent on the type of paper
I write it on?
Same here.

Purely mathematical proofs can fail to prove their claims specifically
because these purely mathematical proofs abstract away (remove)
details that change the outcome.

 

[Karl Heinz Buchegger]

When the Proof of the Halting Problem fails to prove that the Halting Problem
is a problem, then it ceases to be a problem.

You are not an expert in logic, are you?
Read again what you wrote. In the meantime you got so blind that you
don't even see the simplest logic failures in your argumentation.

 

[Karl Heinz Buchegger]

Purely mathematical proofs can fail to prove their claims specifically
because these purely mathematical proofs abstract away (remove)
details that change the outcome.

Example?

 

[Peter Olcott]

Everyone keeps bring up that point because your last assertion is bollocks.
To produce the contradictory input source, one can take the logic from the
source code of the analyzer and use it to construct input that will cause it
to contradict its own logic.

First of all it will not contradict its own logic, it will merely fail to return a result
that would otherwise cause a contradiction. Secondly it only does this specifically
because an error has been added to its code. If this error is not added, then
it functions correctly. There is nothing to prevent it from functioning correctly
besides the error. If will even function correctly using the program with the error
as input, thus it still works for all possible inputs. Working correctly for all possible
inputs, is what is required to refute the Halting Problem, nothing more, and nothing
less.

You have supposedly taken the ability to
construct that source away by making trivial modifications to the analyzer
and claiming that removing them causes the contradiction to not hold, as if
it were necessary for the input to contain a verbatim copy of the analyzer's
source code to show the contradiction.

This method still works even if the hardware specific devices are not
used. It still works even within the context of the original proof on
an unmodified Turing Machine. In this case the Halt function merely
refrains from returning any result to the function that uses this result
to change its behavior, and thus change the result of the analysis. It
returns its result in every other instance, even if applied to the program
that uses its result to change its behavior. Two different invocations
derive two different results.

Since it gets to see all of the relevant source code, it can easily distinguish
between the return of a value to the program being analyzed, that changes
its behavior based on this return value, and all other invocations. Because
there is a difference that it can see, it can provide different results based on
this difference. Because it can see the difference, the Halting Problem
ceases to be a problem.

 

[Karl Heinz Buchegger]

But the claim that the Halt function will work under all possible conditions
(including smashing its computer) is not the relevant claim. The relevant
claims is simply will the halt function work for every possible input? If it
fails this claim then the Halting Problem continues to exist. If it passes this
claim, then the Halting Problem ceases to exist. It does pass this claim.

It does not! For the simple reason that the Halting problem will not simply
'cease to exist'. The Halting Problem is a question and as such has 2 possible
answers: Yes or no.

The Halting problem is the question: Is there an algorithm which can correctly
and in a deterministic way determine if all algorithms ever come to an halt.

That is the question. There are 2 possible outcomes:
* yes
* no
Since the first one seems to be the answer which is harder to proof, Turing
showed that the second answer is the correct one. The proof is to construct
an algorithm (and the clever part is to use the testing function as part of it)
where this testing function is bound to fail. Thus the answer to the Halting
Problem is: No, there is no such algorithm. Even if we assume that there is
one, it turns out that it is possible to cleverly construct an algorithm which
cannot be correctly analyzed by this assumed algorithm.

You constantly mix up the claim with the proof. The function assumption
of WillHalt() and the construction of LoopIfHalts() is *not* the claim.
They are part of the proof!
Even if you modify the proof in such a way that you circumvent the way this
proof works, it does not mean, that the original proof is no longer valid.
It is still there and serves as a perfect example of why the answer to the
Halting problem is still: 'No, there is no such algorithm'.

 

[Peter Olcott]

Peter Olcott wrote:

The Halting Problem is directly derived from its proof.
If the proof is shown to be in error, then the Halting Problem
(which is only derived from the proof) ceases to exist.

 

[Peter Olcott]

Peter Olcott wrote:

Example?

If the solution to a problem requires a separate memory space,
and the mathematical proof disregards a separate memory space
as irrelevant, then the math proof errs.

 

[Peter Olcott]

Peter Olcott wrote:

It does not! For the simple reason that the Halting problem will not simply
'cease to exist'. The Halting Problem is a question and as such has 2 possible
answers: Yes or no.

Nope. The Halting Problem is the problem of not being able to correctly determine
if every program halts. As soon as a method is determined to circumvent the
particular restriction, then the Halting Problem is not a problem. A problem that is
not a problem is a problem no more.

The Halting problem is the question: Is there an algorithm which can correctly
and in a deterministic way determine if all algorithms ever come to an halt.

That is not what has been historically referred to as the Halting Problem.
THE Halting Problem is a much more specific case. It is the case of
specifically showing why this is "impossible".

That is the question. There are 2 possible outcomes:
* yes
* no
Since the first one seems to be the answer which is harder to proof, Turing
showed that the second answer is the correct one. The proof is to construct
an algorithm (and the clever part is to use the testing function as part of it)
where this testing function is bound to fail. Thus the answer to the Halting
Problem is: No, there is no such algorithm. Even if we assume that there is
one, it turns out that it is possible to cleverly construct an algorithm which
cannot be correctly analyzed by this assumed algorithm.

Except that I have just now (in another newsgroup) shown that this is not true.
The Halt analyzer can correctly determine whether or not this cleverly
constructed algorithm halts. Also with my latest method, it can do this
directly within the basic capabilities of a typical Turing Machine. It needs
no special hardware. Since the whole Halting Problem depends on this
proof providing this clever algorithm, and the halt analyzer failing
to correctly process this algorithm, therefore I only need to show how
it can be correctly processed, for the proof, and therefore the Halting Problem
itself, to evaporate. I did this.

You constantly mix up the claim with the proof. The function assumption
of WillHalt() and the construction of LoopIfHalts() is *not* the claim.
They are part of the proof!
Even if you modify the proof in such a way that you circumvent the way this

I don't need to modify the proof, I merely show that it is in error.

 

[David Hilsee]

First of all it will not contradict its own logic, it will merely fail to return a result
that would otherwise cause a contradiction.

Yes, it will contradict its own logic. I don't even know what you mean by
"fail to return a result". If you're talking about returning that UNKNOWN
value/displaying "security problem", then forget it, because that is not an
acceptable answer from the analyzer because it means that the analyzer has
failed to process the input correctly. If you do not see how the analyzer
can be forced to contradict its own logic, then you do not understand the
proof. I have posted a URL (http://www.cgl.uwaterloo.ca/~csk/halt/) that
explains the problem very well, so please read that page as many times as is
necessary for you to understand why it can contradict itself.

The contradiction is very simple:

If the analyzer says the "trick" input program will halt, then, because of
the stolen, embedded logic, that conclusion will imply that it would have
said the program will not halt.

If the analyzer says the "trick" input program will not halt, then, because
of the stolen, embedded logic, that conclusion will imply that it would have
said the program will halt.

The analyzer cannot reach a conclusion that avoids an obvious contradiction.
To be considered a solution, the analyzer is required to determine if any
input halts or does not halt. Therefore, it is not a solution to the halting
problem.

You cannot address this "trick" program by embedding output statements or
making absurd statements about potential errors introduced by return codes.
Also, you cannot address this "trick" program by claiming that the analyzer
will detect if it is analyzing a modified copy of itself and change its
answer accordingly, because that same "answer changing" logic will be
embedded inside the input, which will cause the contradiction once again.

 

[Karl Heinz Buchegger]

Good luck in your attempt to make a complete fool
of yourself.
I did a quick glance into comp.theory and saw that
you have a really hard time there. Compared to that
group, comp.lang.c++ is a piece of cake.


Karl Heinz Buchegger
(e-mail address removed)

 

[Karl Heinz Buchegger]

Nope. The Halting Problem is the problem of not being able to correctly determine
if every program halts. As soon as a method is determined to circumvent the
particular restriction, then the Halting Problem is not a problem. A problem that is
not a problem is a problem no more.

You might want to first educate yourself what you are talking about. That is:
What is the question, commonly referred to as the 'Halting Problem', before
continuing to spread nonsense.