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
.



Relevant Pages

  • Re: Proving a negative is hard
    ... a MATHEMATICAL function that is partial is MULTIPLICATIVE INVERSE. ... it does NOT SATISFY the semantic criteria we agreed to for it, ... function WE were talking about MUST FAIL to return a defined value when the ... undefined whether it does or doesn't halt on some input w. ...
    (sci.logic)
  • Re: What is the Result from Invoking this Halt Function?
    ... a MATHEMATICAL function that is partial is MULTIPLICATIVE INVERSE. ... it does NOT SATISFY the semantic criteria we agreed to for it, ... function WE were talking about MUST FAIL to return a defined value when the ... undefined whether it does or doesn't halt on some input w. ...
    (sci.logic)
  • Re: Halting Problem Final Conclusion
    ... > was to detect programs that failed to halt, ... The primary benefit of a universal Halting Problem ... about programs that fail to halt. ... if this program would halt" analyzer may be as ...
    (comp.theory)
  • Re: Halting Problem Final Conclusion
    ... > was to detect programs that failed to halt, ... The primary benefit of a universal Halting Problem ... about programs that fail to halt. ... if this program would halt" analyzer may be as ...
    (sci.logic)
  • Re: Alan Turings Halting Problem is incorrectly formed (PART-TWO)
    ... I am referring to the specific counter-example test case that the Halt() ... Specifically because the Haltfunction must fail this test case, ... the Halting Problem asserts that determining whether or not ... any program will halt is necessarily incomplete. ...
    (sci.logic)