Solution to the halting Problem?

[tom_usenet]

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.

No, you fool, it would become an unsolved problem, it wouldn't "cease
to exist". But it is a solved problem - it is impossible to write a
halt analyser.

Tom

 

[Peter Olcott]

No, you fool, it would become an unsolved problem, it wouldn't "cease
to exist". But it is a solved problem - it is impossible to write a
halt analyser.

Tom

And you make this statement after careful consideration of my
position (which is not even posted on the newsgroup) ?
Assumptions are no form of correct reasoning.

 

[Peter Olcott]

Peter Olcott wrote:

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.

Well my textbook seems to agree with you. This doesn't effect what I
am saying very much. I have disproved the proof of the Halting Problem,
then. It is a relatively minor semantical distinction.

 

[Peter Olcott]

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

Yes you would be correct here. I have completely redesigned my method
and eliminated that path. What I am talking about here is that the Halting
analyzer can see when its result is being used to change the behavior of the
program being analyzed, thus changing the analysis. In those cases where
it detects this, it provides its own differing behavior to correspond to this.
It refrains from returning a result in those cases where this result is used
to change the behavior of the program being analyzed. Since is still does
return the correct value in every other case, it can still determine this correct
value for this program.

01) int WillHalt(string SourceCode, string DataInput)
02) {
03) if (TheProgramHalts(SourceCode, DataInput))
04) return 1; // also means true in C/C++
05) else
06) return 0; // also means false in C/C++
07) }

08) void LoopIfHalts(string SourceCode, string DataInput)
09) {
10) if (WillHalt(SourceCode, DataInput))
11) while(true)
12) ;
13) else
14) return;
15) }

16) cout << WillHalt(LoopIfHalts, LoopIfHalts);

Line 16 returns the correct result for LoopIfHalts, whereas line 10
returns no result at all.

 

[David Hilsee]

analyzer

Yes you would be correct here. I have completely redesigned my method
and eliminated that path. What I am talking about here is that the Halting
analyzer can see when its result is being used to change the behavior of the
program being analyzed, thus changing the analysis. In those cases where
it detects this, it provides its own differing behavior to correspond to this.
It refrains from returning a result in those cases where this result is used
to change the behavior of the program being analyzed. Since is still does
return the correct value in every other case, it can still determine this correct
value for this program.

01) int WillHalt(string SourceCode, string DataInput)
02) {
03) if (TheProgramHalts(SourceCode, DataInput))
04) return 1; // also means true in C/C++
05) else
06) return 0; // also means false in C/C++
07) }

08) void LoopIfHalts(string SourceCode, string DataInput)
09) {
10) if (WillHalt(SourceCode, DataInput))
11) while(true)
12) ;
13) else
14) return;
15) }

16) cout << WillHalt(LoopIfHalts, LoopIfHalts);

Line 16 returns the correct result for LoopIfHalts, whereas line 10
returns no result at all.

At line 10, WillHalt() returns no result at all? What on earth does that
mean? How does it perform this magic? Also, how does not returning a
result avoid an admission of failure? If calling WillHalt(SourceCode,
DataInput) will not yield the correct answer, the program is not a solution
to the halting problem, because it is required to return the correct answer
for all inputs.
again.

Please keep the above in mind.

 

[Karl Heinz Buchegger]

Well my textbook seems to agree with you.

After all ...

This doesn't effect what I
am saying very much.

It affects it in every possible way

I have disproved the proof of the Halting Problem,
then.

You have not.
You presented something else. Remember: one keypoint in your
'proof' was the inability of returning a value. Thus you have
modified the original proof. For showing that a proof is incorrect,
you are not allowed to modify the proof. The only thing you can do,
is to show that in some of the steps to come up with that proof there
is a logical flaw. But that's all. At the moment you modify the
original proof, you are no longer disproving it.

It is a relatively minor semantical distinction.

It is all the difference between: There is a Halt Analazer and
there is none. I wouldn't call that 'minor'.

 

[Peter Olcott]

Peter Olcott wrote:

You have not.
You presented something else. Remember: one keypoint in your
'proof' was the inability of returning a value. Thus you have
modified the original proof. For showing that a proof is incorrect,
you are not allowed to modify the proof. The only thing you can do,

All I have to do is to take the original problem and show that the conclusion
based on the proof, that this problem can not possibly be solved is incorrect.
To show that this problem can be solved, I merely have to derive one way
to solve it. I did that.

 

[Peter Olcott]

At line 10, WillHalt() returns no result at all? What on earth does that
mean? How does it perform this magic? Also, how does not returning a

Its not magic at all. It merely can't be accomplished on current C++
compilers. The current compilers require you to either return a value
or refrain from returning a value all the time. If they were modified
such that you could return a value or not, then the semantics of the
program would still be coherent. The meaning of testing a return value
would always provide an untrue result. Thus if WillHalt was tested,
it would not test as true. What actually might more sense would be
to have a Boolean with three values: True, False, and Neither.

 

[Karl Heinz Buchegger]

All I have to do is to take the original problem and show that the conclusion
based on the proof, that this problem can not possibly be solved is incorrect.
To show that this problem can be solved, I merely have to derive one way
to solve it. I did that.

