More on k-automatic sequences

[Jon Awbrey]

¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤

David W. Wilson wrote:
> 
> For Seqfans not in the know, Jeffrey Shallit and I cowrote a paper for
> the EATCS a few years ago (more precisely, I supplied the idea, Jeffrey
> actually wrote and published the paper, crediting me).  The paper made
> a connection between the Collatz conjecture (3x+1 conjecture) and
> 2-regular sets (sets of integers whose base-2 reps form a regular set
> (set of strings recognized by a finite automaton).
> 
> For sequence fans not familiar with Collatz:
> 
> The Collatz function is
> 
>     f(x) =
>         x/2 if x is even
>         3x+1 if x is odd
> 
> The Collatz trajectory of positive integer n is the sequence of integers
> obtained by repeatedly applying the Collatz function to n.  The sequence
> ends if 1 is reached.  For example, the Collatz trajectory of 7 is
> 
>     (7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1)
> 
> The Collatz conjecture is that the Collatz trajectory of every positive
> integer is finite, that is, repeatedly applying the Collatz function to
> any positive integer eventually results in 1.  The Collatz conjecture
> is a seriously tough problem which seems true, but has thus far resisted
> proof.
> 
> Let S(n) be the set of positive integers having n odd integers in their
> Collatz trajectories.  We then have
> 
>     S(1) = (1, 2, 4, 8, 16, 32, 64, 128, 256, 512, ...)
>     S(2) = (5, 10, 20, 21, 40, 42, 80, 84, 85, 160, ...)
>     S(3) = (3, 6, 12, 13, 24, 26, 48, 52, 53, 96, ...)
>     S(4) = (17, 34, 35, 68, 69, 70, 75, 136, 138, 140, ...)
>     S(5) = (11, 22, 23, 44, 45, 46, 88, 90, 92, 93, ...)
>     S(6) = (7, 14, 15, 28, 29, 30, 56, 58, 60, 61, ...)
>     S(7) = (9, 18, 19, 36, 37, 38, 72, 74, 76, 77, ...)
>     S(8) = (25, 49, 50, 51, 98, 99, 100, 101, 102, 196, ...)
>     S(9) = (33, 65, 66, 67, 130, 131, 132, 133, 134, 260, ...)
>     S(10) = (43, 86, 87, 89, 172, 173, 174, 177, 178, 179, ...)
> 
> If the Collatz conjecture is true, each positive integer occurs in
> exactly one S(n).
> 
> It is fairly easy to show that S(1) consists of the powers of 2.  In
> base 2 we would write
> 
>     S(1) = (1, 10, 100, 1000, 10000, 100000, 1000000, ...)
> 
> If these base-2 representations are taken as strings, they form a
> regular language described by the regular expression 10* (meaning 1
> followed by any number of 0's).  A set of integers whose base-k reps
> form a regular language is called a k-automatic set.  Thus S(1) is a
> 2-automatic set.
> 
> If we write S(2) in base 2, we get
> 
>    S(2) = (101, 1010, 10100, 10101, 101000, 101010, 1010000, ...)
> 
> which can be described by the regular set 101(01)*0* (101 followed
> by any number of 01's followed by any number of 0's).  Hence S(2) is
> 2-automatic as well.
> 
> What Jeffrey and I showed in our paper is that all S(k) are
> 2-automatic.  The proof was not especially deep (I understand it
> appears as an exercise in Jeffrey's new book).  I was hoping at one
> time to generate the finite state machines for small S(k), to see if
> there might be some structure that could be leveraged against the
> Collatz conjecture, but I gave up for lack of basic tools for logical
> and arithmetical manipulation of k-automatic sets.
> 
> It would be nice if Mathematica provided a k-automatic set package.
> Given Wolfram's penchant for cellular automata and the like, this
> would be right up his alley.

¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤

David, Jeffrey, Sequence Pilgrims Alle ...

Incidental Musement.  There is a parens string & parse graph scheme that I use
for Cook's transcription of "space-&-time limited turing machines" (= STILT's),
which are of course really just finite automata in disguise.  The parse graphs
are a species called "painted and rooted cacti" (PARC's).  Can supply program
and detail if anybody interested.  Here is a link -- if you skip down to where
you see a parity machine diagram you can avoid a lot of diverting preamble:

http://lists.w3.org/Archives/Public/www-rdf-logic/2001Jan/0086.html

Jon Awbrey

¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