Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: wij <wyniijj5@gmail.com>
Newsgroups: comp.theory
Subject: Re: Every sufficiently competent C programmer knows
Date: Wed, 12 Mar 2025 03:32:02 +0800
Organization: A noiseless patient Spider
Lines: 66
Message-ID: <6c3556705e94cf5080c6e860a9b843d7cf786ae6.camel@gmail.com>
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>
MIME-Version: 1.0
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Injection-Date: Tue, 11 Mar 2025 20:32:03 +0100 (CET)
Injection-Info: dont-email.me; posting-host="920c9e6d430639ea994965ae553fae8b";
	logging-data="2255614"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+TCUJMW+WCZGBAJLHUR7F3"
User-Agent: Evolution 3.54.3 (3.54.3-1.fc41)
Cancel-Lock: sha1:gYj4iILvyBaowYv4oIYrN+sAVQI=
In-Reply-To: <vqq1j2$23vhr$2@dont-email.me>
Bytes: 3711

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.=C2=A0 However it's not very illuminating due to
> > > > bugs/design errors/misunderstandings which only serve to
> > > > obfuscate PO's errors in thinking.
> > >=20
> > > [I've now seen the code. Oh deary deary me.]
> > >=20
> > > Thank you for a spirited attempt to be cogent - or at least as
> > > cogent as it is possible to be in the circumstances!
> > >=20
> > > I think PO's first step must be to demonstrate that HHH()
> > > correctly diagnoses some easy functions, such as these:
> > >=20
> > > int rha(unsigned int i)
> > > {
> > > =C2=A0=C2=A0=C2=A0 while(--i > 0)while(--i > 0);
> > > =C2=A0=C2=A0=C2=A0 return 0;
> > > }
> > >=20
> > > int rhb(unsigned int i)
> > > {
> > > =C2=A0=C2=A0=C2=A0 if(i > 0)
> > > =C2=A0=C2=A0=C2=A0 {
> > > =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 rhb(i/10);
> > > =C2=A0=C2=A0=C2=A0 }
> > > =C2=A0=C2=A0=C2=A0 return putchar(i + '0');
> > > }
> > >=20
> > > int rhc(unsigned int i)
> > > {
> > > =C2=A0=C2=A0=C2=A0 typedef int(*pf)(unsigned int);
> > > =C2=A0=C2=A0=C2=A0 pf arr[3] =3D {rha, rhb, rhc};
> > > =C2=A0=C2=A0=C2=A0 return arr[i % 3];
> > > }
> > >=20
> > > and other such obvious tests.
> > >=20
> > > 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.
> > >=20
> >=20
> > No TM can simulate itself.
>=20
> It doesn't have to. For a start, it can take source code as input=20
> and analyse it in much the same way that a compiler does.

SO, what is 'it', the decider? (note: its input is the source of itself)

> > Proving HP in this way is dead end.
>=20
> Proving it any way is a dead end, because the answer to the=20
> Halting Problem is already known, and has been known since at=20
> least 1936.
>=20
> But if the OP is /going/ to write a decision function to attack=20
> the Halting Problem, he either writes a general purpose decision=20
> function or risks tackling the wrong problem.
>=20