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

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{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."
    $(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}(mod2^{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$:
Here lsb $c_{0}=1$ then c_0+1>1 so one has to carry 1 to next column
Carry in second column ( from right to left)

## 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 $\quad \xi \,$
    $\xi =\sum {c_{i}2^{i}|i\leq 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."

## Table

Table

# GAP/FR

This function constructs the state-closed group generated by the adding machine on [1,2]. This group is isomorphic to the Integers.
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.
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).

# References

* ↑ THE n-ARY ADDING MACHINE AND SOLVABLE GROUPS by JOSIMAR DA SILVA ROCHA AND SAID NAJATI SIDKI
* ↑ wikipedia : Endianness
* ↑ wikipedia : Least significant bit
* ↑ Wikipedis : carry at Binary_numeral_system
* ↑ ITERATED MONODROMY GROUPS by VOLODYMYR NEKRASHEVYCH
* ↑ Groups and analysis on fractals Volodymyr Nekrashevych and Alexander Teplyaev
* ↑ FROM SELF-SIMILAR STRUCTURES TO SELF-SIMILAR GROUPS DANIEL J. KELLEHER, BENJAMIN A. STEINHURST, AND CHUEN-MING M. WONG
* ↑ Robert M. Keller : Finite-State Machines
* ↑ wikipedia : State transition table