Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sun-barr!apple!julius.cs.uiuc.edu!ux1.cso.uiuc.edu!midway!midway.uchicago.edu!stuart From: stuart@cookie.cs.uchicago.edu (Stuart A. Kurtz) Newsgroups: comp.theory Subject: Re: 3n + 1 problem, in what sense is it undecidable. Message-ID: Date: 25 Sep 90 20:18:29 GMT References: <1990Sep21.212241.21613@athena.mit.edu> <1290@fornax.UUCP> Sender: news@midway.uchicago.edu (News Administrator) Organization: Dept. of Comp. Sci., The University of Chicago Lines: 35 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