Path: news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail From: Keith Thompson Newsgroups: comp.theory Subject: Re: Incorrect requirements --- Computing the mapping from the input to HHH(DD) Date: Thu, 08 May 2025 15:26:16 -0700 Organization: None to speak of Lines: 235 Message-ID: <87msbmeo3b.fsf@nosuchdomain.example.com> References:

MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit Injection-Date: Fri, 09 May 2025 00:26:17 +0200 (CEST) Injection-Info: dont-email.me; posting-host="302a6dd640940106301f9e87fdade96e"; logging-data="2264471"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+kVfkXB9Z2a0STmMUPcHds" User-Agent: Gnus/5.13 (Gnus v5.13) Cancel-Lock: sha1:dXEGzSpd7/VqTQI5PnqkoY4ABeE= sha1:38fmg9mY0RNbG95fAvFyqpefXvQ= Mr Flibble writes: > On Thu, 08 May 2025 21:01:42 +0100, Richard Heathfield wrote: > >> On 08/05/2025 20:42, olcott wrote: >>> On 5/8/2025 2:04 PM, Fred. Zwarts wrote: >>>> Op 08.mei.2025 om 19:00 schreef olcott: >>>>> On 5/8/2025 11:14 AM, Mike Terry wrote: >>>>>> On 08/05/2025 06:33, Richard Heathfield wrote: >>>>>>> On 08/05/2025 06:22, olcott wrote: >>>>>>>> On 5/7/2025 11:09 PM, Richard Heathfield wrote: >>>>>>>>> On 08/05/2025 02:20, olcott wrote: >>>>>>>>> >>>>>>>>> >>>>>>>>> >>>>>>>>>> Does there exist an HHH such that DDD emulated by HHH according >>>>>>>>>> to the rules of the C programming language >>>>>>>>> >>>>>>>>> Let's take a look. >>>>>>>>> >>>>>>>>> The file is 1373 lines long, but don't worry, because I plan to >>>>>>>>> stop at HHH's first departure from the rules of the C programming >>>>>>>>> language (or at least the first departure I spot). >>>>>>>>> >>>>>>>>> Turn in your songbook if you will to: >>>>>>>>> >>>>>>>>> void CopyMachineCode(u8* source, u8** destination) >>>>>>>>> { >>>>>>>>> u32 size; >>>>>>>>> for (size = 0; source[size] != 0xcc; size++) >>>>>>>>> ; >>>>>>>>> *destination = (u8*) Allocate(size); >>>>>>>>> for (u32 N = 0; N < size; N++) >>>>>>>>> { >>>>>>>>> Output("source[N]: ", source[N]); >>>>>>>>> *destination[N] = source[N]; >>>>>>>>> } >>>>>>>>> ((u32*)*destination)[-1] = size; Output("CopyMachineCode >>>>>>>>> destination[-1]: ", >>>>>>>>> ((u32*)*destination) [-1]); >>>>>>>>> Output("CopyMachineCode destination[-2]: ", >>>>>>>>> ((u32*)*destination) [-2]); >>>>>>>>> }; >>>>>>>>> >>>>>>>>> >>>>>>>> deprecated. >>>>>>> >>>>>>> It's not just deprecated. It's hopelessly broken. >>>>>>> >>>>>>> Everybody makes mistakes, and one slip would be all very well, but >>>>>>> you make essentially the same mistake --- writing to memory that >>>>>>> your program doesn't own --- no fewer than four times in a single >>>>>>> function. >>>>>>> >>>>>>>>> I'll ignore the syntax error (a null statement at file scope is a >>>>>>>>> rookie error). >>>>>>>>> >>>>>>>>> Instead, let's jump straight to this line: >>>>>>>>> >>>>>>>>> *destination = (u8*) Allocate(size); >>>>>>>>> >>>>>>>>> On line 79 of my copy of the code, we find: >>>>>>>>> >>>>>>>>> u32* Allocate(u32 size) { return 0; } >>>>>>>>> >>>>>>>>> In C, 0 is a null pointer constant, so Allocate returns a null >>>>>>>>> pointer constant... which is fine as long as you don't try to >>>>>>>>> deref it. So now *destination is NULL. >>>>>>>>> >>>>>>>>> We go on: >>>>>>>>> >>>>>>>>> for (u32 N = 0; N < size; N++) >>>>>>>>> { >>>>>>>>> Output("source[N]: ", source[N]); >>>>>>>>> *destination[N] = source[N]; >>>>>>>>> } >>>>>>>>> >>>>>>>>> *destination[N] is our first big problem (we're ignoring syntax >>>>>>>>> errors, remember). destination is a null pointer, so >>>>>>>>> destination[N] derefs a null pointer. >>>>>>>>> >>>>>>>>> That's a fail. 0/10, D-, go away and write it again. And you / >>>>>>>>> dare/ to impugn other people's C knowledge! Crack a book, for >>>>>>>>> pity's sake. >>>>>>>>> >>>>>>>>> >>>>>>>> If you can't even understand what is essentially an infinite >>>>>>>> recursive relationship between two functions except that one >>>>>>>> function can terminate the other then you don't have a clue about >>>>>>>> the essence of my system. >>>>>>> >>>>>>> If you can't even understand why it's a stupendously bad idea to >>>>>>> dereference a null pointer, you have no business trying to teach >>>>>>> anyone anything about C. >>>>>>> >>>>>>> Your code is the work of a programmer so hideously incompetent that >>>>>>> 'programmer' is scarcely a fair word to use. >>>>>>> >>>>>>> When you publish code like that, to even *think* about denigrating >>>>>>> other people's C knowledge is the height of arrogant hypocrisy. >>>>>>> >>>>>> One problem here is that you don't understand how PO's code works. >>>>>> That's to be expected, and PO's response ought to be to explain it >>>>>> so that you understand. Instead he goes off on one of his rants, so >>>>>> blamewise it's really down to PO. >>>>>> >>>>>> PO's halt7.c is compiled (it is not linked), then the obj file is >>>>>> fed as input to his x87utm.exe which is a kind of x86 obj code >>>>>> execution environment. x87utm provides a number of primative calls >>>>>> that halt7.c code can make, such as Allocate(), used to allocate a >>>>>> block of memory for use in halt7.c. Within halt7.c code calls an >>>>>> Allocate() function, and x86utm intercepts that and performs the >>>>>> function internally, then jumps the calling code in halt7.c over the >>>>>> Allocate call where it continues as normal. The call never goes to >>>>>> the implementation of Allocate in halt7.c, so the null pointer >>>>>> dereferencing does not actually occur. There are a whole bunch of >>>>>> similar x86utm primitive operations that work in the same way. >>>>>> >>>>>> PO should have said all that, not me, but it seems he's not >>>>>> interested in genuine communication. >>>>>> >>>>>> Mike. >>>>>> >>>>>> >>>>>> >>>>> Thanks for those details, they are correct. >>>>> I try to stay focused on the key essence gist of the issue and never >>>>> delve down into the weeds. >>>>> >>>>> int DD() >>>>> { >>>>> int Halt_Status = HHH(DD); >>>>> if (Halt_Status) >>>>> HERE: goto HERE; >>>>> return Halt_Status; >>>>> } >>>>> >>>>> The key gist of the issue (no weeds involved) >>>>> is that HHH emulated DD according to the rules of the x86 language >>>>> >>>>> >>>>> *until H correctly determines that* >>>>> *its simulated D would never stop running unless aborted* >>>>> >>>> 10/13/2022> >>>> >>>> And since H does not correctly determine that its simulated D would >>>> never stop running unless aborted, it is a vacuous statement and >>>> Sipser's agreement does not tell anything. >>>> >>>> >>> That is counter factual as any fully qualified C programmer will tell >>> you. >> >> As any competent C programmer can tell you, your simulation is driven by >> assembly language, not C. Furthermore, neither halt7.c nor x86utm.cpp is >> syntactically correct C. Once you fix the syntax errors, that still >> leaves you with the undefined behaviour. > > I don't believe the C ISO Standard explictly states that stack overflow is > undefined behaviour however even if it did Flibble's Law applies: if a UTM > is allowed infinite tape then the simulating halt decider is allowed > infinite resources (stack space). How is that relevant? Nobody was talking about stack overflow. The standard does say that it does not specify "the size or complexity of a program and its data that will exceed the capacity of any specific data-processing system or the capacity of a particular processor". It doesn't explicitly say that a program that exceeds the system's capacity has undefined behavior, but "Undefined behavior is otherwise indicated in this document by the words "undefined ========== REMAINDER OF ARTICLE TRUNCATED ==========