From: Danny Calegari Newsgroups: sci.math Subject: Re: Hailstone Anyone? Date: Wed, 02 Oct 1996 19:13:06 -0700 Larry O. Cates wrote: > > dittmer@OsFhRz70.Rz.Fh-Osnabrueck.De (Ingo Dittmer) wrote: > > >In article <52k2iv\$rll@camel1.mindspring.com> locates@atl.mindspring.com writes: > >>I first saw the "Hailstone" problem in the math recreations section of > >>Scientific American about 5 years ago. The statement of the problem > >>goes something like this: > >> > >> Given a positive integer, N, obtain the next integer,M, in a > >>sequence created according to the following rules: > >> a) if N is odd then M=3*N+1 > >> b) if N is even then M=N/2 > >> Then M is used as the next "N" to continue. Regardless of the N > >>chosen, the sequence appears to always result in {4,2,1}. > John Conway gave a very interesting talk on this and related questions, where one considers more general "Hailstone sequences"; i.e. one gives a sequence of fractions p_1/q_1, p_2/q_2, p_3/q_3 . . p_r/q_r starts with x_1 = some initial value, then defines x_n to be x_{n-1}p_i/q_i for the smallest such i that this gives an integer. He then shows that any Turing machine can be "modelled" by some such finite sequence of fractions, and vice-versa (where "halting" is ending up in some well-defined loop), and therefore that one shouldn't necessarily expect the halting problem for Hailstone numbers to be solvable because the halting problem for a "typical" Turing machine is not necessarily solvable, and the Hailstone numbers machine is just some "random" machine. Nothing terribly rigorous here, but it was the best "argument" I've heard that the Hailstone problem may well not be solvable. Danny Calegari. -- "What a waste it is to lose one's mind. Or not to have a mind - how true that is." - Dan Quayle