Re: Halting Problem: What Constitutes Pathological Input

On 5/6/25 9:47 PM, olcott wrote:

On 5/6/2025 5:43 PM, Richard Damon wrote:

On 5/6/25 11:10 AM, olcott wrote:

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

On 2025-05-05 18:14:25 +0000, olcott said:
>

On 5/5/2025 11:16 AM, dbush wrote:

On 5/5/2025 12:13 PM, 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

>
All algorithms either halt or do not halt when executed directly. Therefore the problem is not ill formed.

>
When BOTH Boolean RETURN VALUES are the wrong answer
THEN THE PROBLEM IS ILL-FORMED. Self-contradiction must
be screened out as semantically incorrect.

>
Irrelevant. One of the boolean values (the one not returned) is the
right one as can be determined e.g. with an UTM.
>

You only get something that appears that way when a false assumption is made, namely that the halting function is computable.

>
The mapping from the input HHH(DD) finite string of
machine code to DOES SPECIFY RECURSIVE EMULATION
THAT WOULD PREVENT DD FROM EVER HALTING.

>
No, it does not. HHH returns 0 and DD halts.
>

>
You can't show the detailed steps of the execution
trace of DD emulated by HHH (according to the rules
of the x86 language) where DD halts because you are wrong.

>
Because a trace of DD correctly emulatd by HHH doesn't exist as HHH doesn't correctly emulate DD
>

 Show what the execution trace of DD emulated by HHH
according to the rules of the x86 language should be
 

Since HHH doesn't do that, you are just proving that your "logic" is based on the assumption of the impossible.
As I pointed out elsewhere, you have published the trace of the CORRECT emulation of DD yourself (it just isn't done by HHH, which never does it).
Either look at your trace generated by main calling DD directly.
Or look at the trace of main calling HHH(DD) and change the address if main prior to that call to be the address of DD
Try to show the error in that.

_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]