Re: The Halting Problem is merely an erroneously formed question



Peter Olcott wrote:
On 2/10/2012 4:01 PM, Joshua Cranmer wrote:
On 2/10/2012 12:28 PM, Peter Olcott wrote:
On 2/10/2012 11:58 AM, Joshua Cranmer wrote:
A machine must either halt or fail to halt (i.e., run forever). So
there is no case in which there is no possible correct yes or no answer.

It is possible to construct a solution which returns "halts", "does
not halt", or "inconclusive" which is never wrong--and programs of
this sort do exist in practice and are occasionally used--but this
isn't because the "inconclusive" cases have no correct answer.

Actual machines will always eventually halt (at least by the end of the
universe).
Only mental abstractions of machines may be construed as never halting.

There is a distinction to be made if you insist on this fact. A mathematical model of computation assumes implicitly that when a machine halts on a given input, it is always because the machine has finished producing the correct appropriate output.

It is possible to instruct a real machine to run forever. Since you are asserting that this machine must eventually halt, you are therefore asserting that this machine has entered an invalid run state, and you are breaking the implicit model of computation.

Because this is purely a mental fiction the answer pertaining whether or
not they halt that maps most closely to actuality is that they neither
halt nor fail to halt.

The overriding implicit assumption here--to make it fully explicit--is that all machines will do what they say they will do without error. This may be a mental fiction, but you can make these assumptions fully explicit in descriptions and talk about real world machines in the same manner. In such semantics, I can cast for a real version of the halting problem:

Would this executable binary halt if I give it this command line, assuming that this processor will fully and faithfully uphold its ISA, and that it were given sufficient space to hold all the working files that it needs?

If you object that this too is only a mental fiction, I will point out that answering this kind of question is what actually happens in many real-world program analyses [1]; mental fiction or not, it is an essential problem class for working on real data in production scenarios and not merely an academic curiosity.

[1] To be fair, the halting problem itself is not the most useful problem to solve. Pointer aliasing--which is equally undecidable--is the more important problem.

I am trying to Grok the Halting Problem in an effort to Grok the set of paradoxes, and therefore more fully understand the fundamental nature of truth.

If one treats natural language as a mathematical formalism one may discover extremely subtle nuances of meaning that were never discerned before. In some cases these subtle nuances of meaning may show that some elements of the set of "common knowledge" that are universally accepted as fundamental truth are actually incorrect.

Paradoxes such as the Halting Problem seem to form instances such as this.

How does the fact that the primary expression of the Halting problem is
in mathematical notation, rather than English, affect your thinking on this?

Patricia
.



Relevant Pages

  • Re: The Halting Problem is merely an erroneously formed question
    ... Since you are asserting that this machine must eventually halt, you are therefore asserting that this machine has entered an invalid run state, and you are breaking the implicit model of computation. ... This may be a mental fiction, but you can make these assumptions fully explicit in descriptions and talk about real world machines in the same manner. ... the halting problem itself is not the most useful problem to solve. ... There seems to be something that is slipping past the math notation that begins to be apparent in the English. ...
    (comp.theory)
  • Re: The Halting Problem is merely an erroneously formed question
    ... Since you are asserting that this machine must eventually halt, you are therefore asserting that this machine has entered an invalid run state, and you are breaking the implicit model of computation. ... This may be a mental fiction, but you can make these assumptions fully explicit in descriptions and talk about real world machines in the same manner. ... the halting problem itself is not the most useful problem to solve. ... I am trying to Grok the Halting Problem in an effort to Grok the set of paradoxes, and therefore more fully understand the fundamental nature of truth. ...
    (comp.theory)
  • Re: The Halting Problem is merely an erroneously formed question
    ... Since you are asserting that this machine must eventually halt, you are therefore asserting that this machine has entered an invalid run state, and you are breaking the implicit model of computation. ... This may be a mental fiction, but you can make these assumptions fully explicit in descriptions and talk about real world machines in the same manner. ... the halting problem itself is not the most useful problem to solve. ... word games that are harder to play in mathematical notation. ...
    (comp.theory)
  • Re: simple and beauty strategy
    ... the halting problem is a decision problem ... Alan Turing proved in 1936 that a general algorithm to solve the ... the program will eventually halt when run with that input. ... undecidability of a problem in the lambda calculus had already been ...
    (rec.gambling.lottery)
  • 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)