On 7/27/2022 1:19 PM, Dennis Bush wrote:
> On Wednesday, July 27, 2022 at 2:08:36 PM UTC-4, olcott wrote:
>> On 7/27/2022 12:51 PM, Dennis Bush wrote:
>>> On Wednesday, July 27, 2022 at 1:48:10 PM UTC-4, olcott wrote:
>>>> On 7/27/2022 12:14 PM, Dennis Bush wrote:
>>>>> On Wednesday, July 27, 2022 at 1:05:33 PM UTC-4, olcott wrote:
>>>>>> On 7/27/2022 11:41 AM, Ben Bacarisse wrote:
>>>>>>> Malcolm McLean <malcolm.ar...@gmail.com> writes:
>>>>>>>
>>>>>>>> On Monday, 25 July 2022 at 20:22:44 UTC+1, Mr Flibble wrote:
>>>>>>>>> How can we help Olcott understand that his "infinite recursion" is a
>>>>>>>>> property of his simulating halting decider and NOT a property of the
>>>>>>>>> input passed to his decider? His error is compounded by him
>>>>>>>>> incorrectly mapping his decider's recursion to the input being
>>>>>>>>> non-halting.
>>>>>>>>>
>>>>>>>> The input passed to the decider includes a near copy of the decider
>>>>>>>> itself. So if the decider works on the simulating principle, then
>>>>>>>> infinitely nested simulation is a property of the system, and that's
>>>>>>>> the way that a reasonably functional simulating decider will fail.
>>>>>>>
>>>>>>> This sentence is not unlike stating that if the moon is made of cheese
>>>>>>> then halting is decidable. Or that a halt decider fails to be a halt
>>>>>>> decider it can fail by infinitely nested simulation.
>>>>>>>
>>>>>>> There are no halt deciders, simulating or otherwise. Nothing about them
>>>>>>> can be recursive or non-recursive.
>>>>>>>
>>>>>>>> (PO is aware of this and tries to code round it, but in fact this
>>>>>>>> cannot be done).
>>>>>>>
>>>>>>> He is not aware that there are no halt deciders, and I don't think
>>>>>>> anyone should be encouraging that misunderstanding.
>>>>>>>
>>>>>>>> However Linz's H_Hat doesn't require H to be a simulating halt
>>>>>>>> decider.
>>>>>>>
>>>>>>> He required H to an arbitrary denote a member of an empty set.
>>>>>>>
>>>>>> H(P,P) does correctly determine that its correct x86 emulation of its
>>>>>> input would never reach the C:"return" or x86:"ret" instruction of this
>>>>>> input because this input specifies infinitely recursive simulation to H.
>>>>>
>>>>> The halting problem doesn't care that there is no implementation of the function H that can simulate the function P to a final state.
>>>>>
>>>>> The halting problem cares if Pa(Pa) halts, which it does.
>>>>>
>>>>> If Ha was a halt decider, Ha(Pa,Pa) would return 1. Ha(Pa,Pa) returns 0, therefore Ha is not a halt decider.
>>>>>
>>>> For any program H that might determine if programs halt, a
>>>> "pathological" program P, called with some input, can pass its own
>>>> source and its input to H and then specifically do the opposite of what
>>>> H predicts P will do. No H can exist that handles this case.
>>>> https://en.wikipedia.org/wiki/Halting_problem
>>>> H(P,P) does correctly determine the halt status of the above
>>>> "pathological" input template.
>>>
>>> No, it determines that no implementation of the function H can simulate the function call P(P) to a final state.
>>>
>> Because the correctly simulated input to H(P,P) specifies infinite
>> recursion H cannot simulate its input to the final state of this input.
>
> There is no infinite recursion. You only think there is because no implementation of the function H can simulate the function call P(P) to a final state.
>
> A *complete* and correct simulation of the input to Ha(Pa,Pa) is performed by UTM(Pa,Pa) which halts, demonstrating that Ha aborted too soon.
>
>>> If Ha was a halt decider, Ha(Pa,Pa) would return 1. Ha(Pa,Pa) returns 0, therefore Ha is not a halt decider.
>> If we change the subject to some entirely different sequence of
>> instructions like you just did then you commit the strawman deception.
>
> H has a fixed algorithm. That algorithm is Ha. P has a fixed algorithm. That algorithm is Pa. It's the same set of instructions.
>
>>
>> *straw man*
>> An intentionally misrepresented proposition that is set up because it is
>> easier to defeat than an opponent's real argument.
>> https://www.lexico.com/en/definition/straw_man
>>
>> The verified fact is that H(P,P) does correctly determine that the
>> correct correct correct correct
>> correct correct correct correct
>> correct correct correct correct
>> simulation of its input would never reach the C:"return" or x86:"ret"
>> instruction of this input because this input species infinite recursion
>> to H.
>
> There is no infinite recursion. You only think there is because no implementation of the function H can simulate the function call P(P) to a final state.
>
> So H / Ha is not a halt decider because it is answering the wrong question.

Below I show that pattern that any expert of the x86 language can spot
as specifying infinitely recursive simulation right below.

The correct x86 emulation of the input to H(P,P) by H would always cycle
through its first seven instructions of P again and again until H aborts
its simulation of P.

*You must be clueless about the x86 language to not see this*
*You must be clueless about the x86 language to not see this*
*You must be clueless about the x86 language to not see this*
*You must be clueless about the x86 language to not see this*
*You must be clueless about the x86 language to not see this*

Example 06:
H correctly determines that P() never halts (prior version of halt decider)

#include <stdint.h>
#define u32 uint32_t

#include <stdint.h>
typedef void (*ptr)();

void P(ptr x)
{ if (H(x, x))
HERE: goto HERE;
return;
}

int main()
{ Output("Input_Halts = ", H(P, 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 // push P
[00001359](03) 8b4d08 mov ecx,[ebp+08]
[0000135c](01) 51 push ecx // push P
[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
// H emulates the first seven instructions of P
....[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

// The emulated H emulates the first seven instructions of P
....[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

*Matched infinite recursion detection criteria*
(1) P() calls H(P,P) twice in sequence.
(2) With the same arguments.
(3) With no control flow instructions in P preceding its invocation of
H(P,P) that could escape repeated simulations.

....[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) = 237 pages

--
Copyright 2022 Pete Olcott

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