迭代函数及其可计算性  

作　　者：阎志欣 黄盛萍 

出　　处：《软件学报》1996年第A00期232-238,共7页Journal of Software

摘　　要：带迭代算子的函数式程序设计语言是一种有坚实理论基础、高效的、实际有用的高级程度设计语言，该语言既可描述递归，又可描述迭代，本文证明了仅用迭代算子由已知迭代函数定义的部分迭代函数变可计算部分递归函数，这就等于证明任何图灵可计算的部分函数，都可用有坚实数学基础的部分迭代函数高效地进行计算，文中定义了复合算子、原始迭代和最小化迭代子及部分迭代函数；证明了部分递归函数是部分迭代函数可计算的。

关 键 词：迭代函数 递归函数 可计算性 

分 类 号：O174[理学—数学]