Page 21 - 《软件学报》2026年第1期

18 软件学报 2026 年第 37 卷第 1 期

)
F 1 (n)-放大器的构造是平凡的, 例如图 9 Ampl 1 = P 1 ,X 1 , a ,b ,c ,(a 1 ,b 1 ,c 1 ),Z 1 , 其中,
(
(
)
′
′
′
P 1 给出了
中程序
1 1 1
{
}
{
}
X 1 = a 1 ,b 1 ,c 1 ,a ,b ,c ,t 1 , Z 1 = a ,b ,c ,t 1 . 容易验证其满足放大器的性质, 因为 F 1 (n) = 2n Ampl 1 是 F 1 (n)-放大
,
′
′
′
′
′
′
1 1 1 1 1 1
t 1 , 但为了后文叙述方便, 还是假设存在这样一个计数器.
器. 这里根本没有使用到辅助计数器
)
(
(
)
′
′
′
假设对某个 k ⩾ 1, 我们已经得到了一个 F d (n)-放大器 Ampl k = P k ,X k , a ,b ,c ,(a k ,b k ,c k ),Z k , 其中, Z k =
k k k
a ,b ,c ,t , 需构造出一个 F k + 1 (n)-放大器. 由于计数器程序表达能力有限, 直接构造难度较大, 不妨先构造一个测
{ }
′
′
′
′
k
k
k
{
{
零计数器机器. 考察图 9 P ′ Z k+1 = b ′ } , X k+1 = X k ∪ a ′ ,b ′ ,c ′ } .
中的计数器机器
k+1 , 令 k+1 k+1 k+1 k+1

k b′ +=1;
loop loop a′ +=1, k c′ +=1;
k
1 a′ -=1, 1 a +=1; loop
loop k P ; zero? a′ , b′ , c′ , t ; k
k
k
k
1 b′ -=1, 1 b +=2; loop a -=1, k a′ +=1;
k
loop loop b -=1, k b′ +=1;
k
1 c′ -=1, 1 c +=2; loop c -=1 , k c′ +=1;
k
zero? a , b , c ; b + ′ -=1;
k k k k 1
P 1 P′ k+1
图 9 F d (n) -放大器的递归构造

● 假设某 Z k + 1 -执行从格局乘法三元组 τ s = a ′ k+1 ,b ′ k+1 ,c ′ k+1 ,A s ,B,X k+1 出发, 则前两行可以对任意 A 0 ∈ N 构造乘
(
)
( )
′ ′ ′ Ampl k 是 τ = (a k ,b k ,c k ,A ,
′
′
法三元组 τ 0 = a ,b ,c ,A 0 ,1,X k ; 因为 F k (n)-放大器, 对 Z k 的测零保证执行 P k 后得到
k k k 0 0
F k (1),X k ), 随后的 3 个循环配合对 a k 、b k 、c k 的测零使得下一次执行 P k 前格局为 τ 1 = a ,b ,c ,A 1 ,F k (1),X k , 其中,
(
)
′
′
′
k k k
′ ( ′ ′ ′ )
A 1 = A ; Z k + 1 -执行保证了最终 P k 被准确执行 B 次, 从而终止格局为 τ B = a ,b ,c ,A B ,F k+1 (B),X k .
0
k
k
k
A B−1 ∈ N 使得 Z k -执行一次第 2 个 loop 语句的循环体可以从
● 相反, 给定 A B ∈ N, 由 Ampl k 的性质知: 存在
( ) ( )
′
τ B−1 = a ,b ,c ,A B−1 ,F (B−1) (1),X k 计算出 τ B = a ,b ,c ,A ,F (B) (1),X k , 其中, A ⩾ A B . 不断向前推导可知, 最终存在
′
′
′
′
′
′
′
k k k k k k k B k B
(
A 0 ∈ N 使 得 Z k -执 行 B 次 相 关 语 句 可 以 实 现 从 τ 0 = a ,b ,c ,A 0 ,1,X k 计 算 出 τ B = a ,b ,c ,A ,F k+1 (B) 并 使 得
)
(
)
′
′
′
′
′
′
′

k
B
k
k
k
k
k
A ⩾ A B . 若第 1 个 loop 恰好循环 A 0 次, 我们可以构造出 , 从而使得 P ′ 可以 Z k + 1 -计算出 τ B .
′
B τ 0 k+1
目前 P ′ k+1 可以完成 F k + 1 (n)-放大器的功能, 但因其使用了测零操作故不是计数器程序. 接下来的关键是构造
计数器程序去模拟实现 P ′ 中的两处测零语句. 这需要引入更多新计数器, 也需要更多控制计数器 (注意, 目前
k+1
{ }
Z k+1 = b ′ k+1 ). 接下来两节分别阐述基于控制计数器的方法和后续的优化.
3.3.1 控制计数器方法
本节介绍 Czerwiński 等人 [14] 是如何通过引入额外的控制计数器将图 9 中的计数器机器转换为计数器程序的.
此方法看似复杂, 其本质是基于一个简单的事实: 若干个非负整数之和为 0 当且仅当每个整数都为 0. 在第 4 节中,
我们还能看到该方法的其他相关应用.
考虑图 9 中的 P ′ , 其中对 a k 等计数器进行了多次测零, 故考虑: 若对单计数器 a 进行了 次测零, 至多需要
k
k+1
α 0 ,...,α k−1 , 则这次执行可以表示为:
引入多少控制计数器才能完成模拟? 假设测零前格局分别为

zero?, +d 1 zero?, +d 2 zero?, +d k−1 zero?
α 0 −−−−−−→ α 1 −−−−−−→ ... −−−−−−−→ α k−1 −−−→ 0 (9)
′
a
′
平凡的方式是每次测零后不再修改 a 并引入一个副本 , 将剩下对 a 的操作都转移到 a 上. 但这样需要线性
∑ k−1
个计数器, 对下界的证明十分不利. 注意, 所有计数器的值都是非负的, 因此 α i (a) = 0 当且仅当 α i (a) = 0 对
i=0
∑
k−1
t
t
0 ⩽ i ⩽ k −1 都成立, 我们只需使用辅助计数器 记录 α i (a), 最终对 测零即可. 应用阿贝尔变换得到:
i=0

∑
k−1
(10)
α i (a) = kα 0 (a)+(k −1)d 1 +(k −2)d 2 +...+d k−1
i=0
因此可以仅使用一个额外的维度按如下方式完成记录:

 
   
 α k−1 
 α 0  zero?, +d 1  α 1  zero?, +d 2 zero?, +d k−1    
     
     −−−→ 0 (11)
  −−−−−−→   −−−−−−→ ... −−−−−−−→  ∑ k−1 

     
kα 0 (a) +(k−1)d 1 kα 0 (a)+(k −1)d 1 +(k−2)d 2 +d k−1  α i (a)  zero?
i=0
此方法被称作控制计数器方法 (controlling counter technique) [14] , 并且可以推广到多个计数器测零次数已知的
情形上.