The following is based on Waring's Problem: For all n floor((3/2)^n) + 3^n mod 2^n < 2^n. Kubina has tested this up to 471,600,000.

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

Assume that x and y are int's with unlimited size.

The following is based on Waring's Problem:

For all n floor((3/2)^n) + 3^n mod 2^n < 2^n. Kubina has tested this up to 471,600,000.

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

Assume that x and y are int's with unlimited size.

Whereas small Turing machines have been exhaustively analysed and, as Richard notes, there is a 5-state 2-symbol TM whose halting is unknown, I have not seen a similar analysis for other models of computation (Register Machines, LOOP programs, C programs). So I propose the above C program (containing 32 symbols) as the shortest whose halting is unknown.

In the program x contains powers of 3 and y contains corresponding powers of 2 (x*=3 multiplies x by 3).

The following is based on Waring's Problem: For all n floor((3/2)^n) + 3^n mod 2^n < 2^n. Kubina has tested this up to 471,600,000.

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

Assume that x and y are int's with unlimited size.

The following is based on Waring's Problem: For all n floor((3/2)^n) + 3^n mod 2^n < 2^n. Kubina has tested this up to 471,600,000.

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

Assume that x and y are int's with unlimited size.