<p>Specifically, you may want to check out this paper by Shallit and Wilson: 
<a href="http://www.cs.uwaterloo.ca/~shallit/Papers/wilson.pdf" rel="nofollow noreferrer">The "3x+1" Problem and Finite Automata", <em>Bulletin of the EATCS</em>, 46 (1992), pp. 182-185</a>.</p>

<p>EDITED TO ADD: This appears as result 8.5 in the "section #8" part of <a href="https://cstheory.stackexchange.com/questions/5675/collatz-conjecture-grammars-automata/5676#5676">Oleksandr Bondarenko's answer</a>.</p>

CC BY-SA 2.5
2011-03-28T02:24:42.760Z
2011-03-28T22:37:05.667Z
2017-04-13T12:32:28.053Z
mhum
<p>I guess these papers by Jeffrey C. Lagarias could help:</p>

<ol>
<li><a href="http://arxiv.org/abs/math/0309224">The 3x+1 problem: An annotated bibliography (1963--1999) (sorted by author)</a>.</li>
<li><a href="http://arxiv.org/abs/math/0608208">The 3x+1 Problem: An Annotated Bibliography, II (2000-2009)</a>.</li>
</ol>

<p>Another good source is the recent book "<a href="http://books.google.com/books?id=hekJ7JDMEVkC&amp;printsec=frontcover&amp;source=gbs_atb#v=onepage&amp;q&amp;f=false">The Ultimate Challenge</a>". In it  chapter "Generalized $3x+1$ functions and the theory of computation",<a href="http://books.google.com/books?hl=en&amp;lr=&amp;id=hekJ7JDMEVkC&amp;oi=fnd&amp;pg=PA123#v=onepage&amp;q&amp;f=false">section $\#$ 8</a>, can also be of interest.</p>

CC BY-SA 2.5
2011-03-28T01:44:54.577Z
thanks, I just wanted to see what else bubbles up before accepting the answer.
Deniz
CC BY-SA 2.5
2011-03-26T21:52:47.393Z
2011-03-27T00:00:33.370Z
2011-03-27T00:00:33.370Z
Oleksandr Bondarenko
<p>I was wondering if there is a good bibliography of attempts to investigate the <a href="http://en.wikipedia.org/wiki/Collatz_conjecture">Collatz conjecture</a> as a formal grammar?  (or any other attempts in the CS community to deal with this class of generative phenomena &amp; their "halting" properties). </p>

CC BY-SA 3.0
2012-06-02T04:52:39.160Z
as a sort of folklore approach, there is a fairly natural way to study this problem by building an FSM transducer that computes iterates in binary (least significant bit to most significant bit) although have not seen this in a paper. dont know if this construction is in the shallit and wilson paper, that may be the closest published paper to the transducer technique.
vzn
CC BY-SA 3.0
2013-09-19T17:02:50.363Z
more on collatz conjecture from [FSM transducer angle & misc refs](http://vzn1.wordpress.com/code/collatz-conjecture-experiments/)
vzn
CC BY-SA 3.0
2013-11-26T10:02:24.373Z
See also this [question](http://mathoverflow.net/questions/123491/collatz-conjecture-finite-state-machine-transducer-construction-origination/138675#138675) and its answer.
J.-E. Pin
<fl.formal-languages><nt.number-theory><halting-problem>
Collatz Conjecture & Grammars / Automata
Deniz
# Collatz Conjecture & Grammars / Automata

(Asked by: username_0 on 2011-03-26)

I was wondering if there is a good bibliography of attempts to investigate the [Collatz conjecture](http://en.wikipedia.org/wiki/Collatz_conjecture) as a formal grammar? (or any other attempts in the CS community to deal with this class of generative phenomena & their "halting" properties).

**Tags:** fl.formal-languages, nt.number-theory, halting-problem
> **Comments:**
> **username_1**: as a sort of folklore approach, there is a fairly natural way to study this problem by building an FSM transducer that computes iterates in binary (least significant bit to most significant bit) although have not seen this in a paper. dont know if this construction is in the shallit and wilson paper, that may be the closest published paper to the transducer technique.  
> **username_1**: more on collatz conjecture from [FSM transducer angle & misc refs](http://vzn1.wordpress.com/code/collatz-conjecture-experiments/)  
> **username_2**: See also this [question](http://mathoverflow.net/questions/123491/collatz-conjecture-finite-state-machine-transducer-construction-origination/138675#138675) and its answer.  

---

## 2 answers

### Answer by username_4 on 2011-03-26. Score: 22 | Accepted answer

I guess these papers by Jeffrey C. Lagarias could help:

1. [The 3x+1 problem: An annotated bibliography (1963--1999) (sorted by author)](http://arxiv.org/abs/math/0309224).
2. [The 3x+1 Problem: An Annotated Bibliography, II (2000-2009)](http://arxiv.org/abs/math/0608208).

Another good source is the recent book "[The Ultimate Challenge](http://books.google.com/books?id=hekJ7JDMEVkC&printsec=frontcover&source=gbs_atb#v=onepage&q&f=false)". In it chapter "Generalized $3x+1$ functions and the theory of computation",[section $\#$ 8](http://books.google.com/books?hl=en&lr=&id=hekJ7JDMEVkC&oi=fnd&pg=PA123#v=onepage&q&f=false), can also be of interest.

> **Comments:**
> **username_0**: thanks, I just wanted to see what else bubbles up before accepting the answer.  

---

### Answer by username_3 on 2011-03-28. Score: 10

Specifically, you may want to check out this paper by Shallit and Wilson:
[The "3x+1" Problem and Finite Automata", *Bulletin of the EATCS*, 46 (1992), pp. 182-185](http://www.cs.uwaterloo.ca/~shallit/Papers/wilson.pdf).

EDITED TO ADD: This appears as result 8.5 in the "section #8" part of [Oleksandr Bondarenko's answer](https://cstheory.stackexchange.com/questions/5675/collatz-conjecture-grammars-automata/5676#5676).


---

