Re: Olcott is cured of CrackPottery! (Halting Problem)

From: Mike Oliver (mike_lists_at_verizon.net)
Date: 09/24/04 

Date: Fri, 24 Sep 2004 10:24:22 -0500

Robert Low wrote:
> Charlie-Boo <chvol@aol.com> wrote:
>
>>3. Incomplete or inconsistent specs.
>>Come to think of it, the halting problem (and Godel's Incompleteness
>>Theorem et. al.) is just a case of # 3. Ho hum.
>
>
> Except, of course, that it isn't. The specification "f is a
> function which takes a TM description and an input tape, and
> returns 1 if the TM halts on the input and 0 if it does
> not" is neither incomplete nor inconsistent. It just happens
> to be a function that cannot be computed by a TM. Proving
> that is not so "ho hum" (though it's easy once you know the
> answer, of course).

To be fair to Charlie-Boo--though I hardly see the need,
beyond the sheer mental exercise of the thing--the spec *is*
inconsistent--if you add the requirement that the function
must be computed on a TM.

Relevant Pages