Re: Liar detector: Fred, Richard, Joes and Alan --- Ben's agreement

Op 08.jul.2024 om 19:36 schreef olcott:

On 7/8/2024 11:16 AM, Fred. Zwarts wrote:

Op 08.jul.2024 om 18:07 schreef olcott:

On 7/8/2024 11:04 AM, Fred. Zwarts wrote:

Op 08.jul.2024 om 17:04 schreef olcott:

On 7/8/2024 9:25 AM, Fred. Zwarts wrote:

Op 07.jul.2024 om 15:46 schreef olcott:

>
Correctly is measured by the semantics of the x86 language.
This specifies that when DDD is correctly simulated by HHH
calls emulated HHH(DDD) that this call cannot return.

>
Yes. This shows that the simulation is incorrect.
>

>
You smash a bottle on the ground. No matter how much you
want the bottle to hold water it will not hold water.

>
Similarly, HHH cannot possibly simulate itself correctly, no matter how much you want it to be correct,

>
Where correct is understood to be what-ever-the-Hell that the
machine code of DDD specifies within the semantics of the x86
language then:
>
When DDD is correctly simulated by any pure function x86 emulator
HHH that aborts its emulation at some point calls HHH(DDD) then
it is correctly understood that this call cannot possibly return.
The proof of this is something like mathematical induction.
>
When DDD is correctly emulated by any HHH that aborts
its emulation after N repetitions:
(1) DDD is correctly emulated by HHH

>
But only the first part is simulated, not the full input. The simulation must simulate the full input. It will will only become correct if also the other behaviour of HHH is simulated. But HHH is unable to simulate itself up to that point.
That is what the x86 code specifies.
>

(2) that calls an emulated HHH(DDD) that
(3) emulates another DDD... goto (2) or abort

>
And when it aborts, it is one cycle to soon.

>
Try to show how infinity is one cycle too soon.
>

You believe that two equals infinity.

 void Infinite_Loop()
{
   HERE: goto HERE;
}
 void Infinite_Recursion()
{
   Infinite_Recursion();
}
 void DDD()
{
   HHH(DDD);
}
 Two cycles is enough to correctly determine that none
of the above functions correctly emulated by HHH can
possibly halt.
 That you don't see this is ignorance or deception.
 

The first two irrelevant examples cannot halt, but they differ fundamentally from DDD, because DDD, like Finite_Recursion, halts after N repetitions.
void Finite_Recursion (int N) {
   if (N > 0) Finite_Recursion (N - 1);
}
DDD, is is an unneeded complication, the simple case is:
        int main()
        {
          return H(main, 0);
        }
Yes, your are right that HHH cannot possibly simulate itself correctly. That is because HHH aborts after simulating two cycles of itself. Then it aborts. It does not simulate the full behaviour of the input, which would abort and return one cycle later. So, it misses the most important part of itself, namely, that it aborts and returns.
It assumes that two cycles are equivalent to an infinite number of cycles, which, of course, is an invalid assumption.
TWO DOES NOT EQUAL INFINITY!
That makes the simulation incorrect. A simulation must process the full input, not only the first part, in particular when the last part halts by its own and does not need an abort.
You have shown that other simulators are able to show that a correct simulation of HHH halts.
It is only HHH that cannot possibly simulate itself correctly.
This is supported by your claim that the simulation cannot possibly reach the 'ret' instruction.
It is also supported by the full trace, you published, where we see that the x86 code of the simulated HHH is not completely simulated, but aborted one cycle too early.
So, this incorrect simulation cannot be used to get support from Sipser, who only spoke about a correct simulation.