分形/数学/群/二进制加法器

"加法器在动力系统和群在树上的作用理论中起着重要的作用。 "

结构

字母表 $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);