You did not.
You assumed that it can be solved (that a WillHalt() can exist) and
then used that WillHalt in some other function and claimed some
magic to circumvent the problem of applying this function on itself.
From this you conclude that the assumed WillHalt() function can exist.
But you are still left with an assumed WillHalt() function not a real
one. Up to know you have not shown anything of importance.

 

[tom_usenet]

Its not magic at all. It merely can't be accomplished on current C++
compilers. The current compilers require you to either return a value
or refrain from returning a value all the time. If they were modified
such that you could return a value or not, then the semantics of the
program would still be coherent. The meaning of testing a return value
would always provide an untrue result. Thus if WillHalt was tested,
it would not test as true. What actually might more sense would be
to have a Boolean with three values: True, False, and Neither.

What is a TM that neither halts nor doesn't halt?

Tom

 

[Karl Heinz Buchegger]

All I have to do is to take the original problem and show that the conclusion
based on the proof, that this problem can not possibly be solved is incorrect.
To show that this problem can be solved, I merely have to derive one way
to solve it. I did that.

You: All odd numbers are prime.
We: That's not true, 15 is odd, but it is not prime
You: That doesn't matter, 5 is also odd and is prime, thus
I have shown one example, thus my claim is true.

 

[Karl Heinz Buchegger]

You: All odd numbers are prime.
We: That's not true, 15 is odd, but it is not prime
You: That doesn't matter, 5 is also odd and is prime, thus
I have shown one example, thus my claim is true.

I take that back.
The analogy doesn't hold.
One that holds is:

Turing: There is an interesting question: Are all odd numbers prime?
We: No. Because there is 15. 15 is odd but is not prime, because of 5*3 = 15
You: 5 is odd and is prime. Thus all odd numbers are prime.

 

[Peter Olcott]

You did not.
You assumed that it can be solved (that a WillHalt() can exist) and
then used that WillHalt in some other function and claimed some
magic to circumvent the problem of applying this function on itself.

Its not at all magic. It is nothing that is not obvious to the above
average programmer, at least once it is pointed out. It is clear
that one invocation differs from that other. It doesn't even take
a genius to see this. All the Halt Analyzer does is take advantage
of this clear difference.

From this you conclude that the assumed WillHalt() function can exist.
But you are still left with an assumed WillHalt() function not a real
one. Up to know you have not shown anything of importance.

Except that the fundamental basis for the proof that solving the
Halting Problem is incorrect.

 

[Peter Olcott]

What is a TM that neither halts nor doesn't halt?

Tom

That is what apparently tricked everyone for all these years.
There is no TM that neither halts nor doesn't halt. There is a TM
that does not halt if a halt analyzer determines that it does, and
does halt if a halt analyzer determines that it doesn't. To solve
this problem, merely refrain from speaking with the deceitful TM.
If the only time that the Halt Analyzer refrains from returning
a value is when this value is used to change the behavior, and thus
change the analysis of the TM being analyzed, then even this TM
can be correctly analyzed.

 

[Peter Olcott]

You: All odd numbers are prime.
We: That's not true, 15 is odd, but it is not prime
You: That doesn't matter, 5 is also odd and is prime, thus
I have shown one example, thus my claim is true.

I have shown that the one single example that "proves" the Halting
Problem can not possibly be solved, is not an example that the
Halting Problem can not be solved. This is not at all analogous to
what you claimed.

 

[David Hilsee]

That is what apparently tricked everyone for all these years.
There is no TM that neither halts nor doesn't halt. There is a TM
that does not halt if a halt analyzer determines that it does, and
does halt if a halt analyzer determines that it doesn't. To solve
this problem, merely refrain from speaking with the deceitful TM.
If the only time that the Halt Analyzer refrains from returning
a value is when this value is used to change the behavior, and thus
change the analysis of the TM being analyzed, then even this TM
can be correctly analyzed.

Unfortunately, your comment is just a crafty way of saying that the analyzer
can ignore certain "trickier" inputs and still claim to be a solution to the
halting problem. If that's the case, then this is a solution to the halting
problem:

int WillHalt( string source, string input ) {
// It's tricky, so give up. Someone is trying to deceive me!
return UNKNOWN;
}

 

[Peter Olcott]

Unfortunately, your comment is just a crafty way of saying that the analyzer
can ignore certain "trickier" inputs and still claim to be a solution to the
halting problem. If that's the case, then this is a solution to the halting
problem:

int WillHalt( string source, string input ) {
// It's tricky, so give up. Someone is trying to deceive me!
return UNKNOWN;
}

Yet the crucial difference between my halt analyzer and yours is that
my halt analyzer works for all possible inputs, including the deceitful
program. It merely does not work on all possible invocations. Your
program will not work on all possible inputs.

My program directly contradicts this National Institute of Standards and
Technology definition of the Halting Problem, and yours does not.

No program can ever be written to determine whether any arbitrary
program will halt

http://www.nist.gov/dads/HTML/haltingProblem.html

 

[Howard]

Yet the crucial difference between my halt analyzer and yours is that
my halt analyzer works for all possible inputs, including the deceitful
program. It merely does not work on all possible invocations. Your
program will not work on all possible inputs.

Therein is a crucial flaw in your argument. If your analyzer can use
information about the method or source of invocation, then that information
is an INPUT to the analyzer! So your analyzer does NOT work for all
possible inputs.

-Howard