note-math

自然语言的例子

数字电路表示 bool

这里不处理数字电路的硬件实现. 我也不知道细节

• 且, $\wedge$, and, 逻辑合取 (conjunction)
• 或, $\vee$, or, 逻辑析取 (disjunction)
• 非, $\neg$, not, 逻辑反取 (negation)

自然语言的例子

形式语言

$\wedge ,\vee ,\neg$ 的数字电路和逻辑门 (gate) 的表示

gate 设计为不允许反向电流?

not gate 将低电平转到高电平, 说明 gate 的硬件实现需要外部能量, 需要通电

"冗余性" e.g. 我们可以用 $\neg ,\wedge$ 表示 $\vee$

电路 gate 实现是用 not,nand or $\neg ,\left(\neg \wedge \right)$ 作为开始. 但我觉得保持 $\wedge ,\vee$ 的对称性是有用的, 认知上或者 negetive dual 上

可用逻辑门制造任何 ${\left\{0,1\right\}}^{𝑛}\to {\left\{0,1\right\}}^{𝑚}$ 函数

(image from p.85 of ref-1)

• ${\left\{0,1\right\}}^{𝑛}$ 输入的构造

• ${\left\{0,1\right\}}^1$ 输出的构造

在输入中, 将想要输出到 1 的电线接到 or gate

Example not xor

互斥或, ⊕, xor

• ${\left\{0,1\right\}}^{𝑚}$ 输出的构造. 只需将需要的电线组合接到 $𝑚$ 个 or game

如果函数不需要完整 ${\left\{0,1\right\}}^{𝑛}\to {\left\{0,1\right\}}^{𝑚}$, 电路计算元件不一定要按这种固定方式来构建. 可以根据情况, 进一步简化, 减少 gate 数量的使用. 但这里不进入细节

bool 代数记为 $\left\{0,1\right\},+,\cdot$ 或者 $\left\{0,1\right\},\vee ,\wedge$

bool-distributive-law_(tag) 分配律

bool-commutative-law_(tag) 交换律 $𝐴+𝐵=𝐵+𝐴$. same for $\cdot$

bool-associative-law_(tag) 结合律 $\left(𝐴+𝐵\right)+𝐶=𝐴+\left(𝐵+𝐶\right)$. same for $\cdot$

黑箱模型

可能的实现

• 使用环电路重用上一个周期的 $𝑎,\overline{𝑎}$ 的 1/0 值
• 反相器 (not gate) 确保电流方向并防止 1 衰减 (通过外部能量)
• 为了将 0 写入已有的 1, 需要在 $\overline{\text{write}}$ 写入 1 得到 $\overline{𝑎}=1$, 然后反转为 $𝑎=0$
• 需要比循环里的电压更高的写入电压来覆盖循环中的先前已有的 $1$? e.g. 用更高电压 $\overline{\text{write }}=1$ 来覆盖已有的 $𝑎=1$

finite-machine_(tag) 有限状态机

i/o_(tag) 电路的输入可能来自外界 (e.g. 传感器, 键盘), 电路的输出也可能到达外界 (e.g. 信号灯, 屏幕)

外界输入的节奏通常不一致于计算机内部周期电路的节奏, 因此需要让外界输入先经过同步元件

二进制, 序, 自然数. Example $2^3$ 就是从 000, 001, 010 数到 111 时经过的步数, 虽然这假设了我们能识别三位 bit. $2^{𝑛}=\underset{𝑛\text{-fold}}{\underbrace{2\cdots 2}}$, $101=1\cdot 2^2+0\cdot 2^1+1\cdot 2^0=4+1=5$

用多位 bit 包含的自然数范围, 例如 3 bit 的 $0,1,\dots ,7$ 作为参数, 去对应到真实世界的内容. Example 计算机的字符的表示方式 e.g. ASCII, Unicode, 屏幕的发光点位置和颜色

(image modified from wiki media about ASCII)

在实际应用中, 每个地址多个 bit 好于每个地址 1 bit, or 二维内存阵列比一维高效

通常由内存里一个地址中写着的多位 bit 数据来表示某些电路任务

一些常用电路任务

• 自然数的加法
• 判断 bit 数据是否满足所需条件
• 跳转到其它指令的执行

假设一个指令在一个电路周期内完成 (单周期计算机)

Example add 指令. add x_1 x_2. 指令的 bit 数据位分为三个区域, 表示不同类型的信息

1. 读取 add 指令

   • add 指令在 adress_0 (add x_1 x_2 以及 adress_1, adress 2 来自源代码和编译器的生成)
   • 固定的内存地址 adress_of_instruction 存储的值 adress_0 被读出, add 指令的 index 区的数据被送到控制信号元件 (control unit), 然后计算出控制信号并输出 (细节太多, 见 ref-1)

2. 执行 add 指令

   • 输出的控制信号输入到内存的控制电路元件, 读出内存的 x_1 in adress_1 和 x_2 in adress_2, 将它们输入到算术元件 (ALU)
   • 根据输出控制信号, 算术元件的输出 x_1 + x_2 被写到 adress_1

3. 进入和读取下一个周期的指令

   • adress_of_instruction 存储的值 adress_0 被已经设计好的电路送到算术元件, 计算出 adress_0 + 1 i.e. 下一个指令地址, 被写到 adress_of_instruction 里面的数据. adress_0 + 1 将在下一个电路周期被执行

其它指令可能有多于两个的数据区 (非指令 index 区)

周期电路的速度远远高过人类速度 (1 GHz = 每秒 10^9 次周期)

高级编程语言的循环

i : int = 0;
while (i < 10) {
    i = i + 1;
} // result = 10

1. 读取指令

   bgt (branch_grater_than) 指令存储在 adress_0. (指令从源代码和编译器生成.) 10 在 bgt 的一个数据区, while loop 需要的指令流数量 3 在 bgt 的另一个数据区

2. 执行指令

   执行条件判断 $𝑖<10$

   读出 i 和 10, 在算术元件中比较大小, 根据结果给出控制信号, 结合指令 bgt index 区给出的控制信号

   根据条件判断的结果, 执行不同的任务

   • $𝑖<10$ 时

   算术元件根据此判断输出控制信号, 将 adress_of_instruction 存储的值改变为下一条指令的地址 adress_0 + 1

   • adress_0 + 1 的指令要执行任务 ${𝑖}_{\text{new }}={𝑖}_{\text{ old }}+1$

     用 add 指令计算 i + 1, 写回 adress_1

   • 执行完 add 后, 要回到下一次循环的判断 $𝑖<10?$

     add 指令的下一条指令是 jump 指令, 执行结果是, 修改 adress_of_instruction 的值为 adress_0, 实现指令的跳转, 进行下一次循环的判断 $𝑖<10?$

   • $𝑖\ge 10$ 时
   算术元件根据此判断, 输出控制信号, 将 adress_of_instruction 存储的值改变为 adress_0 + 3, 跳出 while 循环, 执行后面的指令

用 parser or compiler (编译器) 验证 token 流语言正确性, 本质上是遍历所有语言规则, 或使用生成的有限状态机

parser 的运行需要生成内存中大型复杂的数据结构 (一些形象的描述: 表格, 结点, 树)

如果数据流是高级编程语言源代码, 还可以根据这个数据结构生成指令流. 此时称为 compile (编译), 但 parse 和 compile 经常混用

如果语言规则很复杂, 可以对语言规则进行 (多次) 分类和分解, 先遍历分类, 再遍历分类里面的规则. Example 分开为 "syntax 检查" 和 "semantics 检查"