| 摘要: |
| 带迭代算子的函数式程序设计语言是一种有坚实理论基础、高效的、实际有用的高级程序设计语言．该语言既可描述递归，又可描述迭代．本文证明了仅用迭代算子由已知迭代函数定义的部分迭代函数就可计算部分递归函数．这就等于证明任何图灵可计算的部分函数．都可用有坚实数学基础的部分迭代函数高效地进行计算．文中定义了复合算子、原始迭代和最小化迭代算子及部分迭代函数；证明了部分递归函数是部分迭代函数可计算的． |
| 关键词: 函数式语言，原始迭代算子，最小化迭代算子，部分迭代函数，计算能力． |
| DOI： |
| 分类号: |
| 基金项目:本文研究得到南京大学计算机软件研究所基金和航空科学技术基金资助. |
|
| ITERATION FUNCTIONS AND THEIR COMPUTABILITY |
|
Yan Zhixin,Huang Shengping
|
| Abstract: |
| Function programming language with iteration operator is an efficient，useful and practical，high—level programming language with sound theoretical foundation．It can represent recursion and iteration．This paper proved that partial iteration functions which are defined by iteration operators from given iteration functions can compute partial recur-sion functions．It means that any turing computable partial functions can be c6mputed effi-ciently by iteration functions with sound theoretical foundation．In this paper,the authors defined the composition operator，primitive iteration operator，minimization iteration oper-ator and partial iteration functions．Then they proved that partial reeursion functions can be computed by partial iteration functions． |
| Key words: Function language,primitive iteration operator,minimization iteration opera-tor,partial iteration function,computability． |
