On a theory of computation over the real numbers; NP completeness, recursive functions and universal machines
On a theory of computation over the real numbers; NP completeness, recursive functions and universal machines
复制标题
论实数的计算理论；
DOI：
--
复制
发表时间：
1988
期刊：
影响因子：
--
通讯作者：
S. Smale
中科院分区：
文献类型：
--
作者：
L. Blum;M. Shub;S. Smale
本文给出了任意（有序）环R上的计算模型。在这个一般的设置，通用机，部分递归函数，NP完全问题。虽然该理论反映了Z上的经典（例如，可计算函数是递归函数），但它也反映了基础环R的特殊数学性质（例如，Julia集的补集提供了实数上递归可判定不可判定集的自然例子），并为研究数值分析中算法的基础问题提供了自然的背景。<<ETX>>
A model for computation over an arbitrary (ordered) ring R is presented. In this general setting, universal machines, partial recursive functions, and NP-complete problems are obtained. While the theory reflects of classical over Z (e.g. the computable functions are the recursive functions), it also reflects the special mathematical character of the underlying ring R (e.g. complements of Julia sets provide natural examples of recursively enumerable undecidable sets over the reals) and provides a natural setting for studying foundational issues concerning algorithms in numerical analysis.<<ETX>>