Path: ...!weretis.net!feeder9.news.weretis.net!news.quux.org!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: Halting Problem: What Constitutes Pathological Input
Date: Tue, 6 May 2025 09:54:44 +0100
Organization: Fix this later
Lines: 65
Message-ID: <vvciok$2h0gm$2@dont-email.me>
References: <GE4SP.47558$VBab.42930@fx08.ams4> <vvamqc$o6v5$4@dont-email.me>
 <vvan7q$o4v0$1@dont-email.me> <ts5SP.113145$_Npd.41800@fx01.ams4>
 <vvao8p$o4v0$2@dont-email.me> <vvav61$vtiu$5@dont-email.me>
 <vvch3g$2ghfp$2@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Tue, 06 May 2025 10:54:45 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="4489552a91c35915dbf980ce94c452ca";
	logging-data="2654742"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19/T695cJWECyULjSRKmaU4chlZFAEUmgetTRmsFAeKCg=="
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:kMEfSRG84erFnwgabBYD04DFp3I=
Content-Language: en-GB
In-Reply-To: <vvch3g$2ghfp$2@dont-email.me>
Bytes: 2969

On 06/05/2025 09:26, Fred. Zwarts wrote:

<snip>

> OK, show one program for which both answers are wrong.

Well, I obviously I can't do that for him...

> Each program either halts, or does not halt, one answer is always 
> correct and the other one is incorrect.
> It is logically impossible that counter example exists. We must 
> agree that not both answers can be wrong.
> There is no self-contradiction. Only deciders that contradict the 
> correct answer.

....but what I /can/ do is outline a program that either halts or 
doesn't but nobody knows which.

First, we build ourselves a 'bignum' library in C++ (chosen 
because I want C++'s operator overloading). With unbounded tapes, 
we can have 'bint' integers as big as we need. The number 
variables in the following sketch can be assumed to be bignums.

Next, we build ourselves a primality tester, which I'll call 
isPrime, and a candidate tester as follows:

bool test(bint b)
{
   bool pass = false;
   bint midpoint = b/2;
   bint a = 0;
   for(a = 1; !pass && a <= midpoint; a += 2)
   {
     bint c = b - a;
     pass = isPrime(a) && isPrime(c);
   }
   return pass;
}

And now we can write this:

int main(void)
{
   bool counterexample = false;
   bint candidate = 4;

   while(!counterexample)
   {
     candidate += 2;
     counterexample = test(candidate);
     if(counterexample)
     {
       cout << "Counterexample: " << candidate << endl;
     }
   }
}

Would this program halt? Let Mr Olcott's decider decide.

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