On 8/28/23 11:05 AM, olcott wrote:
> On 8/27/2023 2:31 PM, olcott wrote:
>> On 8/27/2023 12:13 PM, olcott wrote:
>>> On 8/27/2023 10:00 AM, olcott wrote:
>>>> On 8/25/2023 1:48 PM, olcott wrote:
>>>>> A pair of C functions are defined such that D has the halting problem
>>>>> proof's pathological relationship to simulating termination
>>>>> analyzer H.
>>>>> When it is understood that D correctly simulated by H (a) Is the
>>>>> behavior that H must report on and (b) Cannot possibly terminate
>>>>> normally then it is understood that D is correctly determined to be
>>>>> non-
>>>>> halting.
>>>>>
>>>>> We can know that D correctly simulated by H must have different
>>>>> behavior
>>>>> than D(D) directly executed in main() because we can see (in its
>>>>> execution trace shown below) exactly how the pathological relationship
>>>>> between D and H changes the behavior of D relative to H.
>>>>>
>>>>> For any program H that might determine whether programs halt, a
>>>>> "pathological" program D, called with some input, can pass its own
>>>>> source and its input to H and then specifically do the opposite of
>>>>> what
>>>>> H predicts D will do. No H can exist that handles this case.
>>>>> https://en.wikipedia.org/wiki/Halting_problem
>>>>>
>>>>> "A decision problem is a yes-or-no question on an infinite set of
>>>>> inputs" https://en.wikipedia.org/wiki/Decision_problem#Definition
>>>>>
>>>>> Can D correctly simulated by H terminate normally?
>>>>> The x86utm operating system: https://github.com/plolcott/x86utm
>>>>> is based on an open source x86 emulator. x86utm enables one C function
>>>>> to execute another C function in debug step mode.
>>>>>
>>>>> // The following is written in C
>>>>> //
>>>>> 01 typedef int (*ptr)(); // pointer to int function
>>>>> 02 int H(ptr x, ptr y)   // uses x86 emulator to simulate its input
>>>>> 03
>>>>> 04 int D(ptr x)
>>>>> 05 {
>>>>> 06   int Halt_Status = H(x, x);
>>>>> 07   if (Halt_Status)
>>>>> 08     HERE: goto HERE;
>>>>> 09   return Halt_Status;
>>>>> 10 }
>>>>> 11
>>>>> 12 void main()
>>>>> 13 {
>>>>> 14   H(D,D);
>>>>> 15 }
>>>>>
>>>>> *Execution Trace*
>>>>> Line 14: main() invokes H(D,D);
>>>>>
>>>>> *keeps repeating* (unless aborted)
>>>>> Line 06: simulated D(D) invokes simulated H(D,D) that simulates D(D)
>>>>>
>>>>> *Simulation invariant*
>>>>> D correctly simulated by H cannot possibly reach past its own line 06.
>>>>>
>>>>> H correctly determines that D correctly simulated by H cannot possibly
>>>>> terminate normally on the basis that H recognizes a dynamic behavior
>>>>> pattern equivalent to infinite recursion. H returns 0 this basis.
>>>>>
>>>>> *ADDENDUM*
>>>>>
>>>>> (1) The source-code of H and D conclusively proves that D correctly
>>>>> simulated by H cannot possibly terminate normally.
>>>>>
>>>>> *THIS IS THE PART THAT EVERYONE LIES ABOUT*
>>>>> (2) The correct simulation of D by H must include the fact that
>>>>> D would continue to call H until stack overflow crash unless H
>>>>> aborts its simulation of D.
>>>>>
>>>>> (3) (2) Means that D is correctly simulated by H and this correctly
>>>>> simulated D is non-halting.
>>>>>
>>>>> (4) "A decision problem is a yes-or-no question on an infinite set
>>>>> of inputs" https://en.wikipedia.org/wiki/Decision_problem#Definition
>>>>> This means that the behavior of non-inputs is not allowed to be
>>>>> considered.
>>>>>
>>>>
>>>> If H ignores reality (not a good idea) and [as most of my reviewers
>>>> believe] makes pretend that it is simulating D(D) directly executed in
>>>> main() then the actual D that H is actually simulating will crash from
>>>> stack overflow because H will never stop simulating D.
>>>>
>>>> This conclusively proves that D is correct to abort its simulation and
>>>> return 0 indicating that D correctly simulated by H cannot possibly
>>>> terminate normally.
>>>>
>>>
>>> (5) Of the infinite set of every possible H where D is correctly
>>> simulated by H there are only a THREE categories of possible
>>> behaviors for H:  (1)(a), (1)(b) and (2)
>>>
>>> (1) Abort its simulation of D after a finite number of steps:
>>>     (a) Return 0 indicating that D correctly simulated by H cannot
>>>         possibly terminate normally.
>>>
>>>     (b) Return 1 indicating that D correctly simulated by H will
>>>         terminate normally.
>>>
>>> (2) Never abort its simulation of D.
>>>
>>> Anyone having a sufficient knowledge of C can correctly determine which
>>> of these options are incorrect on the basis of the source-code of D.
>>>
>>
>> When a termination analyzer is required to provide the halt status or an
>> input that deliberately contradicts whatever Boolean value that this
>> termination analyzer returns the halting problem merely mirrors the Liar
>> Paradox.
>>
>> The Liar Paradox cannot be correctly resolved to a value of True or
>> False only because it is semantically unsound because it is self-
>> contradictory.
>>
>> Thus the inability of a termination analyzer to provide a correct
>> Boolean return value is analogous to a CAD system's inability to
>> correctly draw a square circle. Thus this interpretation of the halting
>> problem is merely an artificial contrivance with no actual merit.
>>
>
> This is "undecidable" in the same way that finding an
> N such that N > 5 and N < 2 is "undecidable".

Nope. Because the correct answer for the H you have provided exists, it
is Halting, BECAUSE your H answers non-halting, and THAT H always will
as that is the only thing THAT H can do as that is what it is programmed
to do. So THIS H is just wrong, the problem isn't "undecidabe"

If you want to try to create an other H that answers Halting for the D
built on it, that OTHER D will just go into a loop and be non-halting,
so that other H is also wrong.

If you make even another H that doesn't abort its simulation, it will
just be wrong by not answering.

Note, you don't even HAVE a "Halting Question" to answer until you
actauly define your Halt Decider, so the problem that is "undecidable"
can't be the "Halting Problem", as it doesn't exist until we have the
input program, and we can't have the program "D" until we have the
program H, fully defined, and at that point, the answer exists (as
described above).

So, the only "undecidable" question you are talking about is one that
isn't the Halting Problem, so you logic is just unsound.

>
> When a termination analyzer must return a Boolean value that provides
> the halt status of and D does the opposite of whatever Boolean value
> that H returns the halting problem is a mere ruse and not any legitimate
> decision problem at all.

Right, and it just can't because the problem is non-computable, not that
it doesn't have an answer.

>
> This only happens when we expect H to determine the halt status of a
> non-input.

Nope, The Behavior of D(D) IS the input, or your H isn't a Halt Decider.

You are just proving you don't understand what you are talking about.

>
> int sum(int x, int y)
> {
>   return x + y;
> }
>
> When for forbid H to report on not inputs this is the same as
> forbidding sum(3,4) to report on the sum of 5 + 7.

Who is forbiding H from reporting on the behavior of the input? It is
perfectly free to give what ever answer it wants (as long as that it
swhat is has been programmed to do, as all programs onlygive the answers
they have been programmed to do). The only issue is that, becaus the
input is build on using a copy of the decider, as ALLOWED by the theory
of computability, that answer will justbe wrong.