Solution to the halting Problem?

[Stewart Gordon]

The function that does not return a value does correctly determine
halting for all inputs, including the function that does return this
value.

Then so will the one generated by modifying your algorithm, replacing
all occurrences of 'write the result to console' or whatever with
'return the result', and changing nothing else.

Even if the result is built up and written to the console little by
little, all occurrences of 'write to console' can be replaced by 'write
to a file', and then the final action of WillHalt can be to read the
file back in and return its contents. Or you can bypass the file, and
use an in-memory buffer.

A single valid counter-example is all that is required. I provided
that.

<snip>

What are you referring to as "a single valid counter-example"? A single
algorithm that can be proven to halt or not halt given arbitrary input?
That isn't what the halting problem means.

Or a single version of WillHalt that will not work with the original
proof? A necessary prerequisite for the theorem to be false is that
your version of WillHalt genuinely cannot be changed into one that is
compatible with the proof. And obviously your example doesn't satisfy
this requirement.

The logic of the proof is still there, it just has one more link in its
chain.

WillHalt can be constructed
=> WillHalt that returns its result can be constructed
=> The LoopIfHalts function can be constructed based on the
result-returning WillHalt
=> The LoopIfHaltsOnItself function can be constructed
=> LoopIfHaltsOnItself can be applied to itself
=> Contradiction.

Here, I'll go down in history for having just extended the standard
proof to deal with your idea.

Stewart.

 

[Jacques Labuschagne]

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

You don't remember the fun and games last time Olcott was here? His
"faster" string implementation? You're just wasting your time...

Jacques.

 

[David Hilsee]

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

I remember the FastString class. In my mind, I didn't classify him as a
crackpot when I read his posts about FastString. I just thought that he
enjoyed showing that he could write a class that, for most test cases, is
more efficient than certain std::string implementations.

Thanks for cutting in. This cycle might not end if I don't stop, breathe
deeply, and just walk away from the argument.

 

[Karl Heinz Buchegger]

Then so will the one generated by modifying your algorithm, replacing
all occurrences of 'write the result to console' or whatever with
'return the result', and changing nothing else.

Even if the result is built up and written to the console little by
little, all occurrences of 'write to console' can be replaced by 'write
to a file', and then the final action of WillHalt can be to read the
file back in and return its contents. Or you can bypass the file, and
use an in-memory buffer.

Peter does not understand that algorithms produce a result. In which form
this result is presented is completely unimportant and such not part of
the algorithm. And having an algorithm which produces absolutely no result
(or does not present its result) is of no particular use. However there
will always be ways to feed the result back to the program. Hint to Peter:
even if you eliminate all ways that your program can directly get at the
result, there are ways to do it. Eg. By calling you version of the WillHalt()
function and then asking the user what the WillHalt() function output was.

Peter reminds me of the Crab in Hofstadter's "Goedel, Escher, Bach" trying
to defend the idea of a record player that can reproduce any and all sounds.

 

[tom_usenet]

I remember the FastString class. In my mind, I didn't classify him as a
crackpot when I read his posts about FastString. I just thought that he
enjoyed showing that he could write a class that, for most test cases, is
more efficient than certain std::string implementations.

Yes, I was one of the unfortunate perpetrators of the thread. I no
longer remember the details of his flawed logic, but I distinctly
remember that his argumentative style was highly dishonest and
illogical. His FastString contained several bugs which helped it
outperform std::string. e.g. s += s[0]; didn't always work, and it
wasn't exception safe. But it was of course much slower in some
circumstances, and he never gave a real world example to demonstrate
it's superiority outside benchmarks. OTOH, the thread was useful in
highlighting the performance problems of std::string, which tries to
be a jack of all trades and is therefore a master of none.

Thanks for cutting in. This cycle might not end if I don't stop, breathe
deeply, and just walk away from the argument.

