Path: news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: wij <wyniijj5@gmail.com>
Newsgroups: sci.logic
Subject: Re: The execution trace of HHH1(DDD) shows the divergence
Date: Sat, 07 Jun 2025 22:53:31 +0800
Organization: A noiseless patient Spider
Lines: 148
Message-ID: <5ad51e66b8651614888e6412c246f0a5a7d3283b.camel@gmail.com>
References: <1021ii4$3327l$6@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Injection-Date: Sat, 07 Jun 2025 16:53:35 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="9bd70c4a0c87ec4ace2a3a7ed7005e97";
	logging-data="3276951"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18qZgIzEkjZI3y9bLkgU+p4"
User-Agent: Evolution 3.56.2 (3.56.2-1.fc42)
Cancel-Lock: sha1:GTdikfi1gH4HTS7yHsFEg6Jm9PA=
In-Reply-To: <1021ii4$3327l$6@dont-email.me>

On Sat, 2025-06-07 at 09:32 -0500, olcott wrote:
> The execution trace of HHH1(DDD) shows the divergence
> of DDD emulated by HHH from DDD emulated by HHH1.
>=20
> int main()
> {
> =C2=A0=C2=A0 HHH1(DDD);
> }
>=20
> Shows that DDD emulated by HHH and DDD emulated by
> HHH1 diverges as soon as HHH begins emulating itself
> emulating DDD.
>=20
> *From the execution trace of HHH1(DDD) shown below*
> DDD emulated by HHH1=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=
=A0=C2=A0=C2=A0=C2=A0=C2=A0 DDD emulated by HHH
> [00002183] push ebp=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 [00002183] push ebp
> [00002184] mov ebp,esp=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=
=A0=C2=A0=C2=A0 [00002184] mov ebp,esp
> [00002186] push 00002183 ; DDD=C2=A0=C2=A0=C2=A0 [00002186] push 00002183=
 ; DDD
> [0000218b] call 000015c3 ; HHH=C2=A0=C2=A0=C2=A0 [0000218b] call 000015c3=
 ; HHH
> *HHH1 emulates DDD once then HHH emulates DDD once, these match*
>=20
> The next instruction of DDD that HHH emulates is at
> the machine address of 00002183.
>=20
> The next instruction of DDD that HHH1 emulates is at
> the machine address of 00002190.
>=20
> 00002183 !=3D 00002190
>=20
> _DDD()
> [00002183] 55=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=
=C2=A0=C2=A0 push ebp
> [00002184] 8bec=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=
=A0 mov ebp,esp
> [00002186] 6883210000=C2=A0=C2=A0=C2=A0=C2=A0 push 00002183 ; push DDD
> [0000218b] e833f4ffff=C2=A0=C2=A0=C2=A0=C2=A0 call 000015c3 ; call HHH
> [00002190] 83c404=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 add esp=
,+04
> [00002193] 5d=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=
=C2=A0=C2=A0 pop ebp
> [00002194] c3=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=
=C2=A0=C2=A0 ret
> Size in bytes:(0018) [00002194]
>=20
> _main()
> [000021a3] 55=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=
=C2=A0=C2=A0 push ebp
> [000021a4] 8bec=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=
=A0 mov ebp,esp
> [000021a6] 6883210000=C2=A0=C2=A0=C2=A0=C2=A0 push 00002183 ; push DDD
> [000021ab] e843f3ffff=C2=A0=C2=A0=C2=A0=C2=A0 call 000014f3 ; call HHH1
> [000021b0] 83c404=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 add esp=
,+04
> [000021b3] 33c0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=
=A0 xor eax,eax
> [000021b5] 5d=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=
=C2=A0=C2=A0 pop ebp
> [000021b6] c3=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=
=C2=A0=C2=A0 ret
> Size in bytes:(0020) [000021b6]
>=20
> =C2=A0 machine=C2=A0=C2=A0 stack=C2=A0=C2=A0=C2=A0=C2=A0 stack=C2=A0=C2=
=A0=C2=A0=C2=A0 machine=C2=A0=C2=A0=C2=A0 assembly
> =C2=A0 address=C2=A0=C2=A0 address=C2=A0=C2=A0 data=C2=A0=C2=A0=C2=A0=C2=
=A0=C2=A0 code=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 language
> =C2=A0 =3D=3D=3D=3D=3D=3D=3D=3D=C2=A0 =3D=3D=3D=3D=3D=3D=3D=3D=C2=A0 =3D=
=3D=3D=3D=3D=3D=3D=3D=C2=A0 =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D =3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D
> <main is executed>
> [000021a3][0010382d][00000000] 55=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=
=A0=C2=A0 push ebp=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 ; main()
> [000021a4][0010382d][00000000] 8bec=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 m=
ov ebp,esp=C2=A0=C2=A0 ; main()
> [000021a6][00103829][00002183] 6883210000 push 00002183 ; push DDD
> [000021ab][00103825][000021b0] e843f3ffff call 000014f3 ; call HHH1
> </main is executed>
>=20
> New slave_stack at:1038d1
> Begin Local Halt Decider Simulation=C2=A0=C2=A0 Execution Trace Stored at=
:1138d9
>=20
> <DDD emulated by HHH1>
> [00002183][001138c9][001138cd] 55=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=
=A0=C2=A0 push ebp=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 ; DDD of HHH1
> [00002184][001138c9][001138cd] 8bec=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 m=
ov ebp,esp=C2=A0=C2=A0 ; DDD of HHH1
> [00002186][001138c5][00002183] 6883210000 push 00002183 ; push DDD
> [0000218b][001138c1][00002190] e833f4ffff call 000015c3 ; call HHH
> </DDD emulated by HHH1>
>=20
> New slave_stack at:14e2f9
> Begin Local Halt Decider Simulation=C2=A0=C2=A0 Execution Trace Stored at=
:15e301
>=20
> <DDD emulated by HHH>
> [00002183][0015e2f1][0015e2f5] 55=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=
=A0=C2=A0 push ebp=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 ; DDD of HHH[0]
> [00002184][0015e2f1][0015e2f5] 8bec=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 m=
ov ebp,esp=C2=A0=C2=A0 ; DDD of HHH[0]
> [00002186][0015e2ed][00002183] 6883210000 push 00002183 ; push DDD
> [0000218b][0015e2e9][00002190] e833f4ffff call 000015c3 ; call HHH
> <DDD emulated by HHH>
>=20
> New slave_stack at:198d21=C2=A0 DDD emulated by HHH
> *This is the beginning of the divergence of the behavior*
> *HHH is emulating itself emulating DDD, HHH1 never does that*
>=20
> <DDD emulated by HHH emulating itself>
> [00002183][001a8d19][001a8d1d] 55=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=
=A0=C2=A0 push ebp=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 ; DDD of HHH[1]
> [00002184][001a8d19][001a8d1d] 8bec=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 m=
ov ebp,esp=C2=A0=C2=A0 ; DDD of HHH[1]
> [00002186][001a8d15][00002183] 6883210000 push 00002183 ; push DDD
> [0000218b][001a8d11][00002190] e833f4ffff call 000015c3 ; call HHH
> </DDD emulated by HHH emulating itself>
>=20
> Local Halt Decider: Infinite Recursion Detected Simulation Stopped
> HHH returns to caller
>=20
> <DDD emulated by HHH1>
> [00002190][001138c9][001138cd] 83c404=C2=A0=C2=A0=C2=A0=C2=A0 add esp,+04=
 ; DDD of HHH1
> [00002193][001138cd][000015a8] 5d=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=
=A0=C2=A0 pop ebp=C2=A0=C2=A0=C2=A0=C2=A0 ; DDD of HHH1
> [00002194][001138d1][0003a980] c3=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=
=A0=C2=A0 ret=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 ; DDD of HHH1
> </DDD emulated by HHH1>
>=20
> <main is executed>
> [000021b0][0010382d][00000000] 83c404=C2=A0=C2=A0=C2=A0=C2=A0 add esp,+04=
 ; main()
> [000021b3][0010382d][00000000] 33c0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 x=
or eax,eax ; main()
> [000021b5][00103831][00000018] 5d=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=
=A0=C2=A0 pop ebp=C2=A0=C2=A0=C2=A0=C2=A0 ; main()
> [000021b6][00103835][00000000] c3=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=
=A0=C2=A0 ret=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 ; main()
> </main is executed>
> Number of Instructions Executed(352831) =3D=3D 5266 Pages

The HP is asking for such a H that H(D)=3D=3D1 iff D() halts.
You are always solving POO Problem.