分形/數學/群/二進位制加法器

"加法器在動力系統和群在樹上的作用理論中起著重要的作用。 "

結構

字母表 $X$ 是一個包含兩個符號的集合，因此稱為二進位制字母表

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

單詞 c 是一個符號序列（字串）。它可以以兩種方式顯示：

• 小端序（最低有效位優先）：$c=c_{0}c_{1}..c_{n-1}$
• 大端序：$c=c_{n-1}..c_{1}c_{0}$

當

• $c_{0}$ 在右側時，更容易將其視為二進位制數
• $c_{0}$ 在左側時，更容易用於機器

單詞空間 $X^{\omega }$ 表示在字母表上所有無限字串的集合。

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

字串（$\epsilon$，0，1，00，01，10，11，000 等）都將在這個空間中。

$\epsilon$ 表示空字串

操作

十進位制 149 的二進位制表示，其中lsb突出顯示。 8 位二進位制數中的msb表示十進位制值為 128。 lsb 表示值為 1。

這裡只有一個變換（操作）a 對輸入字c 

$c=c_{0}w$

其中

• $c_{0}\,$ 是lsb， 第一個符號（這裡在開頭，但對於二進位制表示，它將在序列的末尾）
• $w\,$ 是單詞$c\,$ 的其餘部分

變換由2個遞迴公式定義：

• 如果第一個符號$c_{0}\,$ 為零，那麼我們將它改為一，單詞的其餘部分保持不變
• 如果是1
  • 我們將它改為零
  • 向下一列進位 1。
  • 將操作應用於下一列（符號），直到最後一列。

正式地

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

或者用另一種符號表示

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

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

"這種轉換被稱為加法器或里程錶，因為它描述了對二進位制整數加一的過程。"

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

更明確地說:

$a(x_{1}x_{2}...x_{n})=y_{1}y_{2}...y_{n}\,$

當且僅當

$(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})$

輸入和輸出都是二進位制數，最低有效位在最前面。

例子

字 c 是 n 個符號（從 0 到 n-1）的序列，表示二進位制整數

$c=c_{n-1}..c_{1}c_{0}=\sum _{i=0}^{n-1}c_{i}2^{i}$

其中 $c_{n}$ 是二進位制字母表 X ={0,1} 的元素。

沒有進位，因為最低有效位 $c_{0}=0$

  0 
+ 1 
---
  1

這裡最低有效位 $c_{0}=1$，那麼 c_0+1>1，所以必須把 1 進位到下一列。

  1 
+ 1  
---
 10

  10 
+ 01
-----
  11

進位到第二列（從右到左）

  011 
+ 001   
-----
  100

  100 
+ 001   
-----
  101

  101 
+ 001   
-----
  110

  0111 
+ 0001   
-----
  1000

核心

群 G 的核心是:

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

其中 a 是群 G 的一個操作

樹

二叉樹中的一個點 c = c0 c1 c2 ... 與二元整數 $\quad \xi \,$

$\xi =\sum {c_{i}2^{i}|i\leq 0}$

這可以轉化為 n 進位制加法

$\xi =\xi +1\,$

視覺化表示

圖表

這裡字母表 $X$ 是一個包含兩個符號的集合，因此它被稱為二進位制字母表

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

標籤顯示符號對：輸入/輸出

有 2 個頂點（節點，機器狀態）：1 和 0。

頂點對應於狀態。

"該機器的狀態將表示“進位”到下一個位位置的值。

最初“進位”為 1。

只要輸入位為 1，進位就會“傳播”。

當遇到輸入位為 0 時，進位就會被“吸收”，並輸出 1。

在那一點之後，輸入只是被複制。"

表格

表格

GAP/FR

BinaryAddingGroup	( global variable )

此函式構造在 [1,2] 上由加法器生成的閉態群。該群與整數同構。

BinaryAddingMachine	( global variable )

此函式在字母表 [1,2] 上構造加法器。該機器有一個平凡狀態 1 和一個非平凡狀態 2。它對序列執行“加 1 帶進位”操作。

BinaryAddingElement	( global variable )

此函式構造加法器上的米利元素，初始狀態為 2。

這些函式分別與 AddingGroup(2)、AddingMachine(2) 和 AddingElement(2) 相同。

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