Re: Yet another Attempt at Disproving the Halting Problem

[Peter Olcott]

What tedious and amazing garbage you produce! One stands in awe.

The only reason that not everyone has agreed with everything
that I have said is that they don't bother to examine what I am
saying at the same level detail that makes what I say become true.
I a very subtle level of detail nearly everything that I have said
is fully true.

 

[Peter Olcott]

You've got it, Peter! You understand the proof!

Just one tiny little step that you seem to be leaping over:

If we know that there cannot be a halting analyzer that works correctly in
every possible instance, then we know that there cannot be a halting
analyzer. By definition a halting analyzer is one that works correctly in
every possible instance.

Bravo!

//
// All of the functions are assumed to be standard C++
//
void LoopIfHalts (string ProgramSourceFile, string InputData)
{
if WillHalt01(ProgramSourceFile, InputData)
while (true)
;
else // to make it easier for people who don't know C++
return;
}

bool WillHalt02(LoopIfHalts, LoopIfHalts)

What is the result of invoking WillHalt02 ?

 

[Robert Low]

The only reason that not everyone has agreed with everything
that I have said is that they don't bother to examine what I am
saying at the same level detail that makes what I say become true.

You mean the level of detail where one doesn't distinguish
'true' from 'false'?

I a very subtle level of detail nearly everything that I have said
is fully true.

For sufficiently small values of 'nearly' and 'fully'.

 

[Karl Heinz Buchegger]

//
// All of the functions are assumed to be standard C++
//
void LoopIfHalts (string ProgramSourceFile, string InputData)
{
if WillHalt01(ProgramSourceFile, InputData)
while (true)
;
else // to make it easier for people who don't know C++
return;
}

bool WillHalt02(LoopIfHalts, LoopIfHalts)

What is the result of invoking WillHalt02 ?

What does WillHalt02 do ?

 

[Kent Paul Dolan]

Or, are you _deliberately_ looking for
things to misunderstand in order to keep this discussion going?

Well, but now we come back to the famous cautionary note, whose
author I knew once upon a time, but have now forgotten, but which
_I_ first saw quoted by Jay Maynard:

Never attribute to malice that which can be adequately
explained by stupidity.

HTH

xanthian.

 

[Kent Paul Dolan]

The only reason that not everyone has agreed with
everything that I have said is that they don't
bother to examine what I am saying at the same
level detail that makes what I say become true.

Not everyone cares to enter your madness with you,
and that explains why you are not, really, mad?

I a very subtle level of detail nearly everything
that I have said is fully true.

Well, except for the parts where you are a genius,
and a working professional programmer, and hold a
computer science degree with an A- average, and have
overturned Goedel's proof of the incompleteness of
the usual formalism of mathematics, and have
overturned Turings' proof that the Halting Problem
is unsolvable, and understand with perfect clarity
logical discourse and mathematical proof and
computer theory.

We'll happily grant that you've probably spelled
your name correctly, which seems to be the only
remaining issue in doubt.

xanthian.

By the way, you might want to go over that last
"sentence" of yours with some care, looking for
problems in what you typed, so that you don't in
the future erroneously claim to be able to write
sentences in the English language, and have that
to retract along with all your other bogus
claims.

 

[David C. Ullrich]

Same Reasoning
If square root ever works at all, then square root
would work for negative numbers. Since square
root does not work for negative numbers, therefore
we can conclude that square root does not work at all.

no, idiot. what we can conclude from this is that there
is no function f:R->R such that f(x)^2=x for all x.
that's -true-. just as we conclude from the proof of
the unsolvability of the halting problem that there
is no tm that will determine whether T will halt,
for -every- tm T.

i've never known an actual genius before. are they
all so incredibly bad at incredibly simple logical
arguments?

************************

David C. Ullrich

sorry about the inelegant formatting - typing
one-handed for a few weeks...

 

[David C. Ullrich]

: Peter Olcott wrote:
: > His claim was that a halt analyzer could not work for any possible
: > inputs.

: I see no post that claimed any such thing. Furthermore, I see
: no plausible possibility that anyone, even Peter, could honestly
: infer than Marc Goodman's latest ancestor post meant any such
: thing.

