Convergent Infinite Computation and Applications
-
摘要: 经典计算不能很好地刻画无穷计算的行为.基于形式系统序列及其极限,讨论一类称为收敛无穷计算的问题,旨在建立刻画无穷计算在变化的环境中如何交互与演化以及演化的极限状态的逻辑理论基础.提出了收敛无穷计算的一个逻辑和推理系统,其表达能力超过一阶逻辑.还基于经典计算模型图灵(Turing)机和形式系统序列及其极限,提出了收敛无穷计算的模型,称为过程模式.在极限计算的意义下,其计算能力超过了Turing机和实数机器.讨论了上述研究在数据挖掘中的应用,用收敛无穷计算研究了数据挖掘的极限行为.Abstract: Classical computations can not capture the essence of infinite computations very well. This paper will focus on a class of infinite computations called convergent infinite computations and establish a logical framework for describing and analyzing how an infinite computation interacts and evolves in changing environments and what the limit of the evolution might be. A logic for convergent infinite computations was proposed by extending first order theories using Cauchy sequences,which has stronger expression power than the first order logic. A computation model,called procedure scheme,for convergent infinite computations was proposed,on the basis of classical Turing machine and formal theory sequences and their limits. It has stronger computing power than Turing machines and real machines in the sense of limit computations. As an example of application of the above study,the limit behavior of data mining was discussed by means of limits of theory sequences.
-
Key words:
- computation /
- distance /
- limits /
- convergent infinite computation /
- procedure scheme
-
[1] Abiteboul S,Vardi M Y, Vianu V. Computing with infinitary logic[J]. Theoretical Computer Science,1995,149(1):101~128. [2]Vardi M Y,Wolper P.Reasoning about infinite computations[J]. Information and Computation,1994,115(1):1~37. [3]李 未.一个开放的逻辑系统[J].中国科学(A辑),1992,10:1103~1113. [4]Blum L,Shub M,Smale S. On a theory of computation and complexity over the real numbers:NP-completeness,recursive function and universal machines,bull(New Series)[J]. Amer Math Soc,1989,21(1):1~46. [5]Chadzelek T,Hotz G.Analytic machines[J].Theoretical Computer Science,1999,219:151~167. [6]Nienhuys-Cheng S H. Distance between herbrand interpretations:a measurefor approximations to a target concept. In:Proceedings of the 7th International Workshop on Inductive Programming, 1997.LNAI1297. [7]Li W. A logical framework for inductive inference and its rationality. In:Fu N, ed.Advanced Topics in Artificial Intelligence, 1999.LNAI1747. [8]Dahr M. Deductive databases:theory and applications[M].USA:International Thomson Computer Press,1997. [9]Li W,Ma S,Sui Y,et al. A logical framework for convergent infinite computations. http://xxx.lanl.gov/abs/cs.lo/0105020. [10] Li W,Ma S. A framework for analytic-intelligent agents. In:Proceedings of the International Conference on Artificial Intelligence. Las Vegas:CSREA Press,2000.691~697. -
点击查看大图
计量
- 文章访问数: 2187
- HTML全文浏览量: 88
- PDF下载量: 1126
- 被引次数: 0
下载:
