Re: Yet another Attempt at Disproving the Halting Problem

[Karl Heinz Buchegger]

Yet I dispute this conclusion. using the method that I propose
a halt analyzer can be constructed from an ordinary Turing Machine
that is not prohibited from providing correct results for every
possible input. Or at least not prohibited in the sense of the
proof that this is (was considered to be) impossible.

You make another logical mistake.

The original proof starts with:
*Assume* that a function WillHalt exists.

Even if we follow your argumentation (what we dont'), the only thing
you would have shown is:
If I assume that a function WillHalt() exists, I can write a function
WillHalt().
That's not very spectecular.

The trick in the original proof is:
Even if we assume that such a function can exist, we can show that it
cannot exist.
That is something remarkable, but if you turn it around you are left
with: nothing at all. You can assume as long as you want, if the result
is that it can be done, under the assumption that it can be done, you
gained nothing.

Usually it is easier to proove that something cannot exist then the
opposite. If you claim X, and you want to show that X is not true
all you need is one lousy single counterexample. But if you want
to show that X holds, no matter what, it usually is much more work.

 

[Simon G Best]

Yet I dispute this conclusion. using the method that I propose
a halt analyzer can be constructed from an ordinary Turing Machine
that is not prohibited from providing correct results for every
possible input.

Turing has already refuted this. That's what his proof /is/.

Or at least not prohibited in the sense of the
proof that this is (was considered to be) impossible.

Incorrect. You *still* do not understand the proof you're trying to refute.

Simon

 

[Peter Olcott]

Turing has already refuted this. That's what his proof /is/.


Incorrect. You *still* do not understand the proof you're trying to refute.

Simon

Circular reasoning gets you exactly nowhere with me, sorry.
You think that Turing's proof is true, specifically because you
think it is true. I have shown where and why and how it is false.

 

[Simon G Best]

Statement A: Peter Olcott will never know that Statement A is true.

Circular reasoning gets you exactly nowhere with me, sorry.
You think that Turing's proof is true, specifically because you
think it is true.

No. I did not think Turing's proof was correct (or incorrect) /until/ I
had studied it enough to be certain that I could not possibly refute it.
There is no circular reasoning in that.

In fact, at the time, I really didn't want Turing's proof to be correct.
But the more I tried to find a way around it, the more I tried to find
a flaw in it, the more I learned, and the more I realised just how
irrefutable it is.

I have shown where and why and how it is false.

No you haven't. You're just pretending that you have.

Simon

 

[Peter Olcott]

It has nothing to do with deduction or induction, Peter.

http://c2.com/cgi/wiki?AdVerecundiam
An argumentum ad verecundiam is an argument based on authority.
Fallacious because:

a.. Experts are often wrong. Perhaps less so than laypersons, but still so.

 

[Karl Heinz Buchegger]

http://c2.com/cgi/wiki?AdVerecundiam
An argumentum ad verecundiam is an argument based on authority.
Fallacious because:

a.. Experts are often wrong. Perhaps less so than laypersons, but still so.

For some small value of 'often'.
An expert can be wrong, 2 can be, 100 can be. But all the experts from
all over the world? Possible, but with a very small probability.
(And before you start with: "But first they didn't believe Einstein either"
For every idea the quality of Einsteins idea, there are millions which
just are crap.)

In any case: We don't need experts here. There is a proof. It is there
for everybody to see. It has been checked millions of time and be
considered to be correct. It starts with an assumption. From then
on every step follows logically and in a correct way from the
previous one until finally the functions as posted are derived.
Then those functions are analyzed and concluded that the functions
can not work the way they should. From this the conclusion is made,
that the assumption cannot hold.

 

[Peter Olcott]

Peter Olcott wrote:

For some small value of 'often'.
An expert can be wrong, 2 can be, 100 can be. But all the experts from
all over the world? Possible, but with a very small probability.
(And before you start with: "But first they didn't believe Einstein either"
For every idea the quality of Einsteins idea, there are millions which
just are crap.)

In any case: We don't need experts here. There is a proof. It is there
for everybody to see. It has been checked millions of time and be
considered to be correct. It starts with an assumption. From then
on every step follows logically and in a correct way from the
previous one until finally the functions as posted are derived.
Then those functions are analyzed and concluded that the functions
can not work the way they should. From this the conclusion is made,
that the assumption cannot hold.

Except that I have shown that its one and only basis does not hold
up in every case. Since its one and only basis does not hold up in
each and every case, the entire proof fails to proves its conclusion.

 

[Peter Olcott]

Statement A: Peter Olcott will never know that Statement A is true.



No. I did not think Turing's proof was correct (or incorrect) /until/ I
had studied it enough to be certain that I could not possibly refute it.
There is no circular reasoning in that.

In fact, at the time, I really didn't want Turing's proof to be correct.
But the more I tried to find a way around it, the more I tried to find
a flaw in it, the more I learned, and the more I realised just how
irrefutable it is.


No you haven't. You're just pretending that you have.

Simon

Turing contructed a paradox to show that creating a Halting Analyzer
is not possible.

If the halt analyzer simply refrains from ever providing its result to any
program that is being analyzed, then this paradox becomes completely
impossible to construct. That's exactly all that it takes, it takes nothing
at all more than this. It really is just as simple as that.

 

[Andrew Koenig]

Turing contructed a paradox to show that creating a Halting Analyzer
is not possible.

If the halt analyzer simply refrains from ever providing its result to any
program that is being analyzed, then this paradox becomes completely
impossible to construct. That's exactly all that it takes, it takes nothing
at all more than this. It really is just as simple as that.

If the program that claims to be a halt analyzer refrains from ever
providing its result to any program that is being analyzed, then the program
is not a halt analyzer. That's exactly all that it takes, it takes nothing
at all more than this. It really is just as simple as that.

 

[Marc Goodman]

Turing contructed a paradox to show that creating a Halting Analyzer
is not possible.

Exactly. He constructed a paradox using only a Halt
analyzer, an if statement and goto. One of these things
can't possibly exist. Is it the "if", the "goto" or the
Halt function? You be the judge.

If the halt analyzer simply refrains from ever providing its result to any
program that is being analyzed,

Then it has nothing to do with the case when it DOES return
its result to the program being analyzed.

then this paradox becomes completely

impossible to construct. That's exactly all that it takes, it takes nothing
at all more than this. It really is just as simple as that.

Once again, there are zillions of programs you can construct
that don't contain a paradox. That doesn't make it impossible
to construct a paradox, however. And, if you construct a
paradox, then either paradoxes are allowed or something you
used to construct the paradox isn't allowed. So, is it "goto",
"if" or the halt function?

 

[Buster]

If the halt analyzer simply refrains from ever providing its result to any
program that is being analyzed, then this paradox becomes completely
impossible to construct. That's exactly all that it takes, it takes nothing
at all more than this. It really is just as simple as that.

Assume (only) that your halt-analyser program exists. Starting with the
text of your program, mechanically make the obvious modifications to
obtain a real halt-analyser that returns its result in a form readable
by a containing program. Derive a contradiction as Turing showed.
Surprise! It wasn't impossible, after all.

Alan Turing died a cruel and miserable death. He had saved the lives of
many, many people. Do not deride him.

 

[Simon G Best]

Turing contructed a paradox to show that creating a Halting Analyzer
is not possible.

If the halt analyzer simply refrains from ever providing its result to any
program that is being analyzed, then this paradox becomes completely
impossible to construct. That's exactly all that it takes, it takes nothing
at all more than this. It really is just as simple as that.

Except that if a Turing Machine "simply refrains from ever providing its
result to any program that is being analyzed", it "simply refrains from
ever providing its result". This is obvious from the definition of a
Turing Machine, because a Turing Machine *does not know* who or what it
was that invoked it, and therefore *cannot* take that information into
account. Ignoring this does not refute it.

To understand this, do the following thought experiment:-

Imagine that you are a halt analyzer, WillHalt. You are given a tape
with the following source code and input on it:-

Source code:

bool LoopIfHalts(SourceCode s) {
if (WillHalt(s, s)) {
while(true); // Will loop forever.
return true;
else
return false;
}

Input:

bool LoopIfHalts(SourceCode s) {
if (WillHalt(s, s)) {
while(true); // Will loop forever.
return true;
else
return false;
}

***IMPORTANT:***
However, as WillHalt, you do not know who or what gave you this tape. It
might have been LoopIfHalts; or it might have been someone or something
else.

As a halt analyzer, you have to determine whether or not
LoopIfHalts(LoopIfHalts) would halt, and you have to be able to return
your result. If LoopIfHalts(LoopIfHalts) would halt, return 'true';
otherwise, if it would not halt, return 'false'.

What result, if any, do you return?

A: 'true'.

B: 'false'.

C: No result is returned.

D: A result is returned, but it is neither 'true' nor 'false'.

Bear in mind that, as WillHalt, you do not know whether or not you were
invoked by LoopIfHalts. As a Turing Machine, you simply do not know who
or what gave you that tape.

Simon

 

[George Greene]

: Turing contructed a paradox to show that creating a Halting Analyzer
: is not possible.

Right.

: If the halt analyzer simply refrains from ever providing its result to any
: program that is being analyzed,

This is NOT POSSIBLE.
The halt analyzer ALWAYS PROVIDES
a result, WHENEVER it is called.
BY DEFINITION. IT MUST ALWAYS PROVIDE A RESULT.
For a TM, "to provide a result" means "to halt".
ALL TMs, by definition, provide, as their result, whatever the contents of
their output tape is, when they halt. THE ONLY way in which ANY TM CAN EVER FAIL
to provide a result is by not halting.

: then this paradox becomes completely
: impossible to construct. That's exactly all that it takes, it takes nothing
: at all more than this. It really is just as simple as that.

Agreed that it takes nothing more than that.
The problem is, you can't HAVE even AS MUCH AS that.
Your "analyzer" (call it H), when IT gets called
with H(M,w), CANNOT KNOW "who" is calling it or
"who" it might be giving its result to. What H(M,w) is, and
indeed, what TM(s,d) is, for ANY TM with ANY two input parameters,
IS ALWAYS FULLY DETERMINED, WITHOUT any reference to "what program"
might be "calling" H or TM. And H, in particular, is DEFINED
as needing to work ON ALL programs with ALL input-strings.
So what you are talking about is just bullshit.

Maybe an analogy will help:
the usual arithmetic "plus" is, like H, a binary function of
2 arguments. 2+3=5. ALL THE TIME. You cannot say
"I'm talking about a + that refuses to return its result to
a program that gimbles". +(2,3) is *5*. ALWAYS. ALL THE TIME.
COMPLETELY IRRESPECTIVE of what "program" the "call to +" may
be occurring in. There is no way for + to "Withhold" its answer
because the wrong program wants to know.
ALL TURING MACHINES IN GENERAL ARE LIKE THAT.
THEY DO *NOT* *HAVE* CALLER-ID!

 

[George Greene]

: from the definition of a Turing Machine, because a Turing Machine
: *does not know* who or what it was that invoked it, and therefore
: *cannot* take that information into account.

I guess now Peter Olcott will say that the problem with
TMs is that they need to upgrade to a better service plan --
one that DOES have caller-ID.

 

[>parr\(*>]

|
| > Peter, you really should have a look at my post below. Do you
know
| > when argument from authority can be valid?
|
| Within deduction it is never valid.
| Only deduction can guarantee that it always provides correct
results. It is
| considered to be valid inductive inference, yet inductive inference
can not
| guarantee correct results. Deduction can not err, induction can
err.

Peter, part of me wants to suggest you do a basic maths course and
learn about proof by induction.

However, what you posted above is off topic (that means it has
nothing to do with Turing's proof (by diagonalisation) of his Halting
Problem conclusion).

Please get on topic.

Please, at the very least, make a start and go discover the title of
the Turing paper which you claim is in error.

 

[Peter Olcott]

|
| > Peter, you really should have a look at my post below. Do you
know
| > when argument from authority can be valid?
|
| Within deduction it is never valid.
| Only deduction can guarantee that it always provides correct
results. It is
| considered to be valid inductive inference, yet inductive inference
can not
| guarantee correct results. Deduction can not err, induction can
err.

Peter, part of me wants to suggest you do a basic maths course and
learn about proof by induction.

No, sorry. Mathematical induction (often used for proof of
algorithm correctness) has nothing at all in common with
inductive inference.

 

[Jerry Coffin]

[ ... ]

Within deduction it is never valid.
Only deduction can guarantee that it always provides correct results. It is
considered to be valid inductive inference, yet inductive inference can not
guarantee correct results. Deduction can not err, induction can err.

You should really quit while you're ahead -- or in this case, before
you get further behind.

An inductive proof can be just as much of a proof as a deductive
proof.

What you're (apparently) thinking of is not induction. Just to give an
example, I could look at a bunch of odd primes, and conclude from it
that all odd numbers are primes.

That's not induction though. In a real inductive proof, the first part
is usually fairly trivial: prove the result for the most trivial case
you can -- in the example above, I'd prove that 3 is prime. Then comes
the part that's usually harder: I have to prove that if it's true for
N, then it's also true for whatever's needed to generate the rest of
the applicable values. In the case above, I'd have to prove that for
any odd N, if N is prime then N+2 is also prime. Since I can't do
that, the inductive proof doesn't err.

 

[Jerry Coffin]

[ ... ]

Within deduction it is never valid.
Only deduction can guarantee that it always provides correct results. It is
considered to be valid inductive inference, yet inductive inference can not
guarantee correct results. Deduction can not err, induction can err.

You should really quit while you're ahead -- or in this case, before
you get further behind.

An inductive proof can be just as much of a proof as a deductive
proof.

What you're (apparently) thinking of is not induction. Just to give an
example, I could look at a bunch of odd primes, and conclude from it
that all odd numbers are primes.

That's not induction though. In a real inductive proof, the first part
is usually fairly trivial: prove the result for the most trivial case
you can -- in the example above, I'd prove that 3 is prime. Then comes
the part that's usually harder: I have to prove that if it's true for
N, then it's also true for whatever's needed to generate the rest of
the applicable values. In the case above, I'd have to prove that for
any odd N, if N is prime then N+2 is also prime. Since I can't do
that, the inductive proof doesn't err.

 

[>parr\(*>]

|
| No, sorry. Mathematical induction (often used for proof of
| algorithm correctness) has nothing at all in common with
| inductive inference.

No need to apologise. I see you're happy with that form of proof
(conclusion from stepping) as opposed to the other non-proof (jumping
to conclusions).

Anyway, that's not what this topic is all about.

It's more about your role as a latter-day Hilbert, believing that
finite algorithms may one day be found for all mathematical (and that
includes algorithmic) problems.

More precisely, it is more about your claim to have solved one
variety of Hilbert's 1928 Decision Problem.

Please get on topic.

Please, at the very least, make a start and go discover the title of
the Turing paper which you claim is in error.

 

[Peter Olcott]

[ ... ]

Within deduction it is never valid.
Only deduction can guarantee that it always provides correct results. It is
considered to be valid inductive inference, yet inductive inference can not
guarantee correct results. Deduction can not err, induction can err.

You should really quit while you're ahead -- or in this case, before
you get further behind.

An inductive proof can be just as much of a proof as a deductive
proof.

Logical induction depends upon a crucial assumption that might not be
true, whereas deduction does not.

What you're (apparently) thinking of is not induction. Just to give an
example, I could look at a bunch of odd primes, and conclude from it
that all odd numbers are primes.

Like I said mathematical induction is an entirely different process
than inductive inference. They just happen to share the same name.