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. "[1]

StructureEdit

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

ActionEdit

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.


ExamplesEdit

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

NucleusEdit

The nucleus of group G is :[7]

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

where a is an action of group G

TreeEdit

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 representationEdit

DiagramEdit

Moore diagram of Binary Adding Machine


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]

TableEdit

Table [9]

GAP/FREdit

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);

ReferencesEdit

  1. THE n-ARY ADDING MACHINE AND SOLVABLE GROUPS by JOSIMAR DA SILVA ROCHA AND SAID NAJATI SIDKI
  2. wikipedia : Endianness
  3. wikipedia : Least significant bit
  4. Wikipedis : carry at Binary_numeral_system
  5. ITERATED MONODROMY GROUPS by VOLODYMYR NEKRASHEVYCH
  6. Groups and analysis on fractals Volodymyr Nekrashevych and Alexander Teplyaev
  7. | FROM SELF-SIMILAR STRUCTURES TO SELF-SIMILAR GROUPS DANIEL J. KELLEHER, BENJAMIN A. STEINHURST, AND CHUEN-MING M. WONG
  8. Robert M. Keller : Finite-State Machines
  9. wikipedia : State transition table
Last modified on 18 March 2012, at 18:40