Fractals/Mathematics/group/Binary adding machine

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

Structure

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

$X=\{0,1\}$

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

• a little-endian (least-significant-bit-first) : $c=c_0{c}_1..c_{n-1}$
• a big-endian : $c=c_{n-1}..c_1{c}_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 }={\{0,1\}}^{\omega }$

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

$ϵ$ 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_{0}w$

where :

• $c_0$ is a lsb, first symbol ( here at the beginning, but for binary notation it 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.
  • aply action to the next column (symbol) until last column

Formally:

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

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

$(c{)}^a=c+1$

More explicitly :

$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_1{c}_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 :

$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 $\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=\{0,1\}$

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

Table

Table

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.

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

gap>LoadPackage("fr"); 
gap> Draw(NucleusMachine(BinaryAddingGroup));
gap>Draw(BinaryAddingMachine);