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

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
    Mar 28 '11 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, privacy policy and cookie policy

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