3
$\begingroup$

This problem of Waring's is unsolved: For all $n \ge 2 $, $\lfloor (\frac 32 ) ^n \rfloor + {3^n} \bmod{2^n} < 2^n $. (Kubina and Wunderlich have tested this up to $471,600,000$.) This can be converted into a "C-like" program:

x = 9;  y = 4;  while ( x/y + x%y < y ) {      x = 3*x;      y = 2*y;  }  

which can be shortened slightly to:

x = 9;  for( y = 4 ; x/y + x%y < y ; y *= 2 )     x *= 3; 

Does anyone know of an unsolved problem which can be converted into a shorter program? The program must halt iff the problem is false. Put differently, I conjecture that the above program is the shortest whose halting is unknown. I want the program to be C-like, with integers of unlimited size.

  • 0
    Lew knows about this, but others may benefit by perusing http://mathoverflow.net/questions/29949/what-is-the-shortest-program-for-which-halting-is-unknown2012-10-11

1 Answers 1