Re: The Halting Problem is merely an erroneously formed question



On 2/11/2012 7:34 AM, Peter Olcott wrote:
guess (From Dictionary.com, the first therefore most commonly understood
meaning)

I haven't seen that sight in a long term, but my recollection is that most dictionaries relegate terms as they are used in specific fields to the end of the list. I gave you the term as it is typically used in the context of computability theory; this is not necessarily the same as it is used in the context of everyday speech.

This may be occurring when it is precisely defined exactly what it means
when it says that a fictional machine must halt or fail to halt. When
one gets a little more literally precise one knows that fictional
machines (because they are fictional) neither halt nor fail to halt.

Halting is well-defined for these fictional machines. A fictional machine represents a sequence of discrete computable steps which can include steps like conditionals (do this if that) and loops (while this is true do that). If this sequence comes to an end, the machine halts; if it does not, it fails to halt. I just defined it for you.

Saying that the machines neither halt nor fail to halt because halting is not applicable to a fictional machine is again erring in that you are attempting to apply colloquial definitions into a field where the terminology has a more precise, specific definition which does not fully correlate to the colloquial case.

The Halting Problem and the Liar Paradox have the same form, thus if one
is a paradox then the other one is too.

The first asks if it is possible to construct an algorithm that can determine whether or not a machine would halt if presented with a given output; the latter is a statement which arrives at a paradox by means of self-reference. The only thing I can POSSIBLY see that causes them to have the same form is that the proof that the halting problem is nonconstructable is done via proof by contradiction; logical extension of this reasoning is that all proofs by contradiction are paradoxes.

--
Beware of bugs in the above code; I have only proved it correct, not tried it. -- Donald E. Knuth
.