Path: ...!news.mixmin.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail From: Mikko Newsgroups: comp.theory Subject: Re: Every D(D) simulated by H presents non-halting behavior to H ### Date: Fri, 17 May 2024 13:53:57 +0300 Organization: - Lines: 130 Message-ID: References: <-5Gdnf-nQvstC6b7nZ2dnZfqnPadnZ2d@brightview.co.uk> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Date: Fri, 17 May 2024 12:53:57 +0200 (CEST) Injection-Info: dont-email.me; posting-host="dbf1b225f2871bff3da7815f4eb7b472"; logging-data="2277696"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+/ifFPB7JhCdD4r7dWC05n" User-Agent: Unison/2.2 Cancel-Lock: sha1:156GlSmnbEOdQ9BcmphS4ojpmuw= Bytes: 5973 On 2024-05-16 14:50:19 +0000, olcott said: > On 5/16/2024 5:48 AM, Mikko wrote: >> On 2024-05-15 15:24:57 +0000, olcott said: >> >>> On 5/15/2024 3:18 AM, Mikko wrote: >>>> On 2024-05-14 14:35:42 +0000, olcott said: >>>> >>>>> On 5/14/2024 4:52 AM, Mikko wrote: >>>>>> On 2024-05-13 14:43:09 +0000, olcott said: >>>>>> >>>>>>> On 5/13/2024 4:14 AM, Mikko wrote: >>>>>>>> On 2024-05-13 04:54:30 +0000, immibis said: >>>>>>>> >>>>>>>>> On 10/05/24 19:55, Alan Mackenzie wrote: >>>>>>>>>> [ Followup-To: set ] >>>>>>>>>> >>>>>>>>>> In comp.theory olcott wrote: >>>>>>>>>> >>>>>>>>>> [ .... ] >>>>>>>>>> >>>>>>>>>> I've tried out your much spammed code on GCC (see below).  It is clear >>>>>>>>>> you have never built or run this code, which ironically can't reach Line >>>>>>>>>> 06.  It can't even reach line 00. >>>>>>>>>> >>>>>>>>>>> Richard tried to get away with D never simulated by H as an example >>>>>>>>>>> of D simulated by H: >>>>>>>>>> >>>>>>>>>>> Message-ID: >>>>>>>>>>> On 5/1/2024 7:28 PM, Richard Damon wrote: >>>>>>>>>> >>>>>>>>>>> *That people say they know I am wrong yet will not show the detailed* >>>>>>>>>>> *steps of how I am wrong indicates that they are probably liars* >>>>>>>>>> >>>>>>>>>> You have said, or at least implied that your code fragment is runnable. >>>>>>>>>> I think you are the liar, here. >>>>>>>>>> >>>>>>>>>>> 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 } >>>>>>>>>> >>>>>>>>>> >>>>>>>>>> .  These are the diagnostics generated by GCC: >>>>>>>>>> >>>>>>>>> And the halting problem is about Turing machines, anyway. >>>>>>>> >>>>>>>> Not necessarily. The same question can be asked about different machines. >>>>>>>> The restriction to Turing machines is just one way to ensure that the >>>>>>>> problem is well defined. >>>>>>>> >>>>>>> >>>>>>> Well put. All computable functions even if written in C. >>>>>> >>>>>> You still must ensure that the problem is well defined. With C there is >>>>>> the problem that conforming C programs often fail to be strictly conforming. >>>>>> If a program is not strictly conforming it may be interpreted as halting >>>>>> by some implementation and non-halting or incorrect by another. >>>>>> >>>>> >>>>> 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 } >>>>> >>>>> One can correctly determine that every D simulated by H >>>>> never reaches past its own line 03. >>>> >>>> That is not strictly conforming and hardly conforming at all. >>>> >>> >>> What trivial syntactic error that has no effect >>> what-so-ever on the semantics do you believe remains? >> >> A trivial sysntactic error means that the program is not strictly >> conforming. It may be conforming if some liberal compiler accepts >> it. >> >>> A missing semi-colon? >> >> Normal semantics is that the program is not executed. >> >>> 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 } >> >> Can you find any compiler that is liberal enough to accept that? >> > > It has been fully operational code under Windows and > Linux for two years. If your compiler does not reject that program it is not a conforming C compiler. The semantics according to C standard is that a diagnostic message must be given. The standard does not specify what happens if you execute that program anyway. -- Mikko