Re: It is known that a correct halt decider must return false (in

[olcott]

On 11/26/2020 7:44 PM, Mike Terry wrote:
> On 26/11/2020 21:48, olcott wrote:
>> On 11/26/2020 3:27 PM, Mike Terry wrote:
>>> On 26/11/2020 21:16, olcott wrote:
>>>> On 11/26/2020 3:12 PM, Mike Terry wrote:
>>>>> On 26/11/2020 20:50, olcott wrote:
>>>>>> On 11/26/2020 2:43 PM, Mike Terry wrote:
>>>>>>> On 26/11/2020 20:32, olcott wrote:
>>>>>>>> On 11/26/2020 2:28 PM, Mike Terry wrote:
> <.. snip ..>
>>>>>>>>>
>>>>>>>>> That's not the actual problem at hand.  The problem at hand is
>>>>>>>>> whether
>>>>>>>>> your test within Halts:
>>>>>>>>>
>>>>>>>>> TEST:     [I've gone back to your own description.]
>>>>>>>>>
>>>>>>>>> (1) Keep a global execution trace of every line of user code.
>>>>>>>>>
>>>>>>>>> (2) Whenever any instruction is executed see if it is a function
>>>>>>>>> call.
>>>>>>>>>
>>>>>>>>> (3) If it is a function call find the prior call to this same
>>>>>>>>> function
>>>>>>>>> from the current machine address (if any) searching backward
>>>>>>>>> through
>>>>>>>>> the global execution trace and counting conditional branch
>>>>>>>>> instructions.
>>>>>>>>>
>>>>>>>>> (4) If found and conditional-branch-count == zero terminate the
>>>>>>>>> input.
>>>>>>>>>
>>>>>>>>> actually "works".  (i.e. only non-halting inputs are matched.)
>>>>>>>>>
>>>>>>>>> Your "global execution trace" contain a mixture of x86 program
>>>>>>>>> steps
>>>>>>>>> AT DIFFERENT EMULATION LEVELS.
>>>>>>>>
>>>>>>>> Not really they all call the same global DebugTrace() / Halts().
>>>>>>>>
>>>>>>>
>>>>>>> But your Halts() emulates its input (P,I), and then calls within the
>>>>>>> EMULATED (P,I) call Halts, so there are calls to Halts at different
>>>>>>> emulation levels.
>>>>>>>
>>>>>>>
>>>>>>> Mike.
>>>>>>>
>>>>>>
>>>>>>
>>>>>> That could simply be thought of as recursive invocation
>>>>>
>>>>> A kind of recursion, sure.  We can distinguish the following kinds:
>>>>>
>>>>> -  Recursive CALL
>>>>>     This is where function A /directly calls/ function A.  Or
>>>>>     we could extend it to cover A calls B which calls A again, etc.
>>>>>
>>>>> -  Recursive EMULATION.
>>>>>     This is where function A /EMULATES/ function A.  Or
>>>>>     we could extend it to cover A calls B which EMULATES A again, etc.
>>>>>
>>>>>> that is
>>>>>> functionally equivalent to this:
>>>>>>
>>>>>> int DebugTrace(u32 P, u32 I)
>>>>>> {
>>>>>>   ((int(*)(int))P)(I);
>>>>>>   return 1;
>>>>>> }
>>>>>>
>>>>>> void H_Hat(u32 P)
>>>>>> {
>>>>>>   u32 Aborted = DebugTrace(P, P);
>>>>>>   if (Aborted)
>>>>>>     HALT
>>>>>>   else
>>>>>>     HERE: goto HERE;
>>>>>> }
>>>>>>
>>>>>> int main()
>>>>>> {
>>>>>>   u32 P = (u32)H_Hat;
>>>>>>   DebugTrace(P, P);
>>>>>>   HALT;
>>>>>> }
>>>>>
>>>>> No, that is RECURSIVE CALL, no emulation.  The behaviour regarding
>>>>> infinite recursion is not the same, as I've been telling you.
>>>>>
>>>>> So far, all your explanations have only applied to a recursive call
>>>>> scenario....
>>>>>
>>>>> Mike.
>>>>>
>>>>
>>>> It is computationally equivalent.
>>>>
>>>> What about the price of tea in China?
>>>> Maybe we should factor that in too.
>>>
>>> It is not computationally equivalent, because in the case of recursive
>>> EMULATION, the outer emulation code has the ability to monitor and
>>> abort the inner emulations.  This is not possible in the case of
>>> recursive CALL.
>>>
>>> Mike.
>>
>>
>> Which you already agreed is only a difference in emulator behavior:
>> DebugTrace() or Halts() not a difference in emulated behavior: H_Hat().
>
> You have already shown you don't understand what I said, so it's really
> pointless harping back to that.
>
> What I said is that the SAME CALCULATION "comes out the same under
> different emulators".
>
> OK What are you saying here is "the SAME CALCULATION"?  And what are the
> two emulators?


void H_Hat(u32 P)
{
u32 Aborted = DebugTrace(P, P);
if (Aborted)
HALT
else
HERE: goto HERE;
}

int main()
{
u32 P = (u32)H_Hat;
DebugTrace(P, P);
HALT;
}



void H_Hat(u32 P)
{
u32 Aborted = Halts(P, P);
if (Aborted)
HALT
else
HERE: goto HERE;
}

int main()
{
u32 P = (u32)H_Hat;
Halts(P, P);
HALT;
}


These two calculations are verifiably identical until the second one
stops simulating H_Hat
(a) DebugTrace/H_Hat
(b) Halts/H_Hat


> Don't just say DebugTrace() and Halts() because you've
> had so many versions of everything I haven't a clue which one you mean
> now.  Probably by now you can just cut and paste the code (or at least
> the description).

DebugTrace() is identical to Halts() except that Halts stops simulating
its input and DebugTrace() does not stop simulating its input.

>>
>> If there is not a difference in emulated behavior then the decision of
>> Halts() to abort H_Hat() is examining the exact same execution trace of
>> H_Hat provided by DebugTrace().
>
> But IS there a difference in emulated behaviour? >
> Hmm, and suppose there is no difference, because you really do have a
> single calculation being emulated by two emulators - why would that mean
> your TEST is sound?  (Neither of us wants to go down a blind alley here...)
>
> Mike.
>
>


--
Copyright 2020 Pete Olcott

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