# Collatz conjecture— finite state machine transducer construction, origination?

wikipedia has an entry on the Collatz conjecture with a section on As an abstract machine that computes in base two. this apparently describes a construction of a FSM 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, Lagarias

[3] The 3x + 1 Problem: An Annotated Bibliography, 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.

-
I'm afraid that self-advertisement is something particularly frowned upon here. Why not try math.stackexchange.com? The answer to your question is that the equivalence between the Collatz function and the one described in base 2 is obvious, and needs no reference. –  user30035 Mar 3 at 20:30
the point is, is there a ref, in the literature, ie reference-request, which further explores properties of its construction etc. –  vzn Mar 3 at 20:41
I don't see he is advertising anything. He just wants a reference for the automaton formulation. –  Benjamin Steinberg Mar 3 at 21:35
Actually I take it back. I didn't notice the small print on my IPhone but now that I see it on a real computer I noticed the small print. So I upvote wccanard's comment. –  Benjamin Steinberg Mar 4 at 16:57
No, there is no discrepancy to be inferred! I said you should only say that you are writing something related to this (perhaps phrased in slightly nicer form than I sketched). As opposed to saying you should have left the ps away completely. The problem is not that you say you are writing something, but that you include some positive self-evaluation of it that, frankly, seems possibly exaggerated but even if it is not is is irrelevant to know whether (you think) this is "possibly groundbreaking." Indeed, I gave you some credit for including motivation, else it'd be closed already. –  quid Mar 5 at 20:01
show 5 more comments

## 1 Answer

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.

-
add comment