Fractals/Mathematics/group/Binary adding machine

< Fractals‎ | Mathematics/group

"Adding machines have played an important role in dynamical systems, and in the theory of groups acting on trees. "[1]



Alphabet is a set consisting of two symbols so it is called binary alphabet:

Word c is a sequence of symbols ( string). It can be dsiplayed in two ways : [2]

  • a little-endian (least-significant-bit-first) :
  • a big-endian :

When :

  • is on the right side it is easier to treat it as a binary number
  • is on the leftt side it is easier for machine

Space of words denote the set of all infinite strings over the alphabet.

The strings (, 0, 1, 00, 01, 10, 11, 000, etc.) would all be in this space.

represents the empty string


The binary representation of decimal 149, with the lsb highlighted. The msb in an 8-bit binary number represents a value of 128 decimal. The lsb represents a value of 1.

Here is only one transformation ( action ) a ona a input word c :

where :

  • is a lsb[3] , first symbol ( here at the beginnig, but for binary notationit will be at the end of sequence)
  • is a rest of the word c

Transformation is defined by 2 recursion formulae :

  • if the first symbol is zero then we change it to one and the rest of the word remains unchanged
  • if it is one :
    • we change it to zero
    • carry 1 to next column.[4]
    • aply action to the next column (symbol) until last column


or in other notation :

"This transformation is known as the adding machine, or odometer, since it describes the process of adding one to a binary integer." [5]

More explicitly :[6]

if and only if

Both input and output are binary numbers least-significant bit first.


Word c is a sequence of n symbols ( from 0 to n-1) representing binary integer :

where is an element of binary alphabet X ={0,1}

without carry because lsb :

+ 1 

Here lsb then c_0+1>1 so one has to carry 1 to next column

+ 1  

+ 01

Carry in second column ( from right to left)

+ 001   
+ 001   
+ 001   
+ 0001   


The nucleus of group G is :[7]

where a is an action of group G


A point of the binary tree c = c0 c1 c2 . . .where corresponds to the diadic integer

which translates to the n-ary addition

Visual representationEdit


Here alphabet is a set consisting of two symbols so it is called binary alphabet:

Labels shows pairs of symbols : input/output

There are 2 vertices ( nodes, states of machine) : 1 and 0.

Vertices correspond to the states .

"The states of this machine will represent the value that is "carried" to the next bit position.

Initially 1 is "carried".

The carry is "propagated" as long as the input bits are 1.

When an input bit of 0 is encountered, the carry is "absorbed" and 1 is output.

After that point, the input is just replicated." [8]


Table [9]


BinaryAddingGroup  ( global variable )

This function constructs the state-closed group generated by the adding machine on [1,2]. This group is isomorphic to the Integers.

BinaryAddingMachine        ( global variable )

This function constructs the adding machine on the alphabet [1,2]. This machine has a trivial state 1, and a non-trivial state 2. It implements the operation "add 1 with carry" on sequences.

BinaryAddingElement        ( global variable )

This function constructs the Mealy element on the adding machine, with initial state 2.

These functions are respectively the same as AddingGroup(2), AddingMachine(2) and AddingElement(2).

gap> Draw(NucleusMachine(BinaryAddingGroup));