Sign up ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

[2] what is the nearest problem to the collatz conjecture that has been successfully resolved,

[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.

share|cite|improve this question
I'm afraid that self-advertisement is something particularly frowned upon here. Why not try 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 '13 at 20:30
I don't see he is advertising anything. He just wants a reference for the automaton formulation. –  Benjamin Steinberg Mar 3 '13 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 '13 at 16:57
If you would like to avoid problems of this kind, just do not refer to your work as "possibly groundbreaking" and there is no need to stress that the work is "apparently new". Why not only say that you are in the process of writing something related to this and thus would be interested in a reference you can quote. –  quid Mar 4 '13 at 18:21
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 '13 at 20:01

1 Answer 1

up vote 8 down vote accepted

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, slide 59.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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