The old Google Groups will be going away soon, but your browser is incompatible with the new version.
Message from discussion Proof that Decidability is Always Decidable

From:
To:
Cc:
Followup To:
Subject:
 Validation: For verification purposes please type the characters you see in the picture below or the numbers you hear by clicking the accessibility icon.

More options Apr 20 2012, 1:32 pm
Newsgroups: comp.theory, sci.logic
From: Peter Olcott <NoS...@OCR4Screen.com>
Date: Fri, 20 Apr 2012 12:32:53 -0500
Local: Fri, Apr 20 2012 1:32 pm
Subject: Re: Proof that Decidability is Always Decidable
On 4/20/2012 7:22 AM, Jussi Piitulainen wrote:

> Peter Olcott writes:
>> On 4/20/2012 12:30 AM, Jussi Piitulainen wrote:
>>> Peter Olcott writes:
>>>> On 4/19/2012 10:02 PM, Rick Decker wrote:
>>>>> <sigh>  Just for fun, I'll weigh in on this. This is most
>>>>> emphatically a decidable problem. Exactly one of two deciders is
>>>>> clearly the right one:

>>>>> The fact that we don't know which one is correct has no bearing
>>>>> on the decidability of the problem. The fact that there _is_ a
>>>>> decider is all that we're concerned with. I know that this may
>>>>> strike some people as an unsatisfactory answer, but you just
>>>>> have to live with it. The definition of a decidable problem (or
>>>>> language, if you will) is that there is _some_ algorithm that
>>>>> produces a correct answer to the question. The fact that we
>>>>> might not know which one is correct is by definition immaterial.

>>>>> Regards,

>>>>> Rick
>>>> That reasoning seems correct to me.
>>> Yet you will continue to insist that there are _individual
>>> instances_ of the halting problem that may not be decidable. And
>>> that apart from these undecidable instances the halting problem is
>>> decidable, in the sense _you_ have been using the word.
> [description snipped]

>> If this is *not* an undecidable instance then what element of the
>> set {true, false} can the invocation of Halts(M, M) correctly
>> return?
> [description of why both true and false would be incorrect snipped]

>> (3) This only leaves neither true nor false. I am calling this
>> undecidable. What else can it be called?
> Oh, many things. Bad, erroneous, other, neither, third, unfair,
> confusing, frustrating, paradoxical, particular, mysterious,
> the prefix Halts- for the machine that cannot give the correct answer.

> You need not be stuck with the one word that already has a very
> different meaning in the context where you want to discuss your ideas.
> People keep telling you it has. There are words to choose from.

> Yes, no, maybe. True, false, sorry. Halts, halts not, mu.

> The question remains, is the third answer interesting. And is the
> three-valued thing implementable.

>>> When a Turing machine is run an encoding of itself as a string,
>>> one of Rick's two deciders tells whether it will halt. Do you now
>>> accept this?
>> No for the reasons stated above.
> I knew you would.