Re: Yet another Attempt at Disproving the Halting Problem

[Peter Olcott]

Because it's a bunch of crap and everyone knows it.

A WillHalt algorithm that does not report its results is totally useless,
and determines exactly nothing.

SEE RIGHT HERE IS ANOTHER EXAMPLE! I ONLY SAID NOT
TO REPORT THE RESULT TO THE FUNCTION BEING ANALYZED,
AND YOU LEAP TO THE STUPID CONCLUSION WITHOUT
EVER PAYING ANY ATTENTION TO WHAT I AM SAYING!
I HAVE POSTED EXACTLY WHAT I MEAN BY THIS FOR
SEVERAL WEEKS. THE ADDRESS IS NOT HARD TO REMEMBER
ITS WWW.HALTING-PROBLEM.COM HOW THE HELL DO
YOU EXPECT TO REFUTE ME IF YOU DON'T EVEN KNOW
WHAT I AM SAYING ???

 

[Andrew Koenig]

Ah so you can have no idea the the case that defined the Halting Problem
might be a problem, until after it is not a problem?

No -- in order to be sure that the case that defines the Halting Problem
is actually a problem, you may have to wait forever.

 

[Marc Goodman]

No, it has been assumed to be true, and stated as if it
was a fact, many times. It has never once been shown.

No, it has been proven true. You are simply incapable
of understanding that proof. Sux to be you.

 

[Anonymous]

Dear Peter,

Please see below:

That sure sound like circular reasoning to me.

Yes, yes of course it does ... after all, you're a god damn idiot.

 

[The Ghost In The Machine]

In sci.logic, Andrew Koenig
<[email protected]>
wrote

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.

Good point. Evolutionary programming will lead to some
interesting constructs, methinks -- although I've not
worked with it myself. There's at least one construct --
I *would* forget the name -- which combines, in a rather
bizarre but syntactically and semantically correct fashion,
a while loop and a switch statement. (That one *is*
human-constructed, at least.)

So perhaps I should say "many". But in some cases it's far from
obvious, although the only example that comes to mind is the
Collatz Conjecture:

unlimited_integer n;

if(n <= 0) return;

while(n != 1)
{
if(n % 2 == 0) { n /= 2; }
else { n = 3*n+1; }
}

or some of the entries one might see in the Obfuscated C contest.

 

[stephen]

:>
:> : Your "void" function simply does not meet the requirements of determining
:> : success or failure in the first place. I know you disagree, but hey, you're
:> : simply wrong. Neener neener!
:>
:> The "void" function thing really does not matter. Even with that restriction
:> you can show that it does not alway print the correct value to the screen.
:> If WillHalt looks like
:>
:> void WillHalt(string program, string input)
:> {
:> bool halt;
:> //
:> // do some calculations to compute halt;
:> cout << halt << endl;
:> }
:>
:> it is guaranteed to print the wrong answer for the following program:
:>
:> void f1(string program, string input)
:> {
:> bool halt;
:> //
:> // do some calculations to compute halt;
:> while (halt);
:> }
:>
:> WillHalt has not been modified in any way, and it only prints its
:> value to the screen, but it is still trivial to show that there
:> are programs for which it will get the wrong answer.
:>
:> Stephen

: If you provide any form of the original halting problem
: as an example of this "wrong answer" I will be happy to
: point out where you err.

Your program will print out the wrong answer for f1. If your
program says f1 halts, then f1 will perform the exact same
calculation with the exact same input, and so will evaluate
halt to be non-zero and will therefore loop.

If your program says f1 loops, then f1 will perform the exact
same calculation with the exact same input, and so will evaluate
halt to be zero and will therefore halt.

Where did I err? Which of the unspecified ifs or whiles magically
behaves differently in the two different programs.

Again, if you want to make your case at all write two programs
of the following form that print out different results:

void f1(int x)
{
int h;
/* code to evaluate h
this code is identical in both programs
*/
cout << h << endl;
}

void f2(int x)
{
int h;
/* code to evaluate h
this code is identical in both programs
*/
cout << h << endl;
while (h);
}

If you can provide me with a program f1 and f2 that print different
results when given the same input then I might believe there is
something to your idea. This is after all what you are claiming
how your WillHalt avoids getting a wrong answer.

Stephen

 

[Bryan Olson]

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

Writing a statement that cannot be deliberately misinterpreted
turns out to be somewhat difficult. If Peter honestly thought
Marc meant what Peter said the claim was, that would be a simple
mistake. But that's not plausible.

 

[Robert Low]

