Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Mikko <mikko.levanto@iki.fi>
Newsgroups: comp.theory,  comp.lang.c
Subject: Re: Every D(D) simulated by H presents non-halting behavior to H ###
Date: Sat, 18 May 2024 16:02:41 +0300
Organization: -
Lines: 153
Message-ID: <v2a8th$2ps09$1@dont-email.me>
References: <v18e32$1vbql$1@dont-email.me> <v1avuv$2lks2$1@dont-email.me> <v1b7gl$2ndka$1@dont-email.me> <v1cla9$34iis$1@dont-email.me> <v1d2mi$9f72$11@i2pn2.org> <v1di1h$3b2m5$1@dont-email.me> <v1dtdv$3dqg4$1@dont-email.me> <v1du2i$3dt7u$1@dont-email.me> <v1fetd$3s7jo$1@dont-email.me> <v1ft42$3vdau$2@dont-email.me> <-5Gdnf-nQvstC6b7nZ2dnZfqnPadnZ2d@brightview.co.uk> <v1gid8$4ilc$1@dont-email.me> <v1h9eu$9faf$1@dont-email.me> <v1iqli$nsva$1@dont-email.me> <v1ln3c$vfh$1@news.muc.de> <v1s6e6$397iq$2@dont-email.me> <v1slmi$3cjtp$1@dont-email.me> <v1t8tt$3gu9t$3@dont-email.me> <v1vc8j$3jmr$1@dont-email.me> <v1vsru$7eqc$1@dont-email.me> <v21r4i$otc2$2@dont-email.me> <v22k4b$umr4$1@dont-email.me> <v24oah$1h4u3$1@dont-email.me> <v256fc$1kais$1@dont-email.me> <v27d05$25ga0$1@dont-email.me> <v2838r$29rd7$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 15:02:42 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="48864972f4821b7340d511423b46b671";
	logging-data="2945033"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/vBDp4FPTV8Z0nWxHZpFO9"
User-Agent: Unison/2.2
Cancel-Lock: sha1:rXfETfSPfq4SthmunpPx2LcTErc=
Bytes: 7151

On 2024-05-17 17:14:01 +0000, olcott said:

> On 5/17/2024 5:53 AM, Mikko wrote:
>> 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 <polcott333@gmail.com> 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: <v0ummt$2qov3$2@i2pn2.org>
>>>>>>>>>>>>> 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.
>> 
> 
> It is not nit picky syntax that is the issue here.
> The SEMANTICS OF THE C PROGRAMMING LANGUAGE SPECIFIES
> 
> No D simulated correctly by any H of every H/D pair specified
> by the above template ever reaches its own line 06 and halts.

The standard allows that an program is executed but does not
specify what happens when an invalid program is executed.

> Fully operational software that runs under Widows and Linux
> proves that the above is true EMPIRICALLY.

No, it does not. As the program is not strictly comforming
and uses a non-standard extension some implementation may
execute it differently or refuse to execute.

Of course, in an implementation that refuses to execute the
simulation can not reach the line 06 or any other line.

-- 
Mikko