Representation Theorems for Analytic Machines and Computability of Analytic Functions
Representation Theorems for Analytic Machines and Computability of Analytic Functions
复制标题
解析机的表示定理和解析函数的可计算性
DOI：
--
复制
发表时间：
2012
影响因子：
0.5
通讯作者：
G. Hotz
中科院分区：
文献类型：
--
作者：
Tobias Gärtner;G. Hotz
本文给出了关于解析机的一些结果，解析机是由Hotz引入的一种实际计算模型，它通过无限收敛计算扩展了著名的Blum， Shub和Smale机（BSS机）。众所周知的BSS机器的表示定理阐明了在BSS模型中可计算的函数的结构：这样一个函数的域划分为可数的许多半代数集，并且在这些集上的每个函数都是多项式。有理函数。本文研究了在单变量情况下，表示定理是否可以推广到解析机，即解析机可计算的函数是否可以在其定义域内用幂级数表示。我们证明了这个问题在实数上是负的，而在复数上的函数在一定的限制下是正的。然后，我们使用机器模型定义了单变量复解析函数（即全纯）的可计算性，并特别研究了一类具有解析可计算幂级数展开的解析函数。我们证明了该类在基本解析运算复合、局部反演和解析延拓下是封闭的。
We present results concerning analytic machines, a model of real computation introduced by Hotz which extends the well-known Blum, Shub and Smale machines (BSS machines) by infinite converging computations. The well-known representation theorem for BSS machines elucidates the structure of the functions computable in the BSS model: the domain of such a function partitions into countably many semi-algebraic sets, and on each of those sets the function is a polynomial resp. rational function. In this paper, we study whether the representation theorem can, in the univariate case, be extended to analytic machines, i.e. whether functions computable by analytic machines can be represented by power series in some part of their domain. We show that this question can be answered in the negative over the real numbers but positive under certain restrictions for functions over the complex numbers. We then use the machine model to define computability of univariate complex analytic (i.e. holomorphic) functions and examine in particular the class of analytic functions which have analytically computable power series expansions. We show that this class is closed under the basic analytic operations composition, local inversion and analytic continuation.