It was perfectly valid C++.

Oh, my mistake. Then I suggest that you immediately
write routines which will enable you to settle
the Goldbach conjecture, whether there are infinitely
many twin primes, and whether the hailstone number
sequences all terminate, and publish now. Fame and
glory await you.

 

[Peter Olcott]

:>
:> : Your "void" function simply does not meet the requirements of determining
:> : success or failure in the first place. I know you disagree, but hey, you're
:> : simply wrong. Neener neener!
:>
:> The "void" function thing really does not matter. Even with that restriction
:> you can show that it does not alway print the correct value to the screen.
:> If WillHalt looks like
:>
:> void WillHalt(string program, string input)
:> {
:> bool halt;
:> //
:> // do some calculations to compute halt;
:> cout << halt << endl;
:> }
:>
:> it is guaranteed to print the wrong answer for the following program:
:>
:> void f1(string program, string input)
:> {
:> bool halt;
:> //
:> // do some calculations to compute halt;
:> while (halt);
:> }
:>
:> WillHalt has not been modified in any way, and it only prints its
:> value to the screen, but it is still trivial to show that there
:> are programs for which it will get the wrong answer.
:>
:> Stephen

: If you provide any form of the original halting problem
: as an example of this "wrong answer" I will be happy to
: point out where you err.

Your program will print out the wrong answer for f1. If your
program says f1 halts, then f1 will perform the exact same
calculation with the exact same input, and so will evaluate
halt to be non-zero and will therefore loop.

NOT AT ALL! MY PROGRAM DOES NOT FEED ITS RESULT
BACK TO THE f1() FUNCTION. BECAUSE IT DOES NOT
FEED ITS RESULT BACK TO THE f1() FUNCTION, THE f1()
FUNCTION CAN NOT CHANGE ITS BEHAVIOR BASED ON
THIS RETURNED RESULT. THE CHANGED BEHAVIOR
DERIVES A CHANGED HALT ANALYSIS.

 

[stephen]

:>
:> :>
:> :> : Your "void" function simply does not meet the requirements of determining
:> :> : success or failure in the first place. I know you disagree, but hey, you're
:> :> : simply wrong. Neener neener!
:> :>
:> :> The "void" function thing really does not matter. Even with that restriction
:> :> you can show that it does not alway print the correct value to the screen.
:> :> If WillHalt looks like
:> :>
:> :> void WillHalt(string program, string input)
:> :> {
:> :> bool halt;
:> :> //
:> :> // do some calculations to compute halt;
:> :> cout << halt << endl;
:> :> }
:> :>
:> :> it is guaranteed to print the wrong answer for the following program:
:> :>
:> :> void f1(string program, string input)
:> :> {
:> :> bool halt;
:> :> //
:> :> // do some calculations to compute halt;
:> :> while (halt);
:> :> }
:> :>
:> :> WillHalt has not been modified in any way, and it only prints its
:> :> value to the screen, but it is still trivial to show that there
:> :> are programs for which it will get the wrong answer.
:> :>
:> :> Stephen
:>
:> : If you provide any form of the original halting problem
:> : as an example of this "wrong answer" I will be happy to
:> : point out where you err.
:>
:> Your program will print out the wrong answer for f1. If your
:> program says f1 halts, then f1 will perform the exact same
:> calculation with the exact same input, and so will evaluate
:> halt to be non-zero and will therefore loop.

: NOT AT ALL! MY PROGRAM DOES NOT FEED ITS RESULT
: BACK TO THE f1() FUNCTION. BECAUSE IT DOES NOT
: FEED ITS RESULT BACK TO THE f1() FUNCTION, THE f1()
: FUNCTION CAN NOT CHANGE ITS BEHAVIOR BASED ON
: THIS RETURNED RESULT. THE CHANGED BEHAVIOR
: DERIVES A CHANGED HALT ANALYSIS.

But f1 contains the exact same code as your program. I am not
claiming your program returns a value to f1. f1 does not call
your program. f1 just contains the exact same source code,
with a while loop added on at the end. There is no "feeding",
there is no behavior being changed. I am simply asking your
program if f1 will halt or not, and your program is guaranteed
to get the wrong answer.

How does the while loop added on at the end change the behavior
of the earlier code? Again, I challenge you to write two functions
of the following form that print out different values

void f1(int y)
{
int x;
// code to evalate x
// this code is the same in f1 and f2
cout << x << endl;
}

void f2(int y)
{
int x;
// code to evalate x
// this code is the same in f1 and f2
cout << x << endl;
while(x);
}

