State Transition Diagrams Explained

Since most readers not in the computer science community will not be familiar with state transition diagrams,  it will be well to give a brief explanation with particular attention to the use made of them here.

A state diagram seeks to picture the actions and capabilities of an automaton,  which is simply some kind of mindless device whose actions are completely described by a set of rigid rules.  The states achieved by the automaton can be pictured for clarification simply by showing each state as a node in a graph.  Often it is useful to include a description of  how the states of the automaton change as it makes transitions from state to state in conformance with the rules which govern it.  When the two aspects are combined in a single diagram, the result is a state transition diagram.

In the case of the Collatz trajectories,  the transitions from state to state are numerically complex enough that an understanding of them at a basic level has not arisen.  By discovering appropriate features of  the integer values encountered in the itineraries for use as state descriptors in the state diagram,  using letters to label the distinct states of interest,  and relegating the details of the arithmetic involved to the diagram's legend considerable simplification is attained.   In this simplified and higher level representation,  the behavior of the itineraries jumps into clear focus.

The states with the {5[8]} attribute in the diagram are unique in regard to their lack of any incoming edges.  This suggests that these states have a special role to play.  In considering what integers in {5[8]} can do next as controlled by their value mod 3,  one is led to the double descriptors {2[3],  5[8]},  {1[3],5[8],  and {0[3],5[8]},  or,  equivalently,  {5[24]},  {13[24]},  and {21[24]},  respectively,  for use to develop the sets of integer predecessors for each of these sets of elements in the Collatz graph.  Certain states   (to be called "leaf nodes",  consisting of all integers in {0[3]])  cannot have predecessors under the rules of the Collatz transitions with i in {1,2} (Eq'n 2) and are omitted from the diagram for its further simplification.

These combinations of values modulo   {3,8}  cover all integers  (as it certainly must if we are to have a useful scheme).  In practice,  we will concentrate solely on the odd positive integers.

The transition state diagram is written from the viewpoint of seeking predecessors from any integer set.  This practice will be continued throughout this work.  In the legend,  the arrows point from Collatz successor to Collatz predecessor.  The accuracy of the numerics attached to each transition may easily be checked by applying the familiar Collatz transition rules from right  (predecessor)  to left   (successor).  The C to C transition is given two prototypes,  because the 1->1 transition occuring only at the root of the Collatz graph and thus hardly typical,  whereas the 73->97 example is typical of the transitions among the whole bulk of them.

My Collatz Home Page        Index to Terms Used