Someone sort of unintentionally claimed this.
"It most definitely does say that a Turing Machine
that correctly decides whether any other Turing Machine and
input string correctly halts cannot exist."
But this is more to do with the ambiguity of English. I know the author
meant "any possible Turing Machine", i.e. "all Turing Machines", but
the "any" could be read to mean "any but not necessarily all".

i've often thought that the word 'any' should be banned, for
just this reason.

of course it doesn't usually cause any actual confusion,

: Peter, can you cite where someone's "claim was that a halt
: analyzer could not work for any possible inputs", or are you
: outright lying again?

He is just misreading something and then stubbornly refusing
to recognize what was meant.

except in cases like that.

Stephen

************************

David C. Ullrich

sorry about the inelegant formatting - typing
one-handed for a few weeks...

 

[Will Twentyman]

Same Reasoning
If square root ever works at all, then square root
would work for negative numbers. Since square
root does not work for negative numbers, therefore
we can conclude that square root does not work at all.

Two points: first, the domain of the square root function is usually
defined to be the non-negative reals to avoid working with complex
numbers. Second, I have a calculator that will quite happily do the
square root of negative numbers, and a similar function could be written
in whatever programming language you would like. In C++ writing a
complex number class is fairly simple, for example.

 

[Isaac To]

Karl> Because the square root function, as defined in C or C++,
Karl> doesn't attempt to compute the square root of everything.

Right, it is defined to work with all non-negative numbers smaller
than the maximum number representable by the machine architecture. As
long as you pass it the something right, you get something right,
i.e., an approximation of the mathematical square root.

Karl> But this is not what the Halting problem is about. The
Karl> Halting problem is about an analyzer which works in *all*
Karl> cases. Not a subset, not 10 different algorithms, not 100,
Karl> not 100000, not 10000000000000000000000000000000. *ALL*

The same can be said to the above. In this sense the halting problem
is not different from the square root problem: both have a definite
domain (numbers versus two "strings"---one being a representation of a
Turing machine and the other an arbitrary string). Both require a
program that would solve any problem within the specific domain. The
difference is that the first is solvable and the second is not.

Regards,
Isaac.

 

[Will Twentyman]

It is totally impossible for anyone or anything to ever tell if any at all program
will ever halt.

The second claim says that halt analyzer can exist, yet for a very tiny
fraction of possible input, will not produce correct results.

Since the Halt Analyzer is to be defined for *all* functions and inputs,
then 1) says it can't work on all, and 2) says it can't work on all.
There is no argument about the possibility of building a Halt Analyzer
for *some* functions and their inputs. The issue is *all*. 1) and 2)
say the same thing, Halt Analyzer cannot exist for *all* functions.

 

[Andrew Koenig]

You can tell the same thing with the Halting Problem, thus how
does the analogy fail?

Because in order to tell in advance the cases for which a Halt Analyzer
doesn't work, you must first solve the halting problem.

 

[Andrew Koenig]

It is totally impossible for anyone or anything to ever tell if any at all program
will ever halt.

The second claim says that halt analyzer can exist, yet for a very tiny
fraction of possible input, will not produce correct results.

I still see no difference between the two claims, except that one makes a
guess at probability (without any justification to back up the guess), and
the other doesn't.

The bottom line is that both claims say that it is impossible for anyone or
anything to ever tell if any program will ever halt.

In other words, the Halting Problem has no solution.

There's nothing more to say.

 

[Andrew Koenig]

The only reason that not everyone has agreed with everything
that I have said is that they don't bother to examine what I am
saying at the same level detail that makes what I say become true.
I a very subtle level of detail nearly everything that I have said
is fully true.

Just remember: "nearly" is merely a polite way of saying "not."

 

[Andrew Koenig]

Actually, it's possible to determine whether most programs halt,
using various heuristics. Just not all of them.

Unproven. It is likely to be possible to determine whether most programs
*that are written by humans* halt, provided that the programs actually do
what their authors claim that they do--but that claim is very different from
the claim that it is possible to make that determination for most programs.

 