Do you really believe you can write functions that differ
only by a while(x) at the end that somehow produce different results?

Stephen

 

[Owen Jacobson]

In sci.logic, Andrew Koenig
<[email protected]>
wrote


Good point. Evolutionary programming will lead to some
interesting constructs, methinks -- although I've not
worked with it myself. There's at least one construct --
I *would* forget the name -- which combines, in a rather
bizarre but syntactically and semantically correct fashion,
a while loop and a switch statement. (That one *is*
human-constructed, at least.)

Duff's Device?

/* appropriate declarations */
n=(count+7)/8;
switch(count%8){
case 0: do{ *to = *from++;
case 7: *to = *from++;
case 6: *to = *from++;
case 5: *to = *from++;
case 4: *to = *from++;
case 3: *to = *from++;
case 2: *to = *from++;
case 1: *to = *from++;
}while(--n>0);
}

<http://www.lysator.liu.se/c/duffs-device.html>

 

[Owen Jacobson]

void f1(int y)
{
int x;
// code to evalate x
// this code is the same in f1 and f2
cout << x << endl;
}

void f2(int y)
{
int x;
// code to evalate x
// this code is the same in f1 and f2
cout << x << endl;
while(x);
}

Do you really believe you can write functions that differ
only by a while(x) at the end that somehow produce different results?

We've been around this post already. Unfortunately, he honestly does
believe that this results in a different outcome.

 

[Owen Jacobson]

SEE RIGHT HERE IS ANOTHER EXAMPLE! I ONLY SAID NOT
TO REPORT THE RESULT TO THE FUNCTION BEING ANALYZED,
AND YOU LEAP TO THE STUPID CONCLUSION WITHOUT
EVER PAYING ANY ATTENTION TO WHAT I AM SAYING!
I HAVE POSTED EXACTLY WHAT I MEAN BY THIS FOR
SEVERAL WEEKS. THE ADDRESS IS NOT HARD TO REMEMBER
ITS WWW.HALTING-PROBLEM.COM HOW THE HELL DO
YOU EXPECT TO REFUTE ME IF YOU DON'T EVEN KNOW
WHAT I AM SAYING ???

No. What he is saying is that, in order to be of interest, a program
to determine if (program, input) pairs halt must leave the machine in a
state where it is possible to find out what that result was. In your
terms, "in order to be of interest the Halts(M, x) function must return a
value."

Quoth Peter Olcott @ <http://www.halting-problem.com/>[0]:
"A simple way to eliminate access to the return value of WillHalt() is
to simply not return this value to the caller."

Your proposed construction of Halt(M, x) is useless, as it does not
provide any information about whether the given (program, input) pair
halts. Furthermore, we *must* necessarily be able to take the steps
involved in Halts(M, x) and use them in another function, modifying it in
provably-correct ways to "return".

Halts(M, x) has no way of determining whether the input program is the
same as the "calling" program -- it merely determines if the given
program would halt on the given input.

Given this, it *must* be true that we can build arbitrary, valid programs
that "call" Halts(M, x) and operate on the "returned" value. Given this,
it *must* be possible to construct Turing's proof, which describes a
(program, input) pair that Halts(M, x) *cannot* correctly analyze.

[0] There's a bit of entertaining madness on Peter's "program trace", too:

**************************************************************
**************** Solved Halting Problem **********************
**************************************************************

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

The underlined function is Halts(M, x). The given "WillHalt" function is
NOT Halts(M, x), but rather a function constructed using Halts(M, x).

 

[Peter Olcott]

But this isn't "one way to try to solve" the Halting Problem. Or if it
is, it's spectacularly stupid one. Specifications for Turing machines
don't contain transitions labeled "input TM will halt" or "input TM will

They simply don't have state transition diagrams at all, yet this is
still a valid representation of the material in the proof. I merely
made it more clear by specifically labeling the state transitions.

NOT halt", so the above is not a Turing machine, which makes it rather
trivial that it can't be a way to solve the Halting Problem.

The above is almost exactly a verbatim quote of page 319 of this proof.
I only added labels to the transitions.

Note this material must be printed out to be read, and takes about two
minutes of download time.
http://home.att.net/~olcott/halting/proof.html

Turing's proof goes like this: the output of every Turing machine
differs from the function

Halt(A,x) = 1 if the machine described by A halts when given x as input
0 otherwise

