Re: Halting Problem: What Constitutes Pathological Input

On 2025-05-07 15:36:39 +0000, olcott said:

On 5/7/2025 4:42 AM, Mikko wrote:

On 2025-05-06 15:29:59 +0000, olcott said:
 

On 5/6/2025 4:35 AM, Mikko wrote:

On 2025-05-05 17:37:20 +0000, olcott said:
 

On 5/5/2025 11:13 AM, Mr Flibble wrote:

On Mon, 05 May 2025 11:58:50 -0400, dbush wrote:
 

On 5/5/2025 11:51 AM, olcott wrote:

On 5/5/2025 10:17 AM, Mr Flibble wrote:

What constitutes halting problem pathological input:
 Input that would cause infinite recursion when using a decider of the
simulating kind.
 Such input forms a category error which results in the halting problem
being ill-formed as currently defined.
 /Flibble

 I prefer to look at it as a counter-example that refutes all of the
halting problem proofs.

 Which start with the assumption that the following mapping is computable
and that (in this case) HHH computes it:
  Given any algorithm (i.e. a fixed immutable sequence of instructions) X
described as <X> with input Y:
 A solution to the halting problem is an algorithm H that computes the
following mapping:
 (<X>,Y) maps to 1 if and only if X(Y) halts when executed directly
(<X>,Y) maps to 0 if and only if X(Y) does not halt when executed
directly
  

int DD()
{
  int Halt_Status = HHH(DD);
  if (Halt_Status)
    HERE: goto HERE;
  return Halt_Status;
}
 https://github.com/plolcott/x86utm
 The x86utm operating system includes fully operational HHH and DD.
https://github.com/plolcott/x86utm/blob/master/Halt7.c
 When HHH computes the mapping from *its input* to the behavior of DD
emulated by HHH this includes HHH emulating itself emulating DD. This
matches the infinite recursion behavior pattern.
 Thus the Halting Problem's "impossible" input is correctly determined
to be non-halting.
 

 Which is a contradiction.  Therefore the assumption that the above
mapping is computable is proven false, as Linz and others have proved
and as you have *explicitly* agreed is correct.

 The category (type) error manifests in all extant halting problem proofs
including Linz.  It is impossible to prove something which is ill- formed
in the first place.
 /Flibble

 The above example is category error because it asks
HHH(DD) to report on the direct execution of DD() and
the input to HHH specifies a different sequence of steps.

 No, it does not. The input is DD specifides exactly the same sequence
of steps as DD. HHH just answers about a different sequence of steps
instead of the the seqeunce specified by its input.

 <MIT Professor Sipser agreed to ONLY these verbatim words 10/13/2022>
     If simulating halt decider H correctly simulates its
     input D until H correctly determines that its simulated D
     *would never stop running unless aborted* then
 *input D* is the actual input
*would never stop running unless aborted*
is the hypothetical H/D pair where H does not abort.

 H is hypthetical. There is no actual decider in Sipeser's words. But
what is said about D is true about any actual input as there is no
restriction on D other than it is an input to H.
 

You cannot possibly show the exact execution trace

 That's right. An execution trace is too long to make without tools
that I don't have. Just remenber that absence of evidence is not
evidence of absense.
 

 The execution trace of DD correctly emulated by HHH
keeps repeating the first five instructions until
HHH correctly determines:
 *simulated D would never stop running unless aborted*
In other words HHH predicts what the behavior of DD
*would be* if HHH was a UTM.

No, it starts with first instructions of DD followed by a large number
of instructions of HHH, the last of which is ret, followed by sixth,
seventh, eighth, and ninth instruction and then by eleventh and
folloing instructions up to the ret instruction where DD ends.
If you get someting else you dont have a good tracing tool.
--
Mikko