基本交互算法：预览.pdfVIP

基本交互算法：预览

YuriGurevich

UniversityofMichigan,AnnArbor,MI,USA

本

译

中

1

v

8

9

7

5

0

8.交互的力量

0

5

2

:摘要

v

i

x

r本对话论文提供了对基本交互算法公理化即将进行的工作的预览和

a

初步感受。

现代算法的概念是在20世纪30年代至50年代阐明的。它在一个季

度世纪前被公理化为“顺序算法”或“经典算法”的概念；我们现在更

愿意称之为“基础算法”。这种公理化用于证明每一个基础算法都存在

一个行为等价的抽象状态机。它还被用来证明逻辑学家所理解的丘奇-

图灵论题。

自20世纪60年代起，算法的概念得到了扩展——概率算法、量子

算法等——这促使引入了一个更为宏大的丘奇-图灵论题版本，通常称

为“物理论题”。我们强调两个版本的丘church-turingthesis之间的区

别，并说明如何将非确定性和概率性算法视为具有适当预言机的基本算

法。同样的观点也适用于量子电路算法和其他许多类别的算法。

0部分得到美国陆军研究办公室W911NF25-1-0046的支持。

1抛硬币是算法性的吗？

Q:考虑抛硬币。这是算法吗？

A:你为什么要问？

Q:讨论随机化算法，涉及概率分布。这些分布源自物理过程，比如抛硬币。

所以一个问题出现了：谁抛硬币？我不明白算法是如何做到这一点的。必须

由外部代理来执行抛掷。

A:你也可以问量子测量是否是算法性的。

Q:那不是基本上是同一个问题吗？量子测量也产生一个概率分布。

A:好吧，如果你怀疑一个算法可以翻转一枚硬币，你可能会对一个算法执

行量子测量更加持怀疑态度。毕竟，这个过程涉及到了大自然母亲。

Q:但掷硬币也涉及自然母亲，不是吗？

A:你是对的。区别在于量子测量涉及我们不习惯且不完全理解的自然方面，

而硬币翻转已经被人们很好地理解了很长时间。

无论如何，我坚持传统的观点，认为算法本质上是确定性的，因此“非

确定性算法”是一个自相矛盾的说法。美国哲学家和棒球运动员约吉·贝拉

曾这样说明这一点：“当你来到道路的分岔口时，就走过去。”

Q:如何调和这种观点与“非确定性算法”这一术语的广泛使用？

A:这可能只是一个比喻。非确定性算法可以被视为与环境互动的确定性算

法，在这种环境中，有人会做出必要的选择，可能是通过抛硬币来决定。一

些作者认为一个由0和1组成的随机序列是输入的一部分，因此所需的选项

提前被确定。

或者——而且完全合理地——可以扩展算法的概念，就像数的概念被扩

展一样。从正整数一路扩展到实数，然后是复数及更远。

Q:让我们考虑一个非确定性算法的简单示例。

A:这是一个具有最小非确定性的经典尺规算法。设定是一个固定的欧几里

2

得平面。给定一个圆，其中心为，以及位于外的一点，该算法从构

造一条到的切线。

drawthemidpointbetweenand

drawthecirclecenteredatandpassingthrough

(1)

chooseapoin