in at least one argument pair. To demonstrate this, consider any Turing
machine M. As is known, there is a universal Turing machine U, s.t.
U(A,x,y) = A(x,y). From the instructions of U and M a Turing machine E_M
can be constructed as follows. When given input A the machine E_M
executes the instructions of the Universal Turing machine U, giving to
it as arguments M, A and A. Then depending on the output of U on these
arguments, it loops for ever if U(M,A,A) gives 1 as output and halts
otherwise. We see easily that M(E_M,E_M) necessarily differs from
Halt(E_M,E_M), thus showing that M differs from Halt(A,x) at least for
one argument pair, namely (E_M,E_M).

There is no "one way to try to solve the Halting Problem" here. If you
think there is, please indicate where exactly it occurs.

Let's untangle your somewhat convoluted description:

H=Turing Machine that determines Halting for S on D.
S =SourceCode for a Turing Machine
D=Data Input for a Turing Machine (including S)

H(S, D)--->if(S Halts on D) return 1;
E_M(S, D)--->if (H(S, D) ==1) Loop
Does H(E_M, E_M) return a 1? (YES)

There are two invocations of H here. The first invocation calls E_M, which
calls H. The first (outermost) invocation can correctly return a 1, whereas the
nested invocation must refrain from returning a 1. The invocation that is called
from E_M can see that if it returns a 1, that E_M will immediately go into an
infinite loop. Because it can see this, it refrains from returning a 1. It knows
that it will halt, yet is prohibited from reporting this.

 

[Peter Olcott]

SEE RIGHT HERE IS ANOTHER EXAMPLE! I ONLY SAID NOT
TO REPORT THE RESULT TO THE FUNCTION BEING ANALYZED,
AND YOU LEAP TO THE STUPID CONCLUSION WITHOUT
EVER PAYING ANY ATTENTION TO WHAT I AM SAYING!
I HAVE POSTED EXACTLY WHAT I MEAN BY THIS FOR
SEVERAL WEEKS. THE ADDRESS IS NOT HARD TO REMEMBER
ITS WWW.HALTING-PROBLEM.COM HOW THE HELL DO
YOU EXPECT TO REFUTE ME IF YOU DON'T EVEN KNOW
WHAT I AM SAYING ???

No. What he is saying is that, in order to be of interest, a program
to determine if (program, input) pairs halt must leave the machine in a
state where it is possible to find out what that result was. In your
terms, "in order to be of interest the Halts(M, x) function must return a
value."

Quoth Peter Olcott @ <http://www.halting-problem.com/>[0]:
"A simple way to eliminate access to the return value of WillHalt() is
to simply not return this value to the caller."

Your proposed construction of Halt(M, x) is useless, as it does not
provide any information about whether the given (program, input) pair
halts.

TO THE PRORGAM BEING ANALYZED. I SPECIFICALLY SAID
THAT IT DOES PROVIDE THIS INFORMATION, JUST, NOT
TO THE PROGRAM BEING ANLYZED. I HAVE SAID THIS
SEVERAL HUNDRED TIMES AND YOU STILL DON'T GET IT???

Furthermore, we *must* necessarily be able to take the steps
involved in Halts(M, x) and use them in another function, modifying it in
provably-correct ways to "return".

Halts(M, x) has no way of determining whether the input program is the
same as the "calling" program -- it merely determines if the given
program would halt on the given input.

Given this, it *must* be true that we can build arbitrary, valid programs
that "call" Halts(M, x) and operate on the "returned" value. Given this,
it *must* be possible to construct Turing's proof, which describes a
(program, input) pair that Halts(M, x) *cannot* correctly analyze.

[0] There's a bit of entertaining madness on Peter's "program trace", too:

**************************************************************
**************** Solved Halting Problem **********************
**************************************************************

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

The underlined function is Halts(M, x). The given "WillHalt" function is
NOT Halts(M, x), but rather a function constructed using Halts(M, x).

 

[Eray Ozkural exa]

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


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

Post of the day

There is an awful fact about net.kooks that people learn the hard way:
arguing with them makes us seem disagreeable as well, so the best is
to point out that we think he is a kook and avoid responding further
as Torkel suggests.

Regards,

 

[Peter Olcott]

Post of the day

There is an awful fact about net.kooks that people learn the hard way:
arguing with them makes us seem disagreeable as well, so the best is
to point out that we think he is a kook and avoid responding further
as Torkel suggests.

Regards,

Ah so pointing out any errors that I have made in an objective
way, without resorting to disdain is not reasonable? So far it
seems I am mostly only getting disdain. I am not getting any
valid refutations.

 

[Marc Goodman]

