Path: ...!Xl.tags.giganews.com!local-3.nntp.ord.giganews.com!nntp.brightview.co.uk!news.brightview.co.uk.POSTED!not-for-mail
NNTP-Posting-Date: Tue, 11 Mar 2025 20:37:08 +0000
Subject: Re: Every sufficiently competent C programmer knows
Newsgroups: comp.theory
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>
From: Mike Terry <news.dead.person.stones@darjeeling.plus.com>
Date: Tue, 11 Mar 2025 20:37:04 +0000
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
 Firefox/91.0 SeaMonkey/2.53.18.2
MIME-Version: 1.0
In-Reply-To: <vqpv2u$23vhr$1@dont-email.me>
Content-Type: text/plain; charset=windows-1252; format=flowed
Content-Transfer-Encoding: 8bit
Message-ID: <Ny-dnRlMHcVpA036nZ2dnZfqnPqdnZ2d@brightview.co.uk>
Lines: 87
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-MJrdG/KDc8XkFkS2bzxbovmKoYpZVEwg6VZY/EQcT8ODFTpB/O68yYS3Et9x6HeT+1Wz9tWyCLf6qVl!MsNrEF05dC5Z23b2WgDkJeQmOz8U3BeOF5SfuSwPIr+A9F02h/lb/cYGu9TGDL2uSNdReCi723yu!nVu4UgwMwv9vTcTqiOo52UKp96U=
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly
X-Postfilter: 1.3.40
Bytes: 5339

On 11/03/2025 18:23, 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:

Not really necessary - PO is not trying or claiming to have a (full) halt decider.

Originally his claim was that he had a program which worked for the counter-example TM used in the 
common (e.g. Linz book) proof.  Such a program is impossible, as Linz and others prove, so having a 
program H and its corresponding "counter-example" D, such that H correctly decides D, would 
certainly show that the Linz proof is wrong.  His claim was always that he had "refuted the HP 
proof", or sometimes that he had refuted the HP theorem itself although he's been told dozens of 
times that there are many alternative proofs for the result.

[As it turned out, PO's D(D) halted when run under his x86utm environment, while H(D,D) which is 
required to return the halting status of computation D(D) returned 0 (=non-halting).  That is 
exactly what the Linz proofs claim!]

Anyhow, his decider only /has/ to correctly decide the one input, which is the D constructed from H 
by the usual method (basically D calls H to see what H claims is the halting behaviour, then does 
the opposite - I'm not sure if you're familiar with the proof, but imagine you would be given your 
background).

His decider H works (subject to design errors/bugs and so on) by single-stepping a simulation of its 
input computation, and monitoring for conditions that PO believes indicate non-termination.  He 
tests a couple of conditions, and when one of those matches H aborts and returns non-halting. 
Alternatively if the simulation halts normally, H returns halting.  The problem is (at least) one of 
his non-halting-behaviour tests is invalid, matching during the simulation of DDD, which is a 
halting computation.

It is true that sometimes his tests match and the input is indeed non-halting.  PO quotes this as 
evidence that his tests "work", so when the decided non-halting for a halting computation they must 
be correct and the halting computation in fact is non-halting because it "exhibited non-halting 
behaviour"!


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

I would have to think a bit about your examples - or more likely just try them out (which I'm not 
motivated to do).  PO's non-halting tests involve observing loops and conditional branches in some 
combination.  The major problem for his HHH/DDD is with the simulation aspect - the tests can match 
when the same code address is reached but across completely different simulation levels.  PO does 
not appreciate that tests which /might/ work in a non-simulation setting, could go horribly wrong 
when simulation is involved...  (so your tests aren't especially relevant for PO's code logic - and 
as I said there is only the one case that he really has to handle.)

Mike.