重新定义基础算法，统一解释概率、量子等复杂算法的本质。
Basic interactive algorithms: Preview
- 用公理化方法统一描述各类算法，包括概率与量子算法。
- 证明所有基础算法都可等价为抽象状态机，支持逻辑上的完备性。
- 适合对算法理论、计算哲学感兴趣的读者深入研读。
本文提供了一篇即将发表的关于基础交互算法公理化的预览。现代算法概念在1930至1950年代被阐明，25年前以“顺序算法”或“经典算法”形式完成公理化，现更倾向于称其为“基础算法”。该公理化体系证明了每个基础算法均存在行为等价的抽象状态机，并用于逻辑上验证了教皇-图灵论题。自1960年代起，算法概念扩展至概率算法、量子算法等，催生了更雄心勃勃的“物理论题”。本文强调两种教皇-图灵论题的区别，指出非确定性与概率算法可通过适当预言机视为基础算法；此视角同样适用于量子电路算法及其他算法类别。
原文摘要 · Abstract (English)
This dialog paper offers a preview and provides a foretaste of an upcoming work on the axiomatization of basic interactive algorithms. The modern notion of algorithm was elucidated in the 1930s--1950s. It was axiomatized a quarter of a century ago as the notion of ``sequential algorithm'' or ``classical algorithm''; we prefer to call it ``basic algorithm" now. The axiomatization was used to show that for every basic algorithm there is a behaviorally equivalent abstract state machine. It was also used to prove the Church-Turing thesis as it has been understood by the logicians. Starting from the 1960s, the notion of algorithm has expanded -- probabilistic algorithms, quantum algorithms, etc. -- prompting introduction of a much more ambitious version of the Church-Turing thesis commonly known as the ``physical thesis.'' We emphasize the difference between the two versions of the Church-Turing thesis and illustrate how nondeterministic and probabilistic algorithms can be viewed as basic algorithms with appropriate oracles. The same view applies to quantum circuit algorithms and many other classes of algorithms.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。