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).
I guess these papers by Jeffrey C. Lagarias could help:
- The 3x+1 problem: An annotated bibliography (1963--1999) (sorted by author).
- The 3x+1 Problem: An Annotated Bibliography, II (2000-2009).
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.