有序环（域）下的程序计算与BSS机器计算

PROGRAMMING COMPUTATION AND BSS-MACHINE COMPUTATION OVER ORDERED RINGS AND FIELDS

１９８９年Ｂｌｕｍ，Ｓｈｕｂ与Ｓｍａｌｅ提出了在实数域上的一个计算模型（本文称其为ＢＳＳ机器计算模型）．ＢＳＳ机器计算模型主要是基于（有穷）有向图的，它很直观但没有形式化，不方便使用经典的离散的计算理论中的许多成熟的工具．本文从程序设计系统出发，提出一种在任意有序环（域）下的很自然的程序设计语言，严格定义了它的语法与语义，研究了它与ＢＳＳ机器计算的关系，证明了本文的程序设计计算与ＢＳＳ有穷维机器计算的等价性．

In 1989 Blum, Shub and Smale introduced a model for computations over the real numbeds (and other rings as well) which is now usually called a BSS machine. The important difference with the Turing model is that real numbers are treated as basic entities and that arithmetic operations on the reals are performed in a single step. In the paper, we propose a programming version of the Blum-ShubSmale machine model of computation over the real numbers. The programming model for machines and computation over the real numbers is called Turing-BSS programming computation, which is equated to Blum-Shub-Smale's theory of computation over the real numbers.