Re: Happy Thanksgiving to all (logical necessity)(Over Ben's head)

[olcott]

On 12/6/2020 7:56 PM, Ben Bacarisse wrote:
> Context... Your response to my challenge to show a function F such that
> F(P, I) is true if and only if P(I) is a finite computation and false
> otherwise:
>
> bool Halts(u32 P, u32 I)
> {
> bool Halted = false;
> bool Aborted = false;
> while (!Halted && !Aborted)
> {
> Halted = DebugStep(P, I);
> Aborted = Needs_To_Be_Aborted();
> }
> return !Aborted;
> }
>
> My confounding example, as promised, is the computation
> Confound_Halts(Confound_Halts) with:
>
> void Confound_Halts(u32 P) { if (Halts(P, P)) while (1); }
>
> olcott <No...@NoWhere.com> writes:
>
>> On 12/5/2020 7:50 PM, Ben Bacarisse wrote:
>
>>> ... I am interested in the
>>> fact that
>>>
>>> (a) Halts(Confound_Halts, Confound_Halts) is false and,
>>> (b) Confound_Halts(Confound_Halts) is a finite computation.
>>
>> On 11/27/2020 9:02 PM, Ben Bacarisse wrote:
>>> A computation that would not halt if its simulation were not
>>> halted is indeed a non-halting computation.
>>
>> Halts(Confound_Halts, Confound_Halts) meets the above criteria of a
>> non-halting computation, thus false is indeed the correct answer.
>
> You stated that "the input to Halts" is a finite computation (see
> Message-ID: <6eSdnYuLBrIuVFzC...@giganews.com>). False is
> not the right answer for a finite computation. Were you wrong to say
> that in that post, or are you wrong now?
>
> As for that sentence of mine that you don't understand, let me explain
> again. Because of fact (a) above, both the direct computation
> Confound_Halts(Confound_Halts) and its simulation
> Simulate(Confound_Halts, Confound_Halts) halt. The sentence does not
> apply.
>
> Would you like me to explain the ruse you are trying to pull off again?
>
I proved that the simulation of Confound_Halts(u32 P) had to be halted
on line 18 of the simulation. The infinite recursion is between lines 12
and 18 of the simulation's execution trace shown at the bottom.

Either this is over your head or you are a liar. I have incorrectly
called you a liar so many times that I am going with it is over your
head. The assembly language must be too difficult for you.

This is my 2018-12-13 solution: Every time the same function is called a
second time from the same machine address with no control flow
instructions** in-between we can know that this is definitely infinite
recursion.

** A simplification of the original criteria to make my proof easier to
understand.

I completely recreated the whole simulation.
Prior simulations may have been incorrect.
Actual debug trace of Halts() deciding halting on main()

void Confound_Halts(u32 P)
{
if (Halts(P, P))
while (1);
}

int main()
{
Halts((u32)Confound_Halts, (u32)Confound_Halts);
HALT;
}

_Confound_Halts()
[000005e0](01) 55 push ebp
[000005e1](02) 8bec mov ebp,esp
[000005e3](03) 8b4508 mov eax,[ebp+08]
[000005e6](01) 50 push eax
[000005e7](03) 8b4d08 mov ecx,[ebp+08]
[000005ea](01) 51 push ecx
[000005eb](05) e880fdffff call 00000370 // CALL Halts()
[000005f0](03) 83c408 add esp,+08
[000005f3](02) 85c0 test eax,eax
[000005f5](02) 740b jz 00000602
[000005f7](05) ba01000000 mov edx,00000001
[000005fc](02) 85d2 test edx,edx
[000005fe](02) 7402 jz 00000602
[00000600](02) ebf5 jmp 000005f7
[00000602](01) 5d pop ebp
[00000603](01) c3 ret

_main()
[00000610](01) 55 push ebp
[00000611](02) 8bec mov ebp,esp
[00000613](05) 68e0050000 push 000005e0
[00000618](05) 68e0050000 push 000005e0
[0000061d](05) e84efdffff call 00000370 // CALL Halts()
[00000622](03) 83c408 add esp,+08
[00000625](01) f4 hlt
[00000626](01) 5d pop ebp
[00000627](01) c3 ret

Output_Debug_Trace() Trace_List.size(18)
[00000610](01) EMU_Level(0) 55 push ebp
[00000611](02) EMU_Level(0) 8bec mov ebp,esp
[00000613](05) EMU_Level(0) 68e0050000 push 000005e0
[00000618](05) EMU_Level(0) 68e0050000 push 000005e0
[0000061d](05) EMU_Level(0) e84efdffff call 00000370 // CALL
Halts()
[000005e0](01) EMU_Level(1) 55 push ebp
[000005e1](02) EMU_Level(1) 8bec mov ebp,esp
[000005e3](03) EMU_Level(1) 8b4508 mov eax,[ebp+08]
[000005e6](01) EMU_Level(1) 50 push eax
[000005e7](03) EMU_Level(1) 8b4d08 mov ecx,[ebp+08]
[000005ea](01) EMU_Level(1) 51 push ecx
[000005eb](05) EMU_Level(1) e880fdffff call 00000370 // CALL
Halts()
[000005e0](01) EMU_Level(2) 55 push ebp
[000005e1](02) EMU_Level(2) 8bec mov ebp,esp
[000005e3](03) EMU_Level(2) 8b4508 mov eax,[ebp+08]
[000005e6](01) EMU_Level(2) 50 push eax
[000005e7](03) EMU_Level(2) 8b4d08 mov ecx,[ebp+08]
[000005ea](01) EMU_Level(2) 51 push ecx
[000005eb](05) EMU_Level(2) e880fdffff call 00000370 // CALL
Halts()
The PRIOR Instruction Specifies Infinite Recursion: Simulation Stopped:

--
Copyright 2020 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre
minds." Einstein