Re: Halting Problem: What Constitutes Pathological Input

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