Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail From: Richard Heathfield Newsgroups: comp.theory Subject: Re: Every sufficiently competent C programmer knows Date: Tue, 11 Mar 2025 19:06:10 +0000 Organization: Fix this later Lines: 67 Message-ID: References: MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Date: Tue, 11 Mar 2025 20:06:10 +0100 (CET) Injection-Info: dont-email.me; posting-host="e140e83e0fdcc599ec997207e186ae4a"; logging-data="2227771"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+Fn84YG2LLLutYfRUCk5rlg78eqGWmfPcKxz068K+wqw==" User-Agent: Mozilla Thunderbird Cancel-Lock: sha1:Zztajt/XfQLSwPJ39CFStr6buHM= In-Reply-To: Content-Language: en-GB Bytes: 3353 On 11/03/2025 18:33, wij wrote: > On Tue, 2025-03-11 at 18:23 +0000, Richard Heathfield wrote: >> On 11/03/2025 17:42, Mike Terry wrote: >>> Finally, if you really want to see the actual HHH code, its in >>> the halt7.c file (along with DDD) that PO provides links to from >>> time to time.  However it's not very illuminating due to >>> bugs/design errors/misunderstandings which only serve to >>> obfuscate PO's errors in thinking. >> >> [I've now seen the code. Oh deary deary me.] >> >> Thank you for a spirited attempt to be cogent - or at least as >> cogent as it is possible to be in the circumstances! >> >> I think PO's first step must be to demonstrate that HHH() >> correctly diagnoses some easy functions, such as these: >> >> int rha(unsigned int i) >> { >>    while(--i > 0)while(--i > 0); >>    return 0; >> } >> >> int rhb(unsigned int i) >> { >>    if(i > 0) >>    { >>      rhb(i/10); >>    } >>    return putchar(i + '0'); >> } >> >> int rhc(unsigned int i) >> { >>    typedef int(*pf)(unsigned int); >>    pf arr[3] = {rha, rhb, rhc}; >>    return arr[i % 3]; >> } >> >> and other such obvious tests. >> >> HHH(), the procedure that decides whether a program halts, is >> required to work for all programs and all inputs. Does it work on >> those cited above? I'm guessing it doesn't. >> > > No TM can simulate itself. It doesn't have to. For a start, it can take source code as input and analyse it in much the same way that a compiler does. > Proving HP in this way is dead end. Proving it any way is a dead end, because the answer to the Halting Problem is already known, and has been known since at least 1936. But if the OP is /going/ to write a decision function to attack the Halting Problem, he either writes a general purpose decision function or risks tackling the wrong problem. -- Richard Heathfield Email: rjh at cpax dot org dot uk "Usenet is a strange place" - dmr 29 July 1999 Sig line 4 vacant - apply within