# 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 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.

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

.

**Follow-Ups**:**Re: The Halting Problem is merely an erroneously formed question***From:*Peter Olcott

**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

- 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):