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)