|
|
On Oct 30, 5:10 am, sillyban...@xxxxxxxxx wrote:
> In comp.theory Peter Olcott <NoS...@xxxxxxxxxxxxx> wrote:
>
>
>
> > <sillyban...@xxxxxxxxx> wrote in messagenews:bvn0h.3952$GJ.424@xxxxxxxxxxx
> > > In comp.theory Peter Olcott <NoS...@xxxxxxxxxxxxx> wrote:
>
> > >> Using the term [decidable] in this context is like using {dead} as a
> > >> valid sense meaning for [illness]. Even if it does correspond to
> > >> accepted usage conventions, it is still an error.
>
> > >> How can anything possibly be decidable or undecidable if there is no
> > >> decision involved?
>
> > > 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. This specific instance of the problem (this
> > > program/input pair) is decided by giving a yes/no answer. The problem
> > > (which means *all* such inputs) 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."
> > At least in the case of the LoopIfHalts() variation it can be seen
> > that this decision can be made. It is decidable, the answer is that
> > LoopIfHalts(LoopIfHalts)) will halt. It will specifically halt
> > because WillHalt() will refrain from returning the value of TRUE. It
> > will refrain from returning the value of TRUE, because WillHalt()
> > can see that TRUE provides an incorrect answer in this case.
> > The only reason that it seems to be undecidable is not because it is
> > actually undecidable, but, because WillHalt() is restricted to
> > providing its answer in the form of a specific machine state. The
> > outermost WillHalt() will correctly determine that
> > LoopIfHalts(LoopIfHalts) will halt. It can know that it is the
> > outermost WillHalt() because it specifically uses whatever decision
> > protocol that LoopIfHalts() is unprepared for.You still don't seem to
> > understand what "undecidable" means. It's
> irrelevant what LoopIfHalts() or WillHalt() do. It makes absolutely
> no sense to talk about the "decidability" of one particular input
> (like "LoopIfHalts(LoopIfHalts)").
>
> If you're interested in the answer on one particular input (or any
> finite set of inputs for that matter), then it's ALWAYS decidable. It
> doesn't even matter what the question is (assuming that it's a
> complete function anyway!) - any question on a finite domain is
> decidable.
>
> So to talk about what "LoopIfHalts" does on this particular input and
> talk about this particular decision being "decidable" and
> "undecidable" based on that is nonsense.
>
Say, we set up a halting problem such that a TM halts if a
counterexample to Goldbach's conjecture is found, and does not halt
otherwise. So is the proposition that this TM halts decidable? Sure, if
we have one program asserting "Yes" and the other "No", one of these
two decides the proposition. But really all that is said here is that
the TM halts or not halts, but we do not know which. That is not
"deciding" the problem, from the NAFL point of view -- if you want to
assert that the TM either halts or not halts, you must *in principle*
be able to say *which* of the two is the case, via a proof -- this is a
logical requirement, because you cannot assert the law of the excluded
middle ("halts or not halts") in NAFL without being able to say which
of the two mutually exclusive possibilities is the case. If the halting
problem is undecidable, it must also be undecidable in at least one
such instance in this sense (which is the same as saying that there
must exist undecidable propositions of arithmetic, say PA). For
otherwise we can decide the halting problem by enumerating all proofs
of PA. The existence of such an enumeration is required by classical
first-order logic.
Regards, RS
|
|