Path: ...!weretis.net!feeder8.news.weretis.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Mikko <mikko.levanto@iki.fi>
Newsgroups: comp.theory
Subject: Re: Every D(D) simulated by H presents non-halting behavior to H
Date: Tue, 7 May 2024 10:30:17 +0300
Organization: -
Lines: 65
Message-ID: <v1cla9$34iis$1@dont-email.me>
References: <v18e32$1vbql$1@dont-email.me> <v1avuv$2lks2$1@dont-email.me> <v1b7gl$2ndka$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Tue, 07 May 2024 09:30:17 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="37b97af40bd85270c03ad38b8f6af776";
	logging-data="3295836"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+IVniKCc5nrZIvbvJwv+w3"
User-Agent: Unison/2.2
Cancel-Lock: sha1:hOeem/EYuNtn4tbHSWumOgJuR5s=
Bytes: 3398

On 2024-05-06 18:28:37 +0000, olcott said:

> On 5/6/2024 11:19 AM, Mikko wrote:
>> On 2024-05-05 17:02:25 +0000, olcott said:
>> 
>>> The x86utm operating system: https://github.com/plolcott/x86utm enables
>>> one C function to execute another C function in debug step mode.
>>> Simulating Termination analyzer H simulates the x86 machine code of its
>>> input (using libx86emu) in debug step mode until it correctly matches a
>>> correct non-halting behavior pattern proving that its input will never
>>> stop running unless aborted.
>>> 
>>> Can D correctly simulated by H terminate normally?
>>> 00 int H(ptr x, ptr x)  // ptr is pointer to int function
>>> 01 int D(ptr x)
>>> 02 {
>>> 03   int Halt_Status = H(x, x);
>>> 04   if (Halt_Status)
>>> 05     HERE: goto HERE;
>>> 06   return Halt_Status;
>>> 07 }
>>> 08
>>> 09 int main()
>>> 10 {
>>> 11   H(D,D);
>>> 12 }
>>> 
>>> *Execution Trace*
>>> Line 11: main() invokes H(D,D);
>>> 
>>> *keeps repeating* (unless aborted)
>>> Line 03: simulated D(D) invokes simulated H(D,D) that simulates D(D)
>>> 
>>> *Simulation invariant*
>>> D correctly simulated by H cannot possibly reach past its own line 03.
>>> 
>>> The above execution trace proves that (for every H/D pair of the
>>> infinite set of H/D pairs) each D(D) simulated by the H that this D(D)
>>> calls cannot possibly reach past its own line 03.
>> 
>> When you say "every H/D pair" you should specify which set of pairs
>> you are talking about. As you don't, your words don't mean anything.
>> 
> 
> Every H/D pair in the universe where D(D) is simulated by the
> same H(D,D) that D(D) calls. This involves 1 to ∞ steps of D
> and also includes zero to ∞ recursive simulations where H
> H simulates itself simulating D(D).

"In the universe" is not a set. In typical set theories like ZFC there
is no universal set.

Usually the best way to introduce a set of pairs is that first two
sets are specified and then a rule that selects some pairs from
the Cartesian product of those two sets.

In the current case the first set could be the set programs that
take two input values (possibly of some specific type) and returns
a Boolean value, and the second set could be programs that take
one input value (of the same type as the programs in the first set).
Or whatever best serves your purposes.

-- 
Mikko