Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail From: olcott Newsgroups: comp.lang.c Subject: D correctly simulated by H cannot possibly reach its own line 06 Date: Sat, 18 May 2024 14:10:45 -0500 Organization: A noiseless patient Spider Lines: 69 Message-ID: References: <87jzjrkkmq.fsf@nosuchdomain.example.com> MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit Injection-Date: Sat, 18 May 2024 21:10:45 +0200 (CEST) Injection-Info: dont-email.me; posting-host="95afb1fc0a4871125108def5044e156a"; logging-data="3076902"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19vo3xg/TjjCXNsubajvvYc" User-Agent: Mozilla Thunderbird Cancel-Lock: sha1:e5d2TG62FHImPeq/242uM6UyPUw= In-Reply-To: <87jzjrkkmq.fsf@nosuchdomain.example.com> Content-Language: en-US Bytes: 3974 On 5/18/2024 2:03 PM, Keith Thompson wrote: > James Kuyper writes: > [...] >> "Undefined behavior" is a piece of C jargon. You cannot understand the >> meaning of the term by treating it as an ordinary English phrase: >> "behavior which has no definition'. > [...] >> This is important, because strictly conforming code cannot >> have undefined behavior. If the C standard has no definition for the >> behavior of some code, it cannot be strictly conforming, even if some >> other document does define the behavior. > [...] > > It's also important to note that "strictly conforming" is a piece of C > jargon. I don't know (or care) whether strict conformance is relevant > to the discussion that should have stayed in comp.theory. > > If something in comp.theory raises a question about C, I suggest > starting a new thread in comp.lang.c rather than cross-posting. > > Followups redirected back to comp.theory. > People are saying that they have no idea what this code does because they do not believe it conforms to c11 or c17. typedef int (*ptr)(); // ptr is pointer to int function 00 int H(ptr x, ptr y); 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 return 0; 13 } In the above case a simulator is an x86 emulator that correctly emulates at least one of the x86 instructions of D in the order specified by the x86 instructions of D. This may include correctly emulating the x86 instructions of H in the order specified by the x86 instructions of H thus calling H(D,D) in recursive simulation. *Execution Trace* Line 11: main() invokes H(D,D); *keeps repeating* (unless aborted) Line 01: Line 02: 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 key thing to note is that no D correctly simulated by any H of every H/D pair specified by the above template ever reaches its own line 06 and halts. -- Copyright 2024 Olcott "Talent hits a target no one else can hit; Genius hits a target no one else can see." Arthur Schopenhauer