Re: Yet another Attempt at Disproving the Halting Problem

[Will Twentyman]

First of all this is flatly incorrect. The Halting Problem does not
say that a Halt Analyzer can not ever exist. All that it says is that
under certain weird circumstances it would not produce the correct
results. I will wait and see if you can get past that before I proceed.

If it is not producing correct results, then it does not exist as
described. If I told you I had a function that returns the square of an
integer, except for this one weird case where it says that the square of
13 is 12, then it is not a squaring function. If the Halt Analyzer
exists, there will be no weird circumstances.

 

[Andrew Koenig]

First of all this is flatly incorrect. The Halting Problem does not
say that a Halt Analyzer can not ever exist. All that it says is that
under certain weird circumstances it would not produce the correct
results.

I see no difference between these two claims. Would you explain what you
mean, please?

Putting it differently: If by the term "Halt Analyzer" you mean a program
that can inspect an arbitrary program and say correctly whether that program
will halt when presented with particular input, then either that "Halt
Analyzer" program works correctly in all cases or it gives incorrect results
in some cases. If it gives incorrect results in some cases, then in what
sense can it be said to be a "Halt Analyzer"?

Using the term "weird" to describe the cases in which it gives incorrect
results is a matter of opinion. Are you saying that it is possible to write
a program that determines whether any program will halt except for programs
that you consider weird? If so, why should anyone but you be interested in
such a claim?

 

[Jerry Coffin]

[ ... ]

If one program is made to function incorrectly, then can we
conclude that every program *that returns the same results as
the incorrect program when given the same inputs* always
functions incorrectly?

The answer to this question is obviously yes: A program that produces
the same results as a broken program is broken.

That's not necessarily true: the basic definition of a real-time
program is that its correctness depends not only on producing correct
results, but on doing so in a timely manner. As such, in the real-time
domain, it's entirely possible for two programs to produce identical
results, but even so one is correct, and the other is not.

 

[Chris Menzel]

First of all this is flatly incorrect. The Halting Problem does not
say that a Halt Analyzer can not ever exist.

That is *exactly* what the Halting Problem (or better, the theorem that
it is unsolvable) says, if, by a "halt analyzer" you mean a Turing
machine that can correctly determine whether any given TM halts on any
given input.

All that it says is that under certain weird circumstances it would
not produce the correct results.

And hence wouldn't be a halt analyzer. Congratulations. You just gave
a nice little sketch of the proof that the Halting Problem is
unsolvable. You're almost there.

-cm

 

[Andrew Koenig]

"Andrew Koenig" <[email protected]> wrote in message

That's not necessarily true: the basic definition of a real-time
program is that its correctness depends not only on producing correct
results, but on doing so in a timely manner. As such, in the real-time
domain, it's entirely possible for two programs to produce identical
results, but even so one is correct, and the other is not.

In a real-time environment, timing is part of a program's output.

 

[Kent Paul Dolan]

First of all this is flatly incorrect. The Halting
Problem does not say that a Halt Analyzer can not
ever exist. All that it says is that under certain
weird circumstances it would not produce the
correct results. I will wait and see if you can
get past that before I proceed.

Where do you dig up this endless stream of garbage
you try to pass off as "fact"?

"The Halting Problem" "says" no such thing.

It simply posts the challenge of creating a single,
well-defined Turing machine that will accept a
description of another Turing machine, and a
description of that other Turing machine's input
data, for _every_ possible Turing machine and _every
possible_ set of input data, and then _always_
correctly decides "yes, this case of Turing machine
and input data will halt" or "no, this case of
Turing machine and input data will not halt",
without itself going into an endless loop before
producing one or the other of those two results.

Nowhere in there do we read about "weird cases";
the requirement is that the Machine that Solves the
Halting Problem work for _every_ case, no exceptions
allowed. Specifically this includes cases in which
it is given itself as a subset of a Turing machine
description, and that embedding of itself as its own
input data.

Here is an exposition which defines all the needed
terms, in a way requiring only junior high school
algebra to comprehend, and defines the Halting
Problem using those terms. Any self-described
"genius" and "professional programmer" should be
able to eat this stuff like candy.

