|
|
sillybanter@xxxxxxxxx wrote:
> Of course there's a decision involved. Given a program and an input,
> DECIDE whether the program, when run on that input, halts in a finite
> number of steps.
But for any individual question, where there is in fact a factual
answer
to be discovered, this is ALWAYS possible. Therefore, no INDIVIDUAL
question CAN EVER be undecidable. Indeed, no finite collection of
questions can be undecidable. This is ENTIRELY COUNTER-
intuitive.
> This specific instance of the problem
But THAT is the WHOLE point. The "problem"/instance dichotomy
IS THE WHOLE point. This is a NON-natural concept. This is a
concept of which people outside this field are NOT aware. THIS
IS A TECHNICAL as OPPOSED to natural-language
use of the term "problem". In Real Life, people think they
have individual or finite collections of problems ALL THE TIME.
The fact that a problem HAS to be an INFINITE family of instances
IS NOT generally known. That's one of the things people could LEARN
by coming here IF they came ABLE to learn instead of trying to tell all
of us how stupid Cantor and Godel were.
> (this program/input pair) is decided by giving a yes/no answer.
> The problem (which means *all* such inputs)
THAT'S the point: "The problem" does NOT mean "all such inputs",
naturally, to the uninitiated. That is precisely why you saw PO trying
to reduce the problem to the individual instance of
LoopIfHalts(LoopIfHalts),
and stumbling over the question of whether THAT ONE INSTANCE was
undecidable. The single instance is ALWAYS decidable; EVERY tm either
halts or loops on EVERY input, so the TRUE answer is ALWAYS yes or no,
so EITHER of the-TM-that-always-answers-Yes or
the-TM-that-always-answers-No is guaranteed to decide the single
instance
correctly; even if you don't know which it is, both of them exist, so
one that
decides it correctly exists. THAT was what PO needed explained to him.
But that was long ago.
> is decided if an algorithm can decide
> each instance correctly. I fail to see how this is in any conflict
> with standard English usage of the term "decide."
Please. You yourself just used "decide" with two different usages
IN THE SAME SENTENCE, one for the individual instance, and the
other for the infinite family. Obviously, our use about the infinite
family conflicts with standard English usage. Standard English usage
of "problem" does not entail that problems have to be infinite
families.
The point is that this is OUR room and you have to either use OUR
definitions,
or ones that you define LOGICALLY. In NEITHER case do you just get to
use
the ones you think are common sense.
|
|