I was wondering if there is a good bibliography of attempts to investigate the 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).

  • $\begingroup$ 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. $\endgroup$
    – vzn
    Commented Jun 2, 2012 at 4:52
  • $\begingroup$ more on collatz conjecture from FSM transducer angle & misc refs $\endgroup$
    – vzn
    Commented Sep 19, 2013 at 17:02
  • 2
    $\begingroup$ See also this question and its answer. $\endgroup$
    – J.-E. Pin
    Commented Nov 26, 2013 at 10:02

2 Answers 2


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

  1. The 3x+1 problem: An annotated bibliography (1963--1999) (sorted by author).
  2. The 3x+1 Problem: An Annotated Bibliography, II (2000-2009).

Another good source is the recent book "The Ultimate Challenge". In it chapter "Generalized $3x+1$ functions and the theory of computation",section $\#$ 8, can also be of interest.

  • $\begingroup$ thanks, I just wanted to see what else bubbles up before accepting the answer. $\endgroup$
    – Deniz
    Commented Mar 28, 2011 at 1:44

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.

EDITED TO ADD: This appears as result 8.5 in the "section #8" part of Oleksandr Bondarenko's answer.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.