You, I'm convinced, will choke on it, but go read it
anyway, it will reduce your idiot-quotient. If it
does result in your demise, you sure won't be missed
by the flocks of your supporters ("flock, flock, has
anybody seen Peter's flock?") here.

Come back when, and only when, you can write without
writing consistent utter nonsense.

http://www.csc.liv.ac.uk/~ped/teachadmin/algor/comput.html

xanthian.

 

[Robert Low]

First of all this is flatly incorrect. The Halting Problem does not
say that a Halt Analyzer can not ever exist. All that it says is that

Second of all, this is flat out crazy. Assuming (in order for
it to even try to make sense) that you mean 'the proof that
the halting problem is uncomputable' when you write 'the
Halting Problem', the proof shows that there *is no algorithm
for determining whether an arbitrary algorithm will halt on
an arbitrary data set'.

under certain weird circumstances it would not produce the correct
results.

And in any case, if everything that thinks it is a Halt Analyser
gives the wrong answer on some inputs, that kind of means that
there isn't a Halt Analyser---because a Halt Analyser, by definition,
always produces the correct results.

I will wait and see if you can get past that before I proceed.

Ipse dixit.

 

[Mitch Harris]

The Halting Problem does not
say that a Halt Analyzer can not ever exist. All that it says is that
under certain weird circumstances it would not produce the correct
results. I will wait and see if you can get past that before I proceed.

To add to the others, for a theorem "forall x P(x)" to be
true, P(x) must be true for -all- possible x. Not just most,
not just everything but one, it must work for -all-.

"All primes are odd" is not a theorem because it fails for
2. "There is a TM that determines if every TM halts on given
input" is not a theorem because there is at least one TM for
which any proposed solution will fail to determine halting.

So your questioning of Turing's theorem and/or proof are
very reasonable, in the sense that it is trying to find out
more about this halting phenomenon. First, we know that the
halting problem is unsolvable, but now what? Are there
reasonable subsets of TMs that do have a solvable halting
problem? Can you approximate (guess really well) if a TM
halts? Are there other problems that are unsolvable?

 

[Aatu Koskensilta]

"There is a TM that determines if every TM halts on given
input" is not a theorem because there is at least one TM for
which any proposed solution will fail to determine halting.

This isn't true. There is no TM which every proposed solution fails to
determine the halting of. Rather, for every TM M there is a TM E_M and
input x, for which M does not correctly determine the halting.

 

[Marc Goodman]

First of all this is flatly incorrect. The Halting Problem does not
say that a Halt Analyzer can not ever exist.

Yes it does. It most definitely does say that a Turing Machine
that correctly decides whether any other Turing Machine and
input string correctly halts cannot exist. Learn the proof.

All that it says is that

under certain weird circumstances it would not produce the correct
results.

No it doesn't. Read. Learn. Understand. Evolve.

I will wait and see if you can get past that before I proceed.

 

[Karl Heinz Buchegger]

[snip]
Are there other problems that are unsolvable?

Woman: "What should I wear today?"

 

[Mitch Harris]

This isn't true. There is no TM which every proposed solution fails to
determine the halting of. Rather, for every TM M there is a TM E_M and
input x, for which M does not correctly determine the halting.

Yes. I spoke badly. I was trying too hard to make the
analogy simple (matching quantifiers to quantifiers, etc.)

 

[Peter Olcott]

This isn't true. There is no TM which every proposed solution fails to
determine the halting of. Rather, for every TM M there is a TM E_M and
input x, for which M does not correctly determine the halting.

But the proof only shows that TM E_M and input x does not correctly
determine halting for itself. TM M can determine if TM E_M halts on x.
All that is has to do is to see that it will not make either of the transitions
to the (it does halt) and (it does not halt) final states. Since neither of these
transitions would be defined for the transition function (in this case) we
would know that TM E_M would halt on x.

 

[Dave Vandervies]

Second of all, this is flat out crazy. Assuming (in order for
it to even try to make sense) that you mean 'the proof that
the halting problem is uncomputable' when you write 'the
Halting Problem', the proof shows that there *is no algorithm
for determining whether an arbitrary algorithm will halt on
an arbitrary data set'.

More precisely, there is no algorithm implementable using a turing-
equivalent model of computation that can determine whether an arbitrary
algorithm implementable using a turing-equivalent model of computation
will halt on an arbitrary data set.

(This doesn't actually make the statement any weaker; algorithms that
require a model of computation more powerful than a turing machine
aren't interesting unless you have an appropriate more powerful model
of computation to show us, and nobody seems to have managed that yet.)


dave

 

[Chris Menzel]

More precisely, there is no algorithm implementable using a turing-
equivalent model of computation that can determine whether an arbitrary
algorithm implementable using a turing-equivalent model of computation
will halt on an arbitrary data set.

Alternatively, just prefix Low's version with "Assuming Church's
Thesis...". ;-)

-cm

 

[Aatu Koskensilta]

But the proof only shows that TM E_M and input x does not correctly
determine halting for itself. TM M can determine if TM E_M halts on x.

No. The proof shows that *M* can not correctly decide whether E_M halts
on input <E_M> or not, where <E_M> is the encoding for E_M. The
capabilities of E_M to decide the halting or non-halting of any machine
are entirely irrelevant.

 

[Anonymous]

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!

 

[Peter Olcott]

More precisely, there is no algorithm implementable using a turing-
equivalent model of computation that can determine whether an arbitrary
algorithm implementable using a turing-equivalent model of computation
will halt on an arbitrary data set.

(This doesn't actually make the statement any weaker; algorithms that
require a model of computation more powerful than a turing machine
aren't interesting unless you have an appropriate more powerful model
of computation to show us, and nobody seems to have managed that yet.)


dave

Yet this is not at all what the respondent had claimed. It is not at
all true that no halt analyzer can possibly exist. The Halting Problem
does not say that. The most that the Halting Problem says is that
this Halt analyzer won't work correctly in every possible instance.

 

[Dave Vandervies]

Yet this is not at all what the respondent had claimed. It is not at
all true that no halt analyzer can possibly exist. The Halting Problem
does not say that. The most that the Halting Problem says is that
this Halt analyzer won't work correctly in every possible instance.

How, exactly, is saying that a halt analyzer that works correctly for
all possible inputs cannot exist different from saying that any halt
analyzer that can exist won't work correctly for all possible inputs?


dave

 

[Peter Olcott]

Yes it does. It most definitely does say that a Turing Machine
that correctly decides whether any other Turing Machine and
input string correctly halts cannot exist. Learn the proof.

That is not what the respondant claimed. He claimed that it
could not possibly determine if any program halts, not all
programs, but, any one program.