From: Danny Calegari <dannyc@math.berkeley.edu>
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