论文标题
递归算法的行为理论
A Behavioural Theory of Recursive Algorithms
论文作者
论文摘要
“什么是算法？”是计算机科学的基本问题。 Gurevich的顺序算法的行为理论（又称顺序ASM论文）通过公理地定义（非确定性的）顺序算法给出了部分答案，而无需参考特定的机器模型或编程语言，并表明它们被（非可确定性）顺序摘要机器捕获。 Moschovakis指出，该理论不涵盖递归算法（如Mergesort）。在本文中，我们提出了对顺序递归算法概念的公理定义，该定义通过递归假设扩展了Gurevich的公理作为顺序算法，并允许我们证明顺序递归算法是由recursive抽象的状态机器捕获的，该机械是通过呼叫规则扩展Nd-Sepeq aSMS的扩展。应用此递归ASM论文产生了顺序递归算法作为有限组成的并发算法的表征，其同时运行的所有均为部分顺序运行。
"What is an algorithm?" is a fundamental question of computer science. Gurevich's behavioural theory of sequential algorithms (aka the sequential ASM thesis) gives a partial answer by defining (non-deterministic) sequential algorithms axiomatically, without referring to a particular machine model or programming language, and showing that they are captured by (non-deterministic) sequential Abstract State Machines (nd-seq ASMs). Moschovakis pointed out that recursive algorithms such as mergesort are not covered by this theory. In this article we propose an axiomatic definition of the notion of sequential recursive algorithm which extends Gurevich's axioms for sequential algorithms by a Recursion Postulate and allows us to prove that sequential recursive algorithms are captured by recursive Abstract State Machines, an extension of nd-seq ASMs by a CALL rule. Applying this recursive ASM thesis yields a characterization of sequential recursive algorithms as finitely composed concurrent algorithms all of whose concurrent runs are partial-order runs.