I could see this one turning into a big thread, and it's not worth
wasting your time trying to persuade a crackpot that they are one. He
clearly doesn't understand the concept of formal proofs. He'd get
"null points" if he submitted his "proofs" to a
teacher/academic/mathematician/etc.

Tom

 

[tom_usenet]

You don't remember the fun and games last time Olcott was here? His
"faster" string implementation? You're just wasting your time...

Yes, I remember quite clearly, although he did at least have 1 or 2
valid points in that thread, rather than the 0 success rate in this
one. It's worth posting a few times just so that the uninitiated
reading the thread have no doubt about who is correct and who very
definitely isn't. I've bowed out too now though (and I posted
something similar to your post yesterday in the another thread
strand!).

Tom

 

[Peter Olcott]

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?

If you bothered to read what I said instead of just making assumptions,
then you would already have this answer.

 

[Peter Olcott]

Peter does not understand that algorithms produce a result. In which form

this result is presented is completely unimportant and such not part of
the algorithm.

Since the result is returned to the program being analyzed, and the result
changes the behavior of the program being analyzed, therefore the result
of the analysis is different. If the result is NOT returned to the program
being analyzed, then the behavior of the program is NOT changed, and
the result of the analysis is conclusive. It really very simple.

And having an algorithm which produces absolutely no result
(or does not present its result) is of no particular use. However there

You didn't bother to read what I said all the way through either did you?
If you would have read what I said ALL THE WAY THROUGH, you
would see that your last statemnt is false.

will always be ways to feed the result back to the program. Hint to Peter:
even if you eliminate all ways that your program can directly get at the
result, there are ways to do it. Eg. By calling you version of the WillHalt()
function and then asking the user what the WillHalt() function output was.

This will not work in this case. That would be answers to frequent objections
02.

 

[Peter Olcott]

WillHalt(LoopIfHalts, LoopIfHalts)
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

Since the result is returned to the program being analyzed, and the result
changes the behavior of the program being analyzed, therefore the result
of the analysis is different. If the result is NOT returned to the program
being analyzed, then the behavior of the program is NOT changed, and
the result of the analysis is conclusive. It really very simple.

 

[Karl Heinz Buchegger]

Since the result is returned to the program being analyzed, and the result
changes the behavior of the program being analyzed, therefore the result
of the analysis is different. If the result is NOT returned to the program
being analyzed, then the behavior of the program is NOT changed, and
the result of the analysis is conclusive. It really very simple.

Here is you logical flaw.
As long as you somehow present the result (and you have to do that, otherwise
the whole thing is useless) there are *always* ways to 'return' the result
to the program. Even if that means that the program asks the user: 'What
was the result?' and the user has to enter what WillHalt() printed on the
screen. So even if you try to eliminate all ways to return that information
to the program (as you do by dropping the return value, not allowing the
program to get at that information from the screen buffer memory and whatever
you thouhgt up on your web site) there is only one way to completely close
the information-return-path: not outputting that information at all. But then
your WillHalt() tester is useless.
So there are 2 choices:
1) either WillHalt() outputs some information
2) or it does not. In this case it is useless because it is the nature of
a tester to come up with some result. No result -> no tester

From this it follows that we have to accept 1)
Now if we are with choice 1) then it doesn't matter what you do, the calling
function can get at that information which makes your method just a complicated
case of the original proof. And the conclusion from the original method was:
WillHalt() cannot exist.

qed

You didn't bother to read what I said all the way through either did you?
If you would have read what I said ALL THE WAY THROUGH, you
would see that your last statemnt is false.

Well.
If I am presented with a proof that something cannot exist and minds
brigther then you or I or the complete intelligence of that group confirmed
that proof to be correct, I don't question it.

 

[Karl Heinz Buchegger]

Since the result is returned to the program being analyzed, and the result
changes the behavior of the program being analyzed, therefore the result
of the analysis is different. If the result is NOT returned to the program
being analyzed, then the behavior of the program is NOT changed, and
the result of the analysis is conclusive. It really very simple.

An important part of that proof is *that* the information is returned.
You cannot eliminate that without destroying the proof.

