Path: news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: Richard Heathfield <rjh@cpax.org.uk>
Newsgroups: comp.theory
Subject: Re: Bad faith and dishonesty
Date: Fri, 30 May 2025 11:24:41 +0100
Organization: Fix this later
Lines: 115
Message-ID: <101c11c$eeca$1@dont-email.me>
References: <m99YP.725664$B6tf.610565@fx02.ams4>
 <100uct4$184ak$1@dont-email.me> <100v9ta$1d5lg$7@dont-email.me>
 <1011eai$1urdm$1@dont-email.me> <10121bt$22da5$4@dont-email.me>
 <8bb5266e35845a4d8f2feb618c0c18629c04e4e7@i2pn2.org>
 <1012oj1$278f8$1@dont-email.me>
 <1196d9de2e2aebc1b6d1a85047192e8ea1aeb1f1@i2pn2.org>
 <10137lv$2djeu$1@dont-email.me> <ewIZP.135645$vK4b.131815@fx09.ams4>
 <1017l6l$3cerk$1@dont-email.me> <1017tr1$3drlu$5@dont-email.me>
 <1017ufm$3e54m$6@dont-email.me> <1019vm1$3u8nj$3@dont-email.me>
 <101a65n$3vsp7$1@dont-email.me> <101a86h$3vfam$6@dont-email.me>
 <101a9np$gl7$1@dont-email.me> <101bt7o$58on$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Fri, 30 May 2025 12:24:44 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="98821b3aa39a3256f5c8c5614ee01f20";
	logging-data="473482"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/cHxZlHXMSLXGJZfjnr/lNeOVUeHkmJRXVX9DlrcVJDA=="
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:NIrg7pzMQXCDLc6K4mrz9A00nC4=
In-Reply-To: <101bt7o$58on$1@dont-email.me>
Content-Language: en-GB

On 30/05/2025 10:19, vallor wrote:
> On Thu, 29 May 2025 19:40:57 +0100, Richard Heathfield <rjh@cpax.org.uk>
> wrote in <101a9np$gl7$1@dont-email.me>:
> 
>> On 29/05/2025 19:14, olcott wrote:

<snip>

>>>
>>> It is a tautology that any input D to termination analyzer H that
>>> *would never stop running unless aborted*
>>> DOES SPECIFY NON-TERMINATING BEHAVIOR.
>>
>> But in making that claim you assume that you correctly know the
>> termination behaviour of D.
>>
>> I can easily sketch out a program that your HHH analyser would
>> impatiently abort as non-terminating, but which could conceivably stop
>> running this year, next year, sometime... or never.
> 
> Was wondering when someone would mention that...what does his HHH()
> do with arbitrary programs?
> 
> $ cat ddd.c
> #include <stdio.h>
> 
> void ddd(int r)
>      {
>      r--;
>      if(r <= 0) return;
>      fprintf(stderr,"calling ddd(%d)\n",r);
>      ddd(r);
>      fprintf(stderr,"returning, r=%d\n",r);
>      return;
>      }
> 
> 
> int main(void)
> {
> 
> ddd(50);
> 
> return 0;
> }
> 
> I'd bet his HHH() would say this is non-terminating.

Dunno. I can't test it because I was unable to construct his 
system locally, but your program terminates quite quickly, so 
maybe he can cope with it? I'm not sure.

Here's a sketch of a rather more ambitious program that will 
definitely give his HHH some serious pause for thought.

Imagine if you will a bignum library that can cope with basic 
arithmetic on integers whose bit patterns are stored in 
arbitrarily large arrays of unsigned char. (I have written such a 
library for my own purposes, but you could use Miracl or GMP.)

Clearly, in C this would be implemented using function calls, but 
for the sake of brevity in my sketch I'll pretend that C has 
operator overloading.

You could use the bignum library to implement Miller-Rabin, which 
I'll call is_prime().

Given all of this, we can sketch out a design for a C program 
that can't prove, but may or may not DISprove, the Goldbach 
conjecture:

int main(void)
{
   int found = 0;
   bignum even = 4;

   while(!found)
   {
     even += 2;
     found = check(even);
   }

   if(found)
   {
     printf("Goldbach conjecture is FALSE."
            " Pass me a Fields Medal.\n");
   }

   return EXIT_SUCCESS;
}

int check(bignum n)
{
   int found = 1; /* assume n is a counterexample */
   bignum i, j;
   for(i = 3; found && i += 2; i++)
   {
     j = n - i;

     if(is_prime(i) && is_prime(j))
     {
       /* n is NOT a counter-example */
       found = 0;
     }
   }
   return found;
}

Good luck with that, HHH().

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