Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: Richard Heathfield <rjh@cpax.org.uk>
Newsgroups: comp.theory
Subject: Re: Every sufficiently competent C programmer knows
Date: Tue, 11 Mar 2025 19:49:10 +0000
Organization: Fix this later
Lines: 80
Message-ID: <vqq43m$23vhr$3@dont-email.me>
References: <vqntaq$1jut5$1@dont-email.me> <vqp388$1tvqa$1@dont-email.me>
 <vqpdv9$202b2$2@dont-email.me> <vqperb$20c9k$2@dont-email.me>
 <E6mcnWv3nMa66036nZ2dnZfqnPWdnZ2d@brightview.co.uk>
 <vqpv2u$23vhr$1@dont-email.me>
 <a3304ec1dc4a774e1570a5bcaee4732327635974.camel@gmail.com>
 <vqq1j2$23vhr$2@dont-email.me>
 <6c3556705e94cf5080c6e860a9b843d7cf786ae6.camel@gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Tue, 11 Mar 2025 20:49:11 +0100 (CET)
Injection-Info: dont-email.me; posting-host="e140e83e0fdcc599ec997207e186ae4a";
	logging-data="2227771"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/0Wb50v/1kkDz7nvnNEd+CWW3gTi2qx61WEJZlQ4Lc4g=="
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:WYUXUL0aN/FVqb2TGm1bBL3nD+g=
In-Reply-To: <6c3556705e94cf5080c6e860a9b843d7cf786ae6.camel@gmail.com>
Content-Language: en-GB
Bytes: 3946

On 11/03/2025 19:32, wij wrote:
> On Tue, 2025-03-11 at 19:06 +0000, Richard Heathfield wrote:
>> 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.
> 
> SO, what is 'it', the decider?

Yes. `It' is the program that determines whether an input program 
(fed in at runtime) will halt when supplied with data also fed in 
at run time.

> (note: its input is the source of itself)

No. Its input is /any/ program. Yes, it must be able to handle 
itself (or its own source, if it works on source code), but a 
decider that can only handle itself is trivial to write, and it 
doesn't even have to read the source:

int halts(struct source *s)
{
   return 1;
}

Gee, that was hard. But it doesn't address the Halting Problem. A 
general decider is required, and HHH() isn't one.

-- 
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