Re: The Halting Problem is merely an erroneously formed question
 From: Patricia Shanahan <pats@xxxxxxx>
 Date: Fri, 10 Feb 2012 17:34:49 0800
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). SoActual machines will always eventually halt (at least by the end of the
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 wrongand programs of
this sort do exist in practice and are occasionally usedbut this
isn't because the "inconclusive" cases have no correct answer.
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 hereto make it fully explicitis 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 realworld 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 aliasingwhich is equally undecidableis 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
.
 FollowUps:
 Re: The Halting Problem is merely an erroneously formed question
 From: Peter Olcott
 Re: The Halting Problem is merely an erroneously formed question
 References:
 The Halting Problem is merely an erroneously formed question
 From: Peter Olcott
 Re: The Halting Problem is merely an erroneously formed question
 From: Joshua Cranmer
 Re: The Halting Problem is merely an erroneously formed question
 From: Peter Olcott
 Re: The Halting Problem is merely an erroneously formed question
 From: Joshua Cranmer
 Re: The Halting Problem is merely an erroneously formed question
 From: Peter Olcott
 The Halting Problem is merely an erroneously formed question
 Prev by Date: Re: The Halting Problem is merely an erroneously formed question
 Next by Date: Re: Basis for bypassing the Halting Problem ?
 Previous by thread: Re: The Halting Problem is merely an erroneously formed question
 Next by thread: Re: The Halting Problem is merely an erroneously formed question
 Index(es):
Relevant Pages
