Re: Halting Problem: What Constitutes Pathological Input

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.
_DD()
[00002133] 55         push ebp      ; housekeeping
[00002134] 8bec       mov ebp,esp   ; housekeeping
[00002136] 51         push ecx      ; make space for local
[00002137] 6833210000 push 00002133 ; push DD
[0000213c] e882f4ffff call 000015c3 ; call HHH(DD)
[00002141] 83c404     add esp,+04
[00002144] 8945fc     mov [ebp-04],eax
[00002147] 837dfc00   cmp dword [ebp-04],+00
[0000214b] 7402       jz 0000214f
[0000214d] ebfe       jmp 0000214d
[0000214f] 8b45fc     mov eax,[ebp-04]
[00002152] 8be5       mov esp,ebp
[00002154] 5d         pop ebp
[00002155] c3         ret
Size in bytes:(0035) [00002155]
--
Copyright 2024 Olcott "Talent hits a target no one else can hit; Genius
hits a target no one else can see." Arthur Schopenhauer