Fractals/Mathematics/group/Binary adding machine

From Wikibooks, open books for an open world
Jump to: navigation, search

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

Structure[edit]

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[edit]

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[edit]

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[edit]

The nucleus of group G is :[7]

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

where a is an action of group G

Tree[edit]

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[edit]

Diagram[edit]

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]

Table[edit]

Table [9]

GAP/FR[edit]

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

References[edit]

  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