Fractran的复杂性与程序生产率分析

# Fractran的复杂性与程序生产率分析 ## 相关工作概述 在之前的研究中，对一阶项重写系统（TRS）不同性质的不可判定性进行了分析。TRS的标准性质通常是 $\Sigma_0^1$ 或 $\Pi_0^2$ 完全的，而依赖对问题的复杂性本质上是解析性的，为 $\Pi_1^1$ 完全。这些结果为后续生产率的 $\Pi_1^1$ 和 $\Sigma_1^1$ 完全性结果提供了基础。 此外，有研究表明流规范的相等性是 $\Pi_0^2$ 完全的，这一结果可作为Fractran程序到流规范转换的推论。同时，正交流规范生产率的 $\Pi_0^2$ 完全性也有相关研究，后续将考虑更一般的TRS和任意评估策略下的生产率，进一步强化了该结果。 ## Fractran程序 ### Fractran程序的一步计算 Fractran程序的一步计算是一个部分函数。设 $P = \frac{p_1}{q_1}, \cdots, \frac{p_k}{q_k}$ 是一个Fractran程序，部分函数 $f_P : \mathbb{N} \rightharpoonup \mathbb{N}$ 定义如下： \[ f_P(n) = \begin{cases} n \cdot \frac{p_i}{q_i}, & \text{其中 } \frac{p_i}{q_i} \text{ 是 } P \text{ 中使得 } n \cdot \frac{p_i}{q_i} \in \mathbb{N} \text{ 的第一个分数} \\ \text{未定义}, & \text{如果不存在这样的分数} \end{cases} \] 若存在 $i \in \mathbb{N}$ 使得 $f_P^i(n)$ 未定义，则称 $P$ 在 $n$ 处停机。当 $m = f_P(n)$ 时，记为 $n \to_P m$。 例如，生成素数的Fractran程序对于所有起始值 $n_0$ 都不会停机，因为任何整数与 $\frac{55}{1}$ 的乘积仍是整数。但一般来说，Fractran程序的终止性是不可判定的。 ### Fractran程序的统一停机问题 定理表明，Fractran程序的统一停机问题，即判定一个程序对于每个起始值 $n_0 \in \mathbb{N}_{>0}$ 是否停机，是 $\Pi_0^2$ 完全的。 相关地，广义Collatz问题（GCP）也是 $\Pi_0^2$ 完全的。GCP是判定对于一个Collatz函数 $f$，是否对于每个整数 $x > 0$ 都存在 $i \in \mathbb{N}$ 使得 $f^i(x) = 1$。每个Fractran程序 $P$ 都可以看作一个Collatz函数 $f_P'$，通过将 $f_P$ 中未定义的值替换为 $1$ 得到。因此，GCP是 $\Pi_0^2$ 困难的。 ### 从图灵机到Fractran程序的转换 为证明Fractran程序统一停机问题的定理，设计了从图灵机到Fractran程序的转换。使得得到的Fractran程序对于所有正整数（$n_0 \geq 1$）停机，当且仅当图灵机在所有配置下都终止。这样就将图灵机的统一停机问题归约到了Fractran程序的统一停机问题。 为简化转换，限制使用只有两个符号 $\{0, 1\}$（$0$ 为空白符号）的一元图灵机。一元图灵机 $M$ 是一个三元组 $\langle Q, q_0, \delta \rangle$，其中 $Q$ 是有限状态集，$q_0$ 是初始状态，$\delta : Q \times \{0, 1\} \rightharpoonup Q \times \{0, 1\} \times \{L, R\}$ 是部分转移函数。 #### 转换步骤 1. **选择质数**：设 $M = \langle Q, q_0, \delta \rangle$ 是一个图灵机，选择两两不同的质数 $tape_{\ell}, h, tape_r, tape'_{\ell}, h', tape'_r, m_{L,x}, m_{R,x}, copy_x$ 和 $p_q$（对于每个 $q \in Q$ 和 $x \in \{0, 1\}$），它们分别代表图灵机的不同部分和操作。 2. **定义Fractran程序**：Fractran程序 $P_M$ 由以下分数组成： - $\frac{1}{p \cdot p'}$，对于 $p, p' \in \{m_{L,0}, m_{L,1}, m_{R,0}, m_{R,1}, copy_0, copy_1\}$，$p, p' \in \{p_q | q \in Q\}$ 和 $p, p' \in \{h, h'\}$，用于去除非法配置。 - $\frac{m_{L,1 - x} \cdot tape'_{\ell}}{m_{L,x} \cdot tape_{\ell}^2}, \frac{m_{L,1 - x} \cdot tape'_r^2}{m_{L,x} \cdot tape_r}, \frac{m_{L,1 - x} \cdot tape'_r}{m_{L,x} \cdot h'}, \frac{m_{L,1 - x} \cdot h}{m_{L,x} \cdot tape_{\ell}}, \frac{copy_0}{m_{L,x}}$（$x \in \{0, 1\}$），用于磁带头部向左移动。 - $\frac{m_{R,1 - x} \cdot tape'_r}{m_{R,x} \cdot tape_r^2}, \frac{m_{R,1 - x} \cdot tape'_{\ell}^2}{m_{R,x} \cdot tape_{\ell}}, \frac{m_{R,1 - x} \cdot tape'_{\ell}}{m_{R,x} \cdot h'}, \frac{m_{R,1 - x} \cdot h}{m_{R,x} \cdot tape_r}, \frac{copy_0}{m_{R,x}}$（$x \in \{0, 1\}$），用于磁带头部向右移动。 - $\frac{copy_{1 - x} \cdot tape_{\ell}}{copy_x \cdot tape'_{\ell}}, \frac{copy_{1 - x} \cdot tape_r}{copy_x \cdot tape'_r}, \frac{1}{copy_x}$（$x \in \{0, 1\}$），用于将临时磁带内容复制回主磁带。 - $\frac{p_{q'} \cdot h'^{s'} \cdot m_{d,0}}{p_q \cdot h}$（当 $\delta(q, 1) = \langle q', s', d \rangle$ 时）和 $\frac{p_{q'} \cdot h'^{s'} \cdot m_{d,0}}{p_q}$（当 $\delt