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

# Structure

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

$X = \left \{ 0,1 \right \}$

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

• a little-endian (least-significant-bit-first) : $c = c_0c_1 ..c_{n-1}$
• a big-endian : $c = c_{n-1} ..c_1c_0$

When :

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

Space of words $X ^ \omega$ denote the set of all infinite strings over the alphabet.

$X ^ \omega = \left \{ 0,1 \right \} ^ \omega$

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

$\epsilon$ represents the empty string

## Action

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 :

$c = c_0w$

where :

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

Transformation is defined by 2 recursion formulae :

• if the first symbol $c_0\,$ 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

Formally:

$(c)^a = \begin{cases} ( 0w )^a = 1w \\ ( 1w )^a = 0w^a \end{cases}$

or in other notation :

$a( 0w ) = 1w \,$
$a( 1w ) = 0a(w) \,$

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

$(c)^a = c + 1 \,$

More explicitly :[6]

$a(x_1 x_2 . . . x_n ) = y_1 y_2 . . . y_n \,$

if and only if

$( x_1 + 2*x_2 + 4*x_3 + ... + x_n*2^{n-1} ) + 1 = y_1 + y_2*2 + y_3*4 +... + y_n*2^{n-1} (mod 2^n )$

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

### Examples

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

$c = c_{n-1} ..c_1c_0 = \sum_{i=0}^{n-1} c_i 2^i$

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

without carry because lsb $c_0 = 0$:

  0
+ 1
---
1


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

  1
+ 1
---
10


  10
+ 01
-----
11



Carry in second column ( from right to left)

  011
+ 001
-----
100

  100
+ 001
-----
101

  101
+ 001
-----
110

  0111
+ 0001
-----
1000


## Nucleus

The nucleus of group G is :[7]

$N = \{ 1, a, a^{-1} \} \,$

where a is an action of group G

## Tree

A point of the binary tree c = c0 c1 c2 . . .where corresponds to the diadic integer $\quad \xi \,$

$\xi = \sum{ c_i 2^i |i \le 0}$

which translates to the n-ary addition

$\xi = \xi + 1 \,$

# Visual representation

## Diagram

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

$X = \left \{ 0,1 \right \}$

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]

# GAP/FR

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.

gap>LoadPackage("fr");