P
Peter Olcott
Andrew Koenig said:
He claimed that no program can ever tell if any other program will
halt. In other words a program without any loops could not be
determined to halt.
He claimed that no program can ever tell if any other program will
halt. In other words a program without any loops could not be
determined to halt.
P
Peter Olcott
Will Twentyman said:
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.
A
Andrew Koenig
I don't see how this paragraph answers my question, so I will ask the
question again.
Here are two claims, taken from the first paragraph above:
1) A Halt Analyzer cannot ever exist.
2) Under certain weird circumstances, a Halt Analyzer will not produce
correct results.
I see no difference between these two claims. The first one says that there
is no such thing as a Halt Analyzer; the second one says that a program that
claims to be a Halt Analyzer isn't really such a thing, because sometimes it
doesn't work.
So as far as I can see, these two claims are equivalent, except for the
subjective adjective "weird."
Yet you are saying that you believe that the two claims are different.
Can you please explain, without recourse to what anyone might have said on
other occasions, why you think these two claims are different?
A
Andrew Koenig
Bad analogy. The problem is that you can determine in advance what the
cases are for which square root doesn't work
Here's a better analogy. I have a program that computes square roots,
except that for some input values, it gives incorrect results. There is no
way of determining in advance what those input values are--the best you can
do is to ask the program to take the square root, and then you get a result
that is either correct or it isn't.
In what sense can that be said to be a square root program? At best, it can
be said to be a program that sometimes computes square roots and sometimes
doesn't.
P
Peter Olcott
Andrew Koenig said:
You can tell the same thing with the Halting Problem, thus how
does the analogy fail?
P
Peter Olcott
Andrew Koenig said:
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.
T
The Ghost In The Machine
In sci.logic, Peter Olcott
<[email protected]>
wrote
Actually, it's possible to determine whether most programs halt,
using various heuristics. Just not all of them.
[rest snipped]
<[email protected]>
wrote
Actually, it's possible to determine whether most programs halt,
using various heuristics. Just not all of them.
[rest snipped]
P
Peter Olcott
Dave Vandervies said:
His claim was that a halt analyzer could not work for any possible
inputs.
N
newstome
In comp.theory Peter Olcott said:
??? What exactly do you mean here? Of course there are algorithms
that can determine if certain restricted classes of programs halt
(such as programs without any loops). But a solution to the halting
problem has to work for *ANY* input, meaning you don't get to
restrict the input like that -- it would have to work on any program
with loops as well. If there's even one input (program) that it
doesn't work for, then it's not a solution to the halting problem.
B
Bryan Olson
Peter said:
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.
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?
M
Marc Goodman
Peter said:
No one has made that claim in this thread. You have
misunderstood (again). The claim is and has always been
that you cannot construct a program WillHalt that
correctly determines for every program and input whether
or not that program will halt on that input. You have
now admitted as much yourself, and yet still don't seem
to realize that this is exactly what the proof of the
halting problem says, and only what it says.
I'm sorry you are having a challenge understanding what
people are saying to you. But, if you were more interested
in understanding why people believe what they do and
less interested in creating straw-men arguments or finding
non-existent loopholes, then perhaps you wouldn't find
reading comprehension so difficult.
S
stephen
: > > exists, there will be no weird circumstances.
:>
:> > 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.
:>
:> Bad analogy. The problem is that you can determine in advance what the
:> cases are for which square root doesn't work
: You can tell the same thing with the Halting Problem, thus how
: does the analogy fail?
How do you tell this for the Halting Problem? If your solution
says that a given program will loop for a given output how do you
verify this? Do you run it and wait forever to see if it does not halt?
If your solution says that a given program will halt, and you run
the program and it does not halt after 5 years, does that prove
your solution correct?
Stephen
:>
:> > 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.
:>
:> Bad analogy. The problem is that you can determine in advance what the
:> cases are for which square root doesn't work
: You can tell the same thing with the Halting Problem, thus how
: does the analogy fail?
How do you tell this for the Halting Problem? If your solution
says that a given program will loop for a given output how do you
verify this? Do you run it and wait forever to see if it does not halt?
If your solution says that a given program will halt, and you run
the program and it does not halt after 5 years, does that prove
your solution correct?
Stephen
S
stephen
: 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".
: 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.
Stephen
: > 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".
: 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.
Stephen
M
Marc Goodman
This is most likely the post that is causing Peter's
reading comprehension a challenge. Allow me to clarify:
By "any other" I mean "all," not "some."
Compare and contrast these two sentences:
"Any even integer is divisible by 2." - "Any" is used in the sense of
"For all X, if X is an even integer, then X is divisible by
2"
VS.
"Are there any schools that teach computer theory?" - "Any" is used
in the sense of "does X exist such that X is a school and
X teaches computer theory."
The meaning of the above sentence was:
"The proof of the halting problem most definitely does say that
a Turing Machine cannot exist that correctly decides whether
X halts, for all X, where X is a Turing Machine and input string."
I can't help but feel that if you understood the proof we were
talking about, this fairly simple point would not have caused
you such a difficulty. Or, are you _deliberately_ looking for
things to misunderstand in order to keep this discussion going?
reading comprehension a challenge. Allow me to clarify:
Marc said:
By "any other" I mean "all," not "some."
Compare and contrast these two sentences:
"Any even integer is divisible by 2." - "Any" is used in the sense of
"For all X, if X is an even integer, then X is divisible by
2"
VS.
"Are there any schools that teach computer theory?" - "Any" is used
in the sense of "does X exist such that X is a school and
X teaches computer theory."
The meaning of the above sentence was:
"The proof of the halting problem most definitely does say that
a Turing Machine cannot exist that correctly decides whether
X halts, for all X, where X is a Turing Machine and input string."
I can't help but feel that if you understood the proof we were
talking about, this fairly simple point would not have caused
you such a difficulty. Or, are you _deliberately_ looking for
things to misunderstand in order to keep this discussion going?
M
Marc Goodman
Dang, beat me to it
R
Robert Low
Peter Olcott said:
No, no single program can tell if an arbitrary program will halt;
obviously there are special cases that can be checked mechanically.
The point is that there is no single program that will work
on everything. Which you already conceded elsewhere.
R
Robert Low
Peter Olcott said:
My square root works fine on negative numbers; it
says the square root of -4 is 2i.
Of course, it doesn't work on the colour blue,
so I guess that proves you're right.
In case that was too subtle: an algorithm to
compute a function has to give the right
answer on every element of the domain of
the function. Saying it doesn't work on things
that aren't in the domain is very irrelevant.
The problem with any (okay, Turing Machine)
algorithm that purports to compute the halting
function is that it is guaranteed to give the
wrong answer on things that are in the domain
of the function.
A
Aatu Koskensilta
Peter said:
What tedious and amazing garbage you produce! One stands in awe.
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. 1. is
obviously false when Halt Analyzer is taken in your sense and obviously
correct when taken in the sense others would be more likely to use. In
fact, reading Halt Analyzer in 1. as "total solution to the Halting
Problem" and in 2. as "non-trivial partial solution to the Halting
Problem" would render them equivalent.
P
>parr\(*>
| Andrew Koenig:
| >
| > Bad analogy. The problem is that you can determine in advance
what the
| > cases are for which square root doesn't work
|
| You can tell the same thing with the Halting Problem, thus how
| does the analogy fail?
Peter, I do hope you are not trying to avoid pinpointing the
problem in Turings work by arguing about imaginary problems
with square root functions.
Peter, I do hope you are not avoiding completing your case under the
pretence of responding to your critics.
| >
| > Bad analogy. The problem is that you can determine in advance
what the
| > cases are for which square root doesn't work
|
| You can tell the same thing with the Halting Problem, thus how
| does the analogy fail?
Peter, I do hope you are not trying to avoid pinpointing the
problem in Turings work by arguing about imaginary problems
with square root functions.
Peter, I do hope you are not avoiding completing your case under the
pretence of responding to your critics.
K
Karl Heinz Buchegger
Peter said:
Because the square root function, as defined in C or C++, doesn't
attempt to compute the square root of everything. It is documented
that square root works for positive numbers (in the range speficied
for that implementation) and 0 only.
So square root (that is: the function sqrt()) is made workable by limting
itself to a subset of all mathematically possible square roots.
But this is not what the Halting problem is about. The Halting
problem is about an analyzer which works in *all* cases. Not
a subset, not 10 different algorithms, not 100, not 100000,
not 10000000000000000000000000000000. *ALL*
The difference is like in the famous Fermat theorem: There
is no solution in the whole numbers of
n n n
a + b = c
for n > 2
A few years ago the theorem had been proven only for n = 3, n = 4,
n = 5, up to n = 10000 (if not higher). But that is not the same
as saying for *all* n, no matter what n may be. (And finally
a proof was found for *all* n.)