From: gerry@mpce.mq.edu.au (Gerry Myerson) Subject: Re: Is Collatz Conjecture (3N+1 Problem) Undecidable? Date: Wed, 30 Jun 1999 13:05:01 +1100 Newsgroups: sci.math Keywords: Conway's generalizations include some undecideable problems In article <19990629224649.08062.00004846@ng-fs1.aol.com>, lmwapner@aol.com (LMWapner) wrote: > Has this conjecture been shown undecidable? (I seem to recall that Conway may > have established this fact.) Conway defined a family of problems, a natural generalization of the Collatz problem, and showed that there is no algorithm for deciding all problems in the family, which implies that there are individual problems in the family that are undecidable. This says nothing about the original problem. The reference is J H Conway, Unpredictable iterations, Proc Number Theory Conf, Boulder 1972, 49-52, MR 52 #13717. Gerry Myerson (gerry@mpce.mq.edu.au) ============================================================================== From: mathwft@math.canterbury.ac.nz (Bill Taylor) Subject: Weird sequences. was: Is Collatz Conjecture Undecidable? Date: 2 Jul 1999 07:30:33 GMT Newsgroups: sci.math gerry@mpce.mq.edu.au (Gerry Myerson) writes: |> Conway defined a family of problems, a natural generalization of the Collatz |> problem, and showed that there is no algorithm for deciding all the problems |> ... ... |> The reference is J H Conway, Unpredictable iterations, Proc Number Theory |> Conf, Boulder 1972, 49-52, MR 52 #13717. Dammit, we haven't got this in our library, so I can't do a quick check. However, Gerry, are you sure this is the same thing? Probably I'm all screwed up, but I recall a paper by JHConway (may he live for ever), with a title very like that one, that was about something rather different. As it's rather fun anyway, I'll mention it here for those who haven't seen it. Conway's Weird Sequences. ======================== Here is the archetypical one. Define a function f: N --> N by f(4n+1) = 3n+1 f(4n-1) = 3n-1 f(2n) = 3n This is well-defined for all of N, clearly. And looking at the first few values, we get 3 small cycles... 1 --> 1 2 --> 3 --> 2 4 -> 6 -> 9 -> 7 -> 5 -> 4 ...and then a seemingly infinite sequence of iterations:- 8 -> 12 -> 18 -> 27 -> 20 -> 30 -> 45 -> 32 -> 48 -> 72 -> 108 -> ... More interestingly still, the function f is 1-to-1, as is easily checked. So each number generates a backward sequence as well; that is, an iterative sequence of values of f^(-1). The three finite cycles just reverse direction, but otherwise we get a whole new sequence. Still using the arrow to denote the direction of f, the inverse sequence starting with that same 8 is: 8 <- 11 <- 15 <- 10 <- 13 <- 17 <- 23 <- 31 <- 41 <- 55 <- 73 <- 97 <- ... So, we have three little cycles, and a whole bunch of "doubly infinite" sequences, coming down from infinity, passing through a few smallish numbers, and going back up to infinity a different way. So the full 8-sequence goes ...129 97 73 55 41 31 23 17 13 10 15 11 8 12 18 27 20 30 45 32 48 72 108... There are infinitely many such sequences. You may note the smallest number as yet unaccounted for is 14, and effing and inverse-effing this (what fun!) gives ...103 77 58 87 65 49 37 28 42 63 47 35 26 39 29 22 33 25 19 *14* 21 16 24 36 54 81 61 46 69 52 78 117... There's nothing special about 14 of course, it just happens to be the smallest. The sequences so far have scooped out a lot of the double-digit numbers, but there are still quite a few left, the next smallest being 34. This has its own sequence, which still leaves out some numbers, and so on. The whole collection of seqeunces is really weird, going off infinitely at both ends, but "knowing enough" to know they have to come down toward small(ish) numbers sometime; rather as if someone grabbed an infinite bunch of sloppy spaghetti, and only a few strands are held well up, and a few more not so well... Of course it would be easy to define any old artificial function f to do this, but it's remarkable that such a simple f as the one above will do it. And yet the function is in some sense pseudo-quasi-random, rather as the Collatz sequence is. The heuristics of the double trend to infinity are easy enough to see:- function f either (approximately) adds half or subtracts a quarter of the input to itself, but with equal "probabilities". So "on average", it rises, but in fits and starts. Similarly, the function f^(-1) either adds or subtracts a third of the input to/from itself, but the former more often, by 2 to 1. So it too tends to increase unsteadily. Both f and f^(-1) tend to raise the value!! Whoops! If you pick a large integer "at random", it will "almost surely" head off to infinity without coming down significantly at all. But just a rare once in a while, you might happen to hit one of the left-hand "halves" of the above doubly infinite sequence, as your chosen number. Then iterating f will bring the numbers down a fair way, before starting to rise again. The whole thing is altogether weird and wonderful. ----------------------------------------------------------------- One can re-arrange the three arguments and value expressions of f to get other similar functions, (you may have to go into negative integers); or more generally, move away from the 2-3-4 bases. It would also be nice to put (if poss) some kind of formalization on my probabilistic remarks above, where protected by scare quotes. There is endless scope for fun here... ------------------------------------------------------------------------------- Bill Taylor W.Taylor@math.canterbury.ac.nz ------------------------------------------------------------------------------- The more the universe seems comprehensible, the more it also seems pointless. ------------------------------------------------------------------------------- ============================================================================== From: gerry@mpce.mq.edu.au (Gerry Myerson) Subject: Re: Weird sequences. was: Is Collatz Conjecture Undecidable? Date: Mon, 05 Jul 1999 12:07:08 +1100 Newsgroups: sci.math In article <7lhpqp$bi9$1@cantuc.canterbury.ac.nz>, mathwft@math.canterbury.ac.nz (Bill Taylor) wrote: => gerry@mpce.mq.edu.au (Gerry Myerson) writes: => => |> Conway defined a family of problems, a natural generalization of the => |> Collatz problem.... => |> The reference is J H Conway, Unpredictable iterations, Proc Number Theory => |> Conf, Boulder 1972, 49-52, MR 52 #13717. => => Dammit, we haven't got this in our library, so I can't do a quick check. => => However, Gerry, are you sure this is the same thing? Probably I'm all => screwed up, but I recall a paper by JHConway (may he live for ever), with => a title very like that one, that was about something rather different. => => As it's rather fun anyway, I'll mention it here for those who haven't => seen it. => => Conway's Weird Sequences. => ======================== => => Here is the archetypical one. Define a function f: N --> N by => => f(4n+1) = 3n+1 => f(4n-1) = 3n-1 => f(2n) = 3n Nu? Don't you think this is a member of a family of problems which are natural generalizations of the Collatz problem? => This is well-defined for all of N, clearly. And looking at the first few => values, we get 3 small cycles... => => 1 --> 1 2 --> 3 --> 2 4 -> 6 -> 9 -> 7 -> 5 -> 4 => => ...and then a seemingly infinite sequence of iterations:- => => 8 -> 12 -> 18 -> 27 -> 20 -> 30 -> 45 -> 32 -> 48 -> 72 -> 108 -> ... I note that here you are careful to say, "seemingly infinite." => So, we have three little cycles, and a whole bunch of "doubly infinite" => sequences, coming down from infinity, passing through a few smallish numbers, => and going back up to infinity a different way. So the full 8-sequence goes => => ...129 97 73 55 41 31 23 17 13 10 15 11 8 12 18 27 20 30 45 32 48 72 108... And here you put "doubly infinite" in quotes. But you do seem to be convinced that this sequence goes off to infinity in both directions. And you may well be right. But I don't think it has been proved that this sequence goes off to infinity in either direction. => There are infinitely many such sequences. Maybe so, but so far as I know, it hasn't been proved that there is even one doubly infinite sequence, much less that there are infinitely many of them. => One can re-arrange the three arguments and value expressions of f to get => other similar functions, (you may have to go into negative integers); or more => generally, move away from the 2-3-4 bases. That's the idea behind the family Conway studies. Gerry Myerson (gerry@mpce.mq.edu.au)