You act like somebody saying:

Hay, in Euclids proof for an infinite amount of prime numbers there
is an addition. I don't like that addition thus I replace it with a
multiplcation. Then the proof no longer works and hence there is
an upper bound for the number of prime numbers.

That's simply absurd.

 

[tom_usenet]

An important part of that proof is *that* the information is returned.
You cannot eliminate that without destroying the proof.

You act like somebody saying:

Hay, in Euclids proof for an infinite amount of prime numbers there
is an addition. I don't like that addition thus I replace it with a
multiplcation. Then the proof no longer works and hence there is
an upper bound for the number of prime numbers.

That's simply absurd.

I wouldn't bother arguing with him if I were you; it's a waste of
time.

Tom

 

[Stewart Gordon]

Since the result is returned to the program being analyzed, and the
result changes the behavior of the program being analyzed,

You mean you've found a way to forcibly give a return statement the side
effect of modifying the algorithm it's just finished testing? I'd like
to see it.

therefore the result of the analysis is different. If the result is
NOT returned to the program being analyzed, then the behavior of the
program is NOT changed,

<snip>

Who said anything about a program X calling WillHalt(X)?

Stewart.

 

[Peter Olcott]

You mean you've found a way to forcibly give a return statement the side
effect of modifying the algorithm it's just finished testing? I'd like
to see it.

http://www.netaxs.com/people/nerp/automata/halting2.html
This is how the Halting Problem is defined. The only reason
that the Halting Problem is a problem is that your are required
to analyze the same program that is calling your program.

 

[Peter Olcott]

An important part of that proof is *that* the information is returned.
You cannot eliminate that without destroying the proof.

It is my goal to destroy this proof. As long as I can refute this statement:

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

I have correctly refuted the original Halting Problem proof. The mistake all
along is that returning the result to the caller was NEVER REQUIRED.

 

[David Hilsee]

unaffected

Since the result is returned to the program being analyzed, and the result
changes the behavior of the program being analyzed, therefore the result
of the analysis is different. If the result is NOT returned to the program
being analyzed, then the behavior of the program is NOT changed, and
the result of the analysis is conclusive. It really very simple.

The above paragraph doesn't make sense to me. Do you think that I'm trying
to modify your analysis program? I'm not. I'm producing source code (just
text, not an executable) for you to pass as input to your program. The
input source code resembles the source for your program because it uses the
same logic that your analysis program uses. That's the case when the
program fails: when the input uses a specially-crafted version of the very
program that is performing the analysis. It fails because
WillHaltWithReturnValue() fails, plain and simple.

This will hopefully be my last post in this thread, because tom_usenet has
talked some sense in to me. I'm not going to argue with you any more. I
just wanted to leave a final message with instructions on how you may come
to realize that your function, WillHalt(), is incorrect for the same input
that the other function, WillHaltWithReturnValue() is incorrect. To be
honest, I'm feeling sorry for you because everyone else seems to "get it"
and you don't. If these instructions help you to see the truth, then please
post a response saying so, because it will at least make me feel as though
my time has not been wasted.

Clear your mind of compilers, interpreters, executeable files, memory,
binary, and other things that we use to translate an abstract flow into a an
implementation of that flow, because they are irrelevant. If you ever get
an idea to you could use any of them to differentiate between the two
functions, ignore it. The halting problem works on an abstract machine, and
because all implementations of the machine are subject to the same rules for
implementing the logical flow, anything proven about this primitive abstract
machine applies to any implementation. Consider a fictional machine that
may not be anything like what you are using today. Focus on the Turing
machine.

Avoid using the word "result" to mean something that is a property of the
implementation. For example, do not say that the result is a bit pattern,
or the result is some file, or the result is in the stack. If you do that,
then you are not thinking about the abstract machine. You may accidentally
think that two results are not the same because they do not have the same
representation in the implementation. The representation of a result in the
implementation is irrelevant when considering its correctness. A integer
result of zero that indicates false, a file containing the string "false",
and someone's whispering of "false" in your ear are all equivalent results
because they indicate the same thing. That is, they are the same answer
with a different, irrelevant, representation. As an analogy, if I ask you
to give me the names of all 50 states, and you give me a piece of paper with
them written down, you are just as correct when you say them aloud.

Keep in mind that the UNKNOWN should never be reached for valid input. In
that case, the result must be TRUE or FALSE. If the input is valid and the
program returns UNKNOWN, then it has failed the test. If UNKNOWN were to be
an acceptable answer for valid input, then a program that only consisted of
"return UNKNOWN;" would be a solution. I kept the UNKNOWN value in the
source because I thought it might be used for invalid input and I wanted it
to be as close to the original function as possible. I probably should have
removed it to avoid confusion.

Lastly, avoid focusing on one particular sentence in my posts. I usually
break my posts up into paragraphs for a good reason, so try to understand
the entire paragraph when you apply my posts to your halting problem
"solution."

Now, if you look at the two functions provided and still argue that the
result when display on the screen can be different than the result provided
in the return value, then you must be appealing to an irrelevant
implementation detail that does not affect the result. Once you understand
why both functions, given any input, always produce the same result, you
will understand that they are both wrong when passed the "difficult input"
that looks something like the code I gave you. Remember: a program that,
for every input, always produces the same result as a program that is
incorrect on a particular input will also be incorrect on the same input,
even if the executing code is different. If you're still having problems,
see the post where I provided source code, go to the link I provided, and
make sure you fully understand it. Now consider the case when my source is
passed to your function.

If you think the above points are debateable and wish to respond to them, I
will read your response and consider your counterpoints, but I will probably
not respond back.

 

[Peter Olcott]

Here is you logical flaw.

As long as you somehow present the result (and you have to do that, otherwise
the whole thing is useless) there are *always* ways to 'return' the result
to the program. Even if that means that the program asks the user: 'What
was the result?' and the user has to enter what WillHalt() printed on the
screen.

Ah so the user is a slave to the program? I don't buy it.

So even if you try to eliminate all ways to return that information
to the program (as you do by dropping the return value, not allowing the
program to get at that information from the screen buffer memory and whatever
you thouhgt up on your web site) there is only one way to completely close
the information-return-path: not outputting that information at all. But then
your WillHalt() tester is useless.

I know that this seems like a valid refutation. I also know that it is
not a valid refutation. If this was a valid refutation then it could be
claimed that no program has ever worked, because someone could
always come along and destroy the computer, thus making it not
work. All the I am required to do to refute the original proof is to
derive one single way that the following statement can be refuted:

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

This way is not required to work under all conditions such as:
(1) Destroying the computer that is running the program.
(2) Erasing the program from the computer.
(3) Inserting bugs into the executable program, thus corrupting it.

It only needs to work correctly for all inputs. My idea would
work correctly for all inputs.

 

[Peter Olcott]

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.

Except that the statement below has now been refuted:

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

Since this is the definition of the Halting Problem, the
halting Problem itself has now been refuted.

 

[Peter Olcott]

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.

I never said anything like that. You must be confusing
me with someone else.

 

[David Hilsee]

http://www.netaxs.com/people/nerp/automata/halting2.html
This is how the Halting Problem is defined. The only reason
that the Halting Problem is a problem is that your are required
to analyze the same program that is calling your program.

Ugh, I just posted a long message in another thread, claimed it was going to
be my last, and here I am typing another. I just couldn't let this slide.

That is not the reason that the Halting Problem is a problem. It is a
problem because the analyzing program cannot process specific,
specially-designed input sources that contain logic taken from its own
source because, for those sources, the analyzer cannot produce a result that
avoids a contradiction of the result that would be produced by the stolen,
embedded logic if it were executed. That stolen logic may be modified
slightly to produce return values, but as long as the logic produces the
same result, the problem remains.

At least I kept it short and sweet this time.