On 5/12/2022 1:00 PM, Mr Flibble wrote:
> On Thu, 12 May 2022 12:51:27 -0500
> olcott <NoOne@NoWhere.com> wrote:
>
>> On 5/12/2022 12:47 PM, Mr Flibble wrote:
>>> On Thu, 12 May 2022 12:45:15 -0500
>>> olcott <NoOne@NoWhere.com> wrote:
>>>
>>>> On 5/12/2022 12:43 PM, Mr Flibble wrote:
>>>>> On Wed, 11 May 2022 19:23:45 -0500
>>>>> olcott <NoOne@NoWhere.com> wrote:
>>>>>
>>>>>> On 5/11/2022 2:11 PM, Mr Flibble wrote:
>>>>>>> On Wed, 11 May 2022 13:07:16 -0500
>>>>>>> olcott <NoOne@NoWhere.com> wrote:
>>>>>>>
>>>>>>>> Proof that H(P,P)==0 is correct [ refuting the halting problem
>>>>>>>> proofs ]
>>>>>>>>
>>>>>>>> The x86utm operating system was created so that every detail of
>>>>>>>> the conventional halting problem counter example could be fully
>>>>>>>> specified in C/x86.
>>>>>>>>
>>>>>>>> In computability theory, the halting problem is the
>>>>>>>> problem of determining, from a description of an
>>>>>>>> arbitrary computer program and an input, whether the
>>>>>>>> program will finish running, or continue to run
>>>>>>>> forever...
>>>>>>>>
>>>>>>>> For any program f that might determine if programs halt,
>>>>>>>> a "pathological" program g, called with some input, can
>>>>>>>> pass its own source and its input to f and then
>>>>>>>> specifically do the opposite of what f predicts g will do. No f
>>>>>>>> can exist that handles this case.
>>>>>>>> https://en.wikipedia.org/wiki/Halting_problem
>>>>>>>>
>>>>>>>> This exact same relationship of f(g,g) was created as H(P,P),
>>>>>>>> shown below.
>>>>>>>>
>>>>>>>> This is the overview of the method for proving that this
>>>>>>>> analysis is correct:
>>>>>>>> (a) Verify that the execution trace of P by H is correct by
>>>>>>>> comparing this execution trace to the ax86 source-code of P.
>>>>>>>>
>>>>>>>> (b) Verify that this execution trace shows that P is stuck in
>>>>>>>> infinitely nested simulation (a non-halting behavior).
>>>>>>>>
>>>>>>>> This proof can only be understood only by those having
>>>>>>>> sufficient technical competence in:
>>>>>>>> (a) software engineering (recognizing infinite recursion in C
>>>>>>>> and x86 code) (b) the x86 programming language
>>>>>>>> (c) the C programming language and
>>>>>>>> (d) the details of how C is translated into x86 by the
>>>>>>>> Microsoft C compilers.
>>>>>>>>
>>>>>>>> #include <stdint.h>
>>>>>>>> #define u32 uint32_t
>>>>>>>>
>>>>>>>> void P(u32 x)
>>>>>>>> {
>>>>>>>> if (H(x, x))
>>>>>>>> HERE: goto HERE;
>>>>>>>> return;
>>>>>>>> }
>>>>>>>>
>>>>>>>> int main()
>>>>>>>> {
>>>>>>>> Output("Input_Halts = ", H((u32)P, (u32)P));
>>>>>>>> }
>>>>>>>>
>>>>>>>> _P()
>>>>>>>> [00001352](01) 55 push ebp
>>>>>>>> [00001353](02) 8bec mov ebp,esp
>>>>>>>> [00001355](03) 8b4508 mov eax,[ebp+08]
>>>>>>>> [00001358](01) 50 push eax
>>>>>>>> [00001359](03) 8b4d08 mov ecx,[ebp+08]
>>>>>>>> [0000135c](01) 51 push ecx
>>>>>>>> [0000135d](05) e840feffff call 000011a2 // call H
>>>>>>>> [00001362](03) 83c408 add esp,+08
>>>>>>>> [00001365](02) 85c0 test eax,eax
>>>>>>>> [00001367](02) 7402 jz 0000136b
>>>>>>>> [00001369](02) ebfe jmp 00001369
>>>>>>>> [0000136b](01) 5d pop ebp
>>>>>>>> [0000136c](01) c3 ret
>>>>>>>> Size in bytes:(0027) [0000136c]
>>>>>>>>
>>>>>>>> _main()
>>>>>>>> [00001372](01) 55 push ebp
>>>>>>>> [00001373](02) 8bec mov ebp,esp
>>>>>>>> [00001375](05) 6852130000 push 00001352 // push P
>>>>>>>> [0000137a](05) 6852130000 push 00001352 // push P
>>>>>>>> [0000137f](05) e81efeffff call 000011a2 // call H
>>>>>>>> [00001384](03) 83c408 add esp,+08
>>>>>>>> [00001387](01) 50 push eax
>>>>>>>> [00001388](05) 6823040000 push 00000423 // "Input_Halts
>>>>>>>> = " [0000138d](05) e8e0f0ffff call 00000472 // call
>>>>>>>> Output [00001392](03) 83c408 add esp,+08
>>>>>>>> [00001395](02) 33c0 xor eax,eax
>>>>>>>> [00001397](01) 5d pop ebp
>>>>>>>> [00001398](01) c3 ret
>>>>>>>> Size in bytes:(0039) [00001398]
>>>>>>>>
>>>>>>>> machine stack stack machine assembly
>>>>>>>> address address data code language
>>>>>>>> ======== ======== ======== ========= =============
>>>>>>>> ...[00001372][0010229e][00000000] 55 push ebp
>>>>>>>> ...[00001373][0010229e][00000000] 8bec mov ebp,esp
>>>>>>>> ...[00001375][0010229a][00001352] 6852130000 push 00001352 //
>>>>>>>> push P ...[0000137a][00102296][00001352] 6852130000 push
>>>>>>>> 00001352 // push P ...[0000137f][00102292][00001384] e81efeffff
>>>>>>>> call 000011a2 // call H
>>>>>>>>
>>>>>>>> Begin Local Halt Decider Simulation Execution Trace Stored
>>>>>>>> at:212352 ...[00001352][0021233e][00212342] 55 push ebp
>>>>>>>> // enter P ...[00001353][0021233e][00212342] 8bec mov
>>>>>>>> ebp,esp ...[00001355][0021233e][00212342] 8b4508 mov
>>>>>>>> eax,[ebp+08] ...[00001358][0021233a][00001352] 50 push
>>>>>>>> eax // push P ...[00001359][0021233a][00001352] 8b4d08 mov
>>>>>>>> ecx,[ebp+08] ...[0000135c][00212336][00001352] 51 push
>>>>>>>> ecx // push P ...[0000135d][00212332][00001362] e840feffff call
>>>>>>>> 000011a2 // call H ...[00001352][0025cd66][0025cd6a] 55
>>>>>>>> push ebp // enter P ...[00001353][0025cd66][0025cd6a] 8bec
>>>>>>>> mov ebp,esp ...[00001355][0025cd66][0025cd6a] 8b4508
>>>>>>>> mov eax,[ebp+08] ...[00001358][0025cd62][00001352] 50
>>>>>>>> push eax // push P ...[00001359][0025cd62][00001352] 8b4d08
>>>>>>>> mov ecx,[ebp+08] ...[0000135c][0025cd5e][00001352] 51
>>>>>>>> push ecx // push P ...[0000135d][0025cd5a][00001362]
>>>>>>>> e840feffff call 000011a2 // call H Local Halt Decider:
>>>>>>>> Infinite Recursion Detected Simulation Stopped
>>>>>>>>
>>>>>>>> H sees that P is calling the same function from the same
>>>>>>>> machine address with identical parameters, twice in sequence.
>>>>>>>> This is the infinite recursion (infinitely nested simulation)
>>>>>>>> non-halting behavior pattern.
>>>>>>>>
>>>>>>>> ...[00001384][0010229e][00000000] 83c408 add esp,+08
>>>>>>>> ...[00001387][0010229a][00000000] 50 push eax
>>>>>>>> ...[00001388][00102296][00000423] 6823040000 push 00000423 //
>>>>>>>> "Input_Halts ="
>>>>>>>> ---[0000138d][00102296][00000423] e8e0f0ffff call 00000472 //
>>>>>>>> call Output Input_Halts = 0
>>>>>>>> ...[00001392][0010229e][00000000] 83c408 add esp,+08
>>>>>>>> ...[00001395][0010229e][00000000] 33c0 xor eax,eax
>>>>>>>> ...[00001397][001022a2][00100000] 5d pop ebp
>>>>>>>> ...[00001398][001022a6][00000004] c3 ret
>>>>>>>> Number of Instructions Executed(15892) lines = 237 pages
>>>>>>>>
>>>>>>>>
>>>>>>>> Halting problem undecidability and infinitely nested simulation
>>>>>>>> (V5)
>>>>>>>>
>>>>>>>> https://www.researchgate.net/publication/359984584_Halting_problem_undecidability_and_infinitely_nested_simulation_V5
>>>>>>>>
>>>>>>>
>>>>>>> Your simulation approach is erroneous as there is no infinite
>>>>>>> recursion; the key to understanding this is by realizing the
>>>>>>> implication of the words "pass its own source" in the
>>>>>>> following:
>>>>>>
>>>>>>
>>>>>> YOU IGNORED THIS PART
>>>>>>
>>>>>> This proof can only be understood only by those having sufficient
>>>>>> technical competence in:
>>>>>> (a) software engineering - recognizing infinite recursion in
>>>>>> C/x86 (b) the x86 programming language
>>>>>> (c) the C programming language and
>>>>>> (d) the details of how C is translated into x86 by the Microsoft
>>>>>> C compilers.
>>>>>
>>>>> (a) I have been a software developer/engineer since 1993 and am
>>>>> able to recognize infinite recursion and additionally, and more
>>>>> importantly, a lack of infinite recursion.
>>>>
>>>> This has been disproven in that you did not see this:
>>>>
>>>> >>>> H sees that P is calling the same function from the same
>>>> >>>> machine address with identical parameters, twice in
>>>> >>>> sequence. This is the infinite recursion (infinitely nested
>>>> >>>> simulation) non-halting behavior pattern.
>>>
>>> I am not talking about your braindead simulation, I am talking about
>>> the halting problem proofs you are trying to refute: THEY DO NOT
>>> HAVE AN INFINITE RECURSION.
>>>
>>> /Flibble
>>>
>>
>> My proofs prove that they do.
>> That you fail to comprehend this is no rebuttal at all.
>
> Only your simulation contains an infinite recursion due to a category
> error ON YOUR PART. Your category error is proof that your
> simulation-based proof is in error.
>
> /Flibble
>

