wikipedia has an entry on the [Collatz conjecture](http://en.wikipedia.org/wiki/Collatz_conjecture) with a section on [As an abstract machine that computes in base two](http://en.wikipedia.org/wiki/Collatz_conjecture#As_an_abstract_machine_that_computes_in_base_two). this apparently describes a construction of a [FSM transducer](http://en.wikipedia.org/wiki/Finite_state_transducer) computing sequential iterates starting from lsb to msb (least sig. bit to most sig. bit). [this is more a TCS, theoretical computer science construction.] however, there is no specific ref cited.



> 
> does anyone know where this FSM iterate transducer construction appears, or first appeared in the literature?
> 
> 
> 


note, there is some relation to ref [4].


[ps, have some apparently new/possibly groundbreaking results related to this construction & intend to write it up on a blog, may edit this post later to incl the ref.]


[1] [The ultimate challenge: the 3x+1 problem](http://rads.stackoverflow.com/amzn/click/0821849409), Lagarias


[2] [what is the nearest problem to the collatz conjecture that has been successfully resolved](https://cstheory.stackexchange.com/questions/11611/what-is-the-nearest-problem-to-the-collatz-conjecture-that-has-been-successful), tcs.se


[3] [The 3x + 1 Problem: An Annotated Bibliography](http://arxiv.org/pdf/math/0309224.pdf), Lagarias, arxiv


[4] Jeffrey O. Shallit and David W. Wilson (1991), The “3x + 1” Problem and Finite Au- tomata, Bulletin of the EATCS (European Association for Theoretical Computer Sci- ence), No. 46, 1991, pp. 182–185.



Collatz conjecture— finite state machine transducer construction, origination?
I gave a sequential machine computing the 3n+1/n:2 function in base 2 in several courses
since 1990, but of course I am not claiming any originality here, since it is just an easy
exercise.  

Anyway, if you want to see in more details how this sequential machine can be computed in a systematic way, you can look at <http://www.liafa.univ-paris-diderot.fr/~jep/PDF/Exposes/Sequential.pdf>, slide 59.