Ah so pointing out any errors that I have made in an objective
way, without resorting to disdain is not reasonable? So far it
seems I am mostly only getting disdain. I am not getting any
valid refutations.

First we start with the valid refutations. Then we proceed
to disdain when you are unable to understand them. This
surprises you? You should be used to this from your IAMYHWH
and refuting Go:del discussions. I would think you'd be
pretty much immune to disdain by now.

 

[Peter Olcott]

In comp.theory Peter Olcott <[email protected]> wrote:

: NOT AT ALL! MY PROGRAM DOES NOT FEED ITS RESULT
: BACK TO THE f1() FUNCTION. BECAUSE IT DOES NOT
: FEED ITS RESULT BACK TO THE f1() FUNCTION, THE f1()
: FUNCTION CAN NOT CHANGE ITS BEHAVIOR BASED ON
: THIS RETURNED RESULT. THE CHANGED BEHAVIOR
: DERIVES A CHANGED HALT ANALYSIS.

But f1 contains the exact same code as your program. I am not
claiming your program returns a value to f1. f1 does not call
your program. f1 just contains the exact same source code,
with a while loop added on at the end. There is no "feeding",
there is no behavior being changed. I am simply asking your
program if f1 will halt or not, and your program is guaranteed
to get the wrong answer.

No, there is a subtle but crucial difference between what you said,
and what would actually occur. My program still GETS the right
answer, and it sees that it is prohibited from providing this correct
answer to your f1() function, otherwise f1() would use this to change
its behavior, thus making this right answer into a wrong answer.
So for all practical purposes, adding this feedback loop effectively
disables the output mechanism. The halt analyzer still gets the correct
results.

How does the while loop added on at the end change the behavior
of the earlier code? Again, I challenge you to write two functions
of the following form that print out different values

void WillHalt(string program, string input)
{
bool halt;
//
// do some calculations to compute halt;
cout << halt << endl;
}

void f1(string program, string input)
{
bool halt;
//
// do some calculations to compute halt; // see notes
while (halt);
}

cout << WillHalt(f1) // outputs true
cout << WillHalt(f2) // outputs true

*** NOTES ***
The invocation of the halt analyzer from the specific context
of f1() will not return true. From this specific context it will
see that returning true will be used by f2() to make true an
incorrect answer, thus refrain from returning true within this
specific context.

 

[Simon G Best]

In your first post in this thread, you said, "Anyone willing to help me
learn this proof, your help would be greatly appreciated." The "proof"
you were referring to, of course, was Turing's proof of the nonexistence
of a general solution to The Halting Problem.

[...]

Let's untangle your somewhat convoluted description:

H=Turing Machine that determines Halting for S on D.
S =SourceCode for a Turing Machine
D=Data Input for a Turing Machine (including S)

H(S, D)--->if(S Halts on D) return 1;
E_M(S, D)--->if (H(S, D) ==1) Loop
Does H(E_M, E_M) return a 1? (YES)

I think you've made a mistake in your attempt to "untangle" Aatu's
"somewhat convoluted description". E_M takes two arguments, but H would
determine whether or not E_M would halt on the single argument E_M.
Let's look at what you probably meant (using your sort of notation).

H(S, D) --> if (S halts on D) return 1; else return 0.

E_M(S) --> if (H(S, S) == 1) loop forever; else return 0.

Does H(E_M, E_M) return a 1?

There are two invocations of H here. The first invocation calls E_M, which
calls H. The first (outermost) invocation can correctly return a 1, whereas the
nested invocation must refrain from returning a 1.

(Which do you mean by "first"? You seem to have got confused.)

Indeed, H(E_M, E_M) either evaluates to 1, or it doesn't.

The invocation that is called
from E_M can see that if it returns a 1, that E_M will immediately go into an
infinite loop. Because it can see this, it refrains from returning a 1.

Indeed, from the definitions of H and E_M, H(E_M, E_M) can't evaluate to
1. Also from the definitions of H and E_M, H(E_M, E_M) can't evaluate
to 0. From the definition of H, H(E_M, E_M) must evaluate to either 0
or 1. That's obviously a contradiction. Therefore, it must be that E_M
cannot exist.

If E_M cannot exist, then H cannot exist. Why? Because if H could
exist, then E_M could exist, and we now know that E_M can't exist.

It knows that it will halt, yet is prohibited from reporting this.

It doesn't know anything. It's a Turing Machine. Turing Machines don't
know anything, ever. They're just dumb machines.

Anyway, does this help to clarify Turing's proof?

Simon