无状态多计数器机器的计算能力研究

### 无状态多计数器机器的计算能力研究 在计算理论中，无状态机器是一类独特的计算模型，因其没有状态，其移动仅依赖于输入头扫描的符号和存储单元的局部部分。本文聚焦于具有反转受限计数器的无状态多计数器机器，深入探讨其计算能力。 #### 无状态多计数器机器概述 无状态机器的输入字符串接受方式与有状态机器不同。例如，对于下推自动机（PDA），接受方式是“空”栈。已知有状态的非确定性PDA与无状态的非确定性PDA等价，但确定性情况下并非如此。对于图灵机，有状态版本的计算能力强于无状态版本。 本文研究的无状态多计数器机器具有m个计数器，在由左右端标记界定的单向输入上运行。机器的移动仅取决于输入头下的符号和计数器的符号（指示计数器是否为零）。当输入头从左端标记开始，所有计数器为零，最终到达右端标记且所有计数器再次为零时，输入字符串被接受。此外，机器是k反转受限的，即对于指定的k，任何计算中，计数器在增加模式和减少模式之间的交替次数不超过k次。 #### 无状态多计数器机器的规则与类型 确定性无状态单向m计数器机器在形式为cw$的输入上运行，其中c和$是左右端标记。计算开始时，输入头位于左端标记c，所有m个计数器为零。机器的移动由一组规则描述： \((x, s_1, .., s_m) →(d, e_1, ..., e_m)\) 其中： - \(x ∈Σ ∪\{c, $}\)，Σ是输入字母表。 - \(s_i\)是计数器\(C_i\)的符号（0表示零，1表示正）。 - \(d = 0\)或1（输入头移动方向，\(d = 0\)表示不移动，\(d = 1\)表示向右移动一个单元）。 - \(e_i = +, −, 或 0\)（将计数器i加1、减1或不改变计数器i），且\(e_i = -\)仅在\(s_i = 1\)时适用。 由于机器是确定性的，没有两条规则可以有相同的左侧。当机器到达输入头位于右端标记$且所有计数器为零的配置时，输入w被接受。 无状态机器有两种类型： - 实时机器：每次移动\(d = 1\)，即输入头每步向右移动。当输入头到达$时，所有计数器为零以实现接受。 - 非实时机器：\(d\)可以为0或1。当输入头到达$时，机器可以继续计算，直到所有计数器变为零后接受。本文主要关注确定性实时机器。 #### 无状态实时多计数器机器 即使在输入字母表为单字母表\(Σ = \{a\}\)的情况下，无状态实时多计数器机器也具有强大的计算能力。由于是实时机器，规则\((x, s_1, .., s_m) →(d, e_1, ..., e_m)\)中\(d = 1\)，可简化为\((x, s_1, ..., s_m) →(e_1, ..., e_m)\)。 我们将m计数器机器计算过程中可能出现的符号向量\(v = (s_1, .., s_m)\)称为符号向量，它可以表示为长度为m的二进制字符串\(s_1 · · · s_m\)，也可以等价表示为集合\(\{1, 2, ..., m\}\)的子集S。字符串\(0^m\)表示所有计数器为零。 **定理1**：每个由无状态实时多计数器机器M接受的\(Σ = \{a\}\)上的语言形式为\(a^r(a^s)^*\)，其中\(r, s ≥0\)。 - **证明思路**： - 若\((c, 0^m) →0^m\)是M的移动，则M接受ε或\(Σ^*\)。分两种情况：若M没有\((a, 0^m) →(e_1, ..., e_m)\)形式的移动，则接受输入为c$，此时\(r = s = 0\)；若有\((a, 0^m) →0^m\)的移动，则接受\(Σ^*\)，对应\(r = 0, s = 1\)。 - 若\((c, 0^m) →S\)（\(S ≠ 0^m\)）是M的移动，则M接受单例或无限语言。设r是M接受\(a^r\)的最小整数，当机器读取$前的a时，符号向量为非空的\(S_r\)。再分两种情况：若\((a, 0^m) →0^m\)是规则，则接受\(a^rΣ^*\)；若\((a, 0^m) →S\)（\(S ≠ 0^m\)）是规则，设s是使M接受\(a^{r + s}\)的最小正整数，若不存在则接受单例\(a^r\)，否则\(a^{r + ks} ∈L\)（\(k ≥0\)）。 #### 1 - 反转机器 我们关注接受单例语言\(L = \{a^n\}\)的机器，推导最大n的精确值，并证明实现该n的机器程序在计数器索引重标记的情况下是唯一的。 接受非空单例的m计数器机器的接受计算可表示为： \(0^m →S_1 →S_2 →· · · →S_r →0^m\) 其中\(S_i ≠ 0^m\)（\(1 ≤i ≤r\)），箭头表示机器每次移动后的符号向量序列。这样的机器接受单例语言\(\{a^r\}\)，即能计数到r。 借鉴马尔可夫链理论的术语，非空符号向量S若在上述序列中仅出现一次，则为瞬态；若出现多次，则为循环态。瞬态S仅贡献一次移动，而循环态S在计算过程中会多次“重新进入”。 下面是几个关于1 - 反转机器接受单例的引理： - **引理1**：若S是循环态，且\(S'\)出现在S的两次出现之间，则\(S ⊆S'\)。 - **证明**：假设\(j ∈S\setminus S'\)，计数器\(C_j\)在计算开始时为零，在S首次出现时非零，在\(S'\)出现时或之前为零。由于机器是1 - 反转的，计数器\(C_j\)在S第二次出现时不可能再次非零。 - **引理2**：若S是循环态，且\(S'\)出现在S的两次出现之间，则\(S' = S\)。 - **证明**：假设S的首次出现后是\(S''\)，即\(S →S'' →· · · →S' →· · · →S\)。先证明\(S'' ⊆S\)，假设\(j ∈S'' \setminus S\)，则在S处计数器\(C_j\)必须从0增加到1，但由于机器是1 - 反转的，在两个S处不能多次发生这种情况，所以\(S'' ⊆S\)。由引理1可知\(S ⊆S''\)，因此\(S = S''\)，进而所有出现在S两次出现之间的符号向量\(S'\)都等于S。 - **引理3**：设\(S_1, S_2, . . . , S_d\)是接受单例的1 - 反转m计数器机器M计算中出现的不同非空符号向量，则\(d ≤2^m - 1\)。 - **证明**：令\(S_0 = S_{d + 1} = 0^m\)，考虑\(m × (d + 2)\)的二进制矩阵B，其中第j列是\(S_{j - 1}\)（\(1 ≤j ≤d + 2\