[Andrew Koenig]

His claim was that a halt analyzer could not work for any possible
inputs.

For any possible inputs, or for every possible input? You say one thing in
the first paragraph above and the other in the third. They're not the same
claim. Which is it?

It is obviously false that a halt analyzer cannot work for *any* possible
input, because it can surely work for an empty program. So such a claim
would be pointless. The important claim is the one that a halt analyzer
cannot work for *every* possible input. In other words, for any given
program H that purports to be a halt analyzer, it is possible to find a
program P such that H cannot correctly analyze P.

This claim is so important that I'll say it again, in more precise terms:

If you show me a program H that claims to be a halt analyzer, then

I will give you a program P that H cannot analyze.

An essential part of the argument is that you have to show me H before I
show you P. In other words, P is allowed to depend on H, but H is not
allowed to depend on P. That is the distinction between "any" and "every".

 

[Marc Goodman]

//
// All of the functions are assumed to be standard C++
//
void LoopIfHalts (string ProgramSourceFile, string InputData)
{
if WillHalt01(ProgramSourceFile, InputData)
while (true)
;
else // to make it easier for people who don't know C++
return;
}

bool WillHalt02(LoopIfHalts, LoopIfHalts)

What is the result of invoking WillHalt02 ?

A working WillHalt01 cannot exist. A working WillHalt02 cannot
exist. Therefore, there can be no result from invoking WillHalt02.
Which is sort of the point of the whole proof, actually.

 

[Chris Menzel]

...
The only reason that not everyone has agreed with everything
that I have said is that they don't bother to examine what I am
saying at the same level detail that makes what I say become true.

But see, Peter, there is a reason for that. The "level of detail" that
makes what you say true -- as Aatu has very clearly pointed out -- also
makes what you say *utterly* trivial and uninteresting. When, in a
forum like this, an assertion has both an utterly trivial reading and a
bold and provocative one, it is quite natural to believe the poster
intends the latter. Moreover, you are being somewhat disingenuous here.
For it is quite clear that you yourself believed you had discovered an
earthshaking flaw in the foundations of computability theory, and you
advertised your discovery as such -- notably, you first claimed there
was a flaw in Turing's proof of the Halting Problem, and then when, for
a time, you seemed to admit that the proof was sound, you claimed that
the proof only showed that a certain *way* of trying to solve the
Halting Problem failed. If, all along, you really meant what you said
in the true, but trivial and uninteresting, sense you now claim, you'd
never have advertised your "discoveries" in the way you did.

I[n] a very subtle level of detail nearly everything that I have said
is fully true.

What makes your claims true is neither a matter of subtlety nor detail.
It's nothing more than the matter of heeding the standard mathematical
practice of defining one's terms with sufficient rigor -- a basic
obligation of mathematical discourse that you consistently refused to
accept throughout this entire exercise. The (somewhat pathological)
patience and persistence of your many interlocutors have finally driven
you into a corner, and it has become clear that your claims have turned

[Aatu wrote:]

Although it will obviously be of no use, I'll refrain from resisting the
tempation of writing this post and note that in fact 2[*] is exactly what
Turing proved and everyone has been trying to get you to understand.
There is only a slight terminological confusion: you call any
non-trivial partial solution to the Halting Problem a Halt Analyzer,
while others would reserve that word only to a total solution, i.e. one
for which there does not exist any circustamce, weird or otherwise, in
which the Halt Analyzer fails to produce correct results.

Just so.

Chris Menzel

[*]"Under certain weird circumstances, a Halt Analyzer will not produce
correct results."

 

[Julie]

<SNIP>

Can someone *PLEASE* explain to me what the halting problem or any of its
derivative sub-topics have to do w/ the C++ language?

If not, please refrain from including comp.lang.c++ in this (and
subsequent/related) thread(s).

Thanks

 

[Chris Menzel]

<SNIP>

Can someone *PLEASE* explain to me what the halting problem or any of
its derivative sub-topics have to do w/ the C++ language?

Sure: There is no C++ program that solves the Halting Problem.

;-)

Consider my headers henceforth appropriately edited.

-cm