Path: ...!3.eu.feeder.erje.net!feeder.erje.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 correctly simulated by H never reaches its final state and halts
Date: Sat, 18 May 2024 12:53:49 +0300
Organization: -
Lines: 84
Message-ID: <v29trd$2nq7m$1@dont-email.me>
References: <v26b2t$1rdu0$1@dont-email.me> <v270q1$22vhs$1@dont-email.me> <v27t5q$28hmg$2@dont-email.me> <v2855m$2a6vf$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Sat, 18 May 2024 11:53:49 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="09f5db4735dcda801e35839cc47e3f1d";
	logging-data="2877686"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18DgLIybOrttYbMRreRFiGb"
User-Agent: Unison/2.2
Cancel-Lock: sha1:zgsH6S2RowpnLtprFW8B7lgOuDI=
Bytes: 4142

On 2024-05-17 17:46:29 +0000, olcott said:

> On 5/17/2024 11:00 AM, Mikko wrote:
>> On 2024-05-17 15:30:01 +0000, olcott said:
>> 
>>> On 5/17/2024 2:25 AM, Fred. Zwarts wrote:
>>>> Op 17.mei.2024 om 03:15 schreef olcott:
>>>>> The following is self-evidently true on the basis of the
>>>>> semantics of the C programming language.
>>>>> 
>>>>> typedef int (*ptr)();  // ptr is pointer to int function
>>>>> 00 int H(ptr x, ptr x);
>>>>> 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.
>>>>> 
>>>>> Any H/D pair matching the above template where
>>>>> D(D) is simulated by the same H(D,D) that it calls
>>>>> cannot possibly reach its own line 06 and halt.
>>>>> 
>>>>> *This is a simple software engineering verified fact*
>>>>> 
>>>> 
>>>> Note that olcott defines 'verified fact' as 'proven fact', but he is 
>>>> unable to show the proof. So, it must be read as 'my belief'.
>>> 
>>> It is self-evidently true to anyone having sufficient knowledge
>>> of the semantics of the C programming language.
>> 
>> No, it isn't, because the C code of H is not shown.
> 
> *I DON'T KNOW WHY I MUST REPEAT THIS HUNDREDS OF TIMES*
> The C code that <is> shown provides the template for the
> infinite set of every D correctly simulated by H.
> 
>> The actual
>> implementation of H as decribed in some earlier messages is
>> not fully encoded in standard C, so in order to understand the
>> behaviour of D one needs to know and understand something that
>> is not given as a C code and therefore not understandable from
>> mere knowing the C language definition.
>> 
> 
> *SUFFICIENTLY KNOWING THE SEMANTICS OF C*
> *SUFFICIENTLY KNOWING THE SEMANTICS OF C*
> *SUFFICIENTLY KNOWING THE SEMANTICS OF C*
> 
> I could cast uint32_t to and from the various function pointer
> types yet this is more difficult for people to understand.

Such casts are not permitted by the C standard. They may be
allowed by some compilers as an extension to C.

> I got complaints about this.
> It is simpler and easier to do this: typedef int (*ptr)();

The C standard does not permit reading the memory with a pointer
of this type nor a cast to another type that would permit such
reading. As simulation requires reading, this prevents all simulation
of the code. A compiler may allow casting to another type that
can be used for simulation as an extension to C. The C standard
is quite liberal about implementation specific extensions.

-- 
Mikko