stuart@cookie.cs.uchicago.edu (Stuart A. Kurtz) (09/26/90)
There is some yet unpublished work on the 3n+1 problem (also known as the Collatz problem), in which one considers generalized Collatz functions. A generalized Collatz function takes 2m+1 parameters. The first is an integral modulus (m), and then there are 2m rationals (q_i, r_i), subject to the constraint that q_i n + r_i is integral if n is congruent to i mod m. Thus, for the standard 3n+1 function, we have m = 2 q_0 = 1/2 r_0 = 0 q_1 = 3 r_1 = 1 In general, f(n) is the number of iterations of this (implicitly given) transformation necessary to get to 1. Conway proved that determining, for a given generalized Collatz function, whether or not it was total on all inputs of the form 3^n, is equivalent to the totality problem for turing machines. Janos Simon and I improved Conway's result, showing that the totality problem for generalized Collatz functions is equivalent to the totality problem for turing machines. Thus, the Collatz problem is an element of a set that is \Pi_2 complete (with respect to 1-reductions). Of course, this gives very little information about how difficult the original 3n+1 problem is. Obviously, a \Pi_2 complete set necessarily contains both easy & hard problems. Hope this helps, Stuart A. Kurtz Department of Computer Science University of Chicago stuart@cs.uchicago.edu