> PO's idea is to have a simulator with an infinite cycle detector.
> You would achieve this by modifying a UTM, so describing it as
> a "modified UTM", or "acts like a UTM until it detects an infinite
> cycle", is reasonable. And such a machine is a fairly powerful
> halt decider. Even if the infinite cycle detector isn't very
> sophisticated, it will still catch a large subset of non-halting
> machines.

The following simplifies the syntax for the definition of the Linz
Turing machine Ĥ.
There is no need for the infinite loop after H.qy because it is never
reached. The halting criteria has been adapted so that it applies to a
simulating halt decider (SHD).

Ĥ.q0 ⟨Ĥ⟩ ⊢* H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* H.qy
If the correctly simulated input ⟨Ĥ⟩ ⟨Ĥ⟩ to H would reach its own final
state of ⟨Ĥ.qy⟩ or ⟨Ĥ.qn⟩.

Ĥ.q0 ⟨Ĥ⟩ ⊢* H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* H.qn
If the correctly simulated input ⟨Ĥ⟩ ⟨Ĥ⟩ to H would never reach its own
final state of ⟨Ĥ.qy⟩ or ⟨Ĥ.qn⟩.

When Ĥ is applied to ⟨Ĥ⟩
Ĥ copies its input ⟨Ĥ0⟩ to ⟨Ĥ1⟩ then H simulates ⟨Ĥ0⟩ ⟨Ĥ1⟩

Then these steps would keep repeating: (unless their simulation is aborted)
Ĥ0 copies its input ⟨Ĥ1⟩ to ⟨Ĥ2⟩ then H0 simulates ⟨Ĥ1⟩ ⟨Ĥ2⟩
Ĥ1 copies its input ⟨Ĥ2⟩ to ⟨Ĥ3⟩ then H1 simulates ⟨Ĥ2⟩ ⟨Ĥ3⟩
Ĥ2 copies its input ⟨Ĥ3⟩ to ⟨Ĥ4⟩ then H2 simulates ⟨Ĥ3⟩ ⟨Ĥ4⟩...

Since we can see that the simulated input: ⟨Ĥ0⟩ to H would never reach
its own final state of ⟨Ĥ0.qy⟩ or ⟨Ĥ0.qn⟩ we know that it is non-halting.

Linz, Peter 1990. An Introduction to Formal Languages and Automata.
Lexington/Toronto: D. C. Heath and Company. (317-320)

--
Copyright 2022 Pete Olcott

"Talent hits a target no one else can hit;
Genius hits a target no one else can see."
Arthur Schopenhauer