Re: Yet another Attempt at Disproving the Halting Problem

[Peter Olcott]

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

It might only apply to TM's. The other things derived from the
original Halting Problem might remain unchanged.

 

[Peter Olcott]

Mathematical induction and inductive inference are entirely different things.

[ ... ]

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.

--
Later,
Jerry.

The universe is a figment of its own imagination.

 

[Jerry Coffin]

Mathematical induction and inductive inference are entirely different things.

Induction is induction. Apparently, you're simply talking about
"guessing" and dressing it up with a fancy-sounding name, so people
won't realize how obvious a statement you're making when you say that
guesses can be wrong!

In the end, however, picking fancy words and such won't show anything
about the original topic of conversation.

 

[Robert Low]

Induction is induction. Apparently, you're simply talking about
"guessing" and dressing it up with a fancy-sounding name, so people
won't realize how obvious a statement you're making when you say that
guesses can be wrong!

"Induction" is often used to mean the process of inferring
a general rule of principle from a collection of observations.
Clearly, this form of induction does not generally work
reliably. Yes, "guessing", or to be slightly fairer, "informed
guessing" is what that kind of induction is.

The proof technique we all know and love for proving that
some property holds of all integers is sometimes called
"mathematical induction" simply to distinguish it from
what is more generally meant. Also, it is nicer because
it works Mathematicians rarely bother to call
it "mathematical induction": the reason for this is
left as an exercise for the reader.

 

[Peter Olcott]

NOT!
http://dictionary.reference.com/search?q=logical induction

 

[Peter Olcott]

"Induction" is often used to mean the process of inferring
a general rule of principle from a collection of observations.
Clearly, this form of induction does not generally work
reliably. Yes, "guessing", or to be slightly fairer, "informed
guessing" is what that kind of induction is.

It works with far greater consistency than random guessing.
Thus it can be said to work reliably. That daytime will ever
occur again can only be known by inductive inference.

 

[Will Twentyman]

It works with far greater consistency than random guessing.
Thus it can be said to work reliably. That daytime will ever
occur again can only be known by inductive inference.

As long as you understand that it does not count as mathematical proof.
For example, just because you can determine whether a function will
halt for every one you've seen does not mean you can do so for *all*
functions.

 

[Peter Olcott]

As long as you understand that it does not count as mathematical proof.
For example, just because you can determine whether a function will
halt for every one you've seen does not mean you can do so for *all*
functions.

Just because I have refuted the original basis for the proof that the
halting Problem can't be solved, only means that I have refuted
the Halting Problem's proof.

 

[Karl Heinz Buchegger]

Just because I have refuted the original basis for the proof that the
halting Problem can't be solved, only means that I have refuted
the Halting Problem's proof.

No.
Just because you *think* you have refuted the original basis for the
proof, it does not mean that you actually *have* refuted the original
basis for the proof.

 

[Peter Olcott]

No.
Just because you *think* you have refuted the original basis for the
proof, it does not mean that you actually *have* refuted the original
basis for the proof.

This is exactly and precisely what I have done:

Quick Summary:
Alan Turing conclusively proved is that it is impossible to construct a halt
analyzer that always returns a correct result back to the program being analyzed.

Since returning the result back to the program being analyzed is not the only
way to construct a halt analyzer, his proof did not show that constructing a
halt analyzer that works correctly for all input is impossible.

I am still studyng the original proof.

 

[Will Twentyman]

This is exactly and precisely what I have done:

Quick Summary:
Alan Turing conclusively proved is that it is impossible to construct a halt
analyzer that always returns a correct result back to the program being analyzed.

Since returning the result back to the program being analyzed is not the only
way to construct a halt analyzer, his proof did not show that constructing a
halt analyzer that works correctly for all input is impossible.

I am still studyng the original proof.

Start by studying the definitions. Once you do that you will understand
that what you wrote above is nonsense. The definitions are not open to
discussion. In particular, how the halt analyzer returns its result is
not open to discussion.

At this point, you have a few options, including not posting to
sci.logic since you don't seem to understand what a definition is.

 

[Karl Heinz Buchegger]

This is exactly and precisely what I have done:

Quick Summary:
Alan Turing conclusively proved is that it is impossible to construct a halt
analyzer that always returns a correct result back to the program being analyzed.

Since returning the result back to the program being analyzed is not the only
way to construct a halt analyzer, his proof did not show that constructing a
halt analyzer that works correctly for all input is impossible.

What you have done is analogous to:

Question: Is it possible for a human beeing to survive a free fall in
any and all instances?
Answer: No
Proof: Nobody can survive a free fall from a height of 100 meters.
Olcott: But I refuse to jump from that height and thus I have proofen
that a human beeing can survive any and all free falls.

 

[Daryl McCullough]

Peter Olcott says...

Quick Summary:
Alan Turing conclusively proved is that it is impossible to construct a halt
analyzer that always returns a correct result back to the program being
analyzed.

Since returning the result back to the program being analyzed is not the only
way to construct a halt analyzer, his proof did not show that constructing a
halt analyzer that works correctly for all input is impossible.

Turing *defined* what he meant by a "solution to the halting problem"
and by that definition, there *is* no solution. You are proposing a
*different* definition. Turing's proof does not *directly* apply to
your new definition. You haven't refuted Turing, you've changed the
subject.

Now, if you want to introduce a broader notion of what it means to
"solve the halting problem", you are free to do so. If you could somehow
show that it is solvable in this broader sense, you *wouldn't* have
refuted Turing, because Turing was talking about a *different* sense
of "solvable". So even if you were right, your arguments wouldn't
constitute a refutation of Turing.

As to the question of whether the halting problem is solvable in a
broader sense, that's where Church's thesis comes in. Church conjectured
(he didn't prove, because there is no way to rigorously prove a claim
that involves the intuitive meanings of words) that any problem that
is computable in a broader sense of "computable" is computable by
Turing machines (or in the lambda calculus, or in Godel's theory of
partial recursive functions, etc.)

So, if you managed to solve the halting problem in a way that could
*not* be translated into Turing's notion of solvable, then you would
be disproving Church's thesis, not Turing's proof of the unsolvability
of the halting problem.

Of course, you haven't given anything whatsoever that shows any
hope of solving the halting problem. What you've been concentrating
on is trying to defeat the *proof* that a program doesn't solve
the halting problem. That is a completely nonsensical approach.

It's as if I claim that there are no pink elephants. You note that to
demonstrate that an elephant is not pink, I must turn on the
light. So your approach to producing a pink elephant is to build a dark
building with no lights, and to confiscate any candles or
flashlights that anyone takes into the building. That way, nobody
can prove that you don't have a pink elephant.

The way to prove that a program is not a solution to the halting
problem is to run it on some tough cases, in some special circumstances.
If you somehow arrange things so that your program refuses to answer
in a circumstance in which its answer could be used against it, then
you have defeated the proof that it is not a solution to the halting
problem. But that doesn't mean that you have solved the halting problem,
any more than having an elephant in a dark room is a proof that you
have a pink elephant.

You're using the tricks of a professional psychic --- if someone attempts
to actually *test* whether the psychic has psychic abilities, the psychic
claims that "Oh, my abilities don't work in the presence of cynics and
doubters". If that's the psychic's claim, then there is, indeed, no
way to prove that the psychic is a fraud. But you would strongly suspect
it.

Peter, you are a fraud of the exact same kind.

 

[>parr\(*>]

| Olcott: But I refuse to jump from that height
| and thus I have proofen
| that a human beeing can survive any
| and all free falls.

Hi Karl, how about giving him a push?
BTW, why not stop all responses from midnight tonight?

 

[Chris Menzel]

This is exactly and precisely what I have done:

Quick Summary:
Alan Turing conclusively proved is that it is impossible to construct a halt
analyzer[.]

Stop right there and you've got it.

 

[George Greene]

(e-mail address removed) (Daryl McCullough) writes:
: You're using the tricks of a professional psychic --- if someone attempts
: to actually *test* whether the psychic has psychic abilities, the psychic
: claims that "Oh, my abilities don't work in the presence of cynics and
: doubters". If that's the psychic's claim, then there is, indeed, no
: way to prove that the psychic is a fraud. But you would strongly suspect
: it.
:
: Peter, you are a fraud of the exact same kind.

I don't agree. PO is nowhere near smart enough to be any kind of fraud
or use any kinds of tricks. He instead prefers to talk about a "Halt
analyzer". That is not a trick; it is just blatant hubris and megalomania.
The original proof talked about A TURING MACHINE, not an "analyzer".
If he ever manages to figure out that he is obligated to design A TURING
MACHINE, as OPPOSED to an "analyzer", in order to even participate in the
discussion, then the battle will be half-won. The other half will involve
convincing him that TMs don't do have thigs like "calling", "security",\
"process", caller-ID, ad nauseam.

 

[David C. Ullrich]

[...]

It's as if I claim that there are no pink elephants. You note that to
demonstrate that an elephant is not pink, I must turn on the
light. So your approach to producing a pink elephant is to build a dark
building with no lights, and to confiscate any candles or
flashlights that anyone takes into the building. That way, nobody
can prove that you don't have a pink elephant.

precisely. [and also precisely why i don't understand why people
debate whether the silly things he suggests are possible or legal -
it's so obvious that 'not returning the result' can't possibly
-help-...]



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

David C. Ullrich

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

 

[Kenneth Doyle]

(e-mail address removed) (Daryl McCullough) wrote in

Now, if you want to introduce a broader notion of what it means to
"solve the halting problem", you are free to do so. If you could somehow
show that it is solvable in this broader sense, you *wouldn't* have
refuted Turing, because Turing was talking about a *different* sense
of "solvable". So even if you were right, your arguments wouldn't
constitute a refutation of Turing.

Let's not give him false hope. Even if he manages to refute Turing, which
he can't because the proof works, then he would "not" have solved the
halting problem. Refuting Turing's proof would mean that the halting
problem is exactly the problem it was before Turing's proof.

 

[Peter Olcott]

[...]

It's as if I claim that there are no pink elephants. You note that to
demonstrate that an elephant is not pink, I must turn on the
light. So your approach to producing a pink elephant is to build a dark
building with no lights, and to confiscate any candles or
flashlights that anyone takes into the building. That way, nobody
can prove that you don't have a pink elephant.

precisely. [and also precisely why i don't understand why people
debate whether the silly things he suggests are possible or legal -
it's so obvious that 'not returning the result' can't possibly
-help-...]

Yup it is completely obvious to anyone whom has not thought it through
at all. You will come to this same conclusion iff you ever attempt to
prove the prior baseless assertion bereft of supporting reasoning.
BABOSR

 

[Peter Olcott]

Peter Olcott says...


Turing *defined* what he meant by a "solution to the halting problem"
and by that definition, there *is* no solution. You are proposing a

Halting Problem according to Alan Turing:
The problem of finding out whether a given number is the D.N of a
circle-free machine,

Translation: (The problem of finding out whether a given Turing Machine
Description specifies a Turing Machine that fails to Halt).

I have refuted any existing proof that the above is impossible.