Comparison between the complexity of a function and the complexity of its graph

作     者：Durand, B Porrot, S 

作者机构：LIM CMI F-13453 Marseille 13 France Univ Sci & Technol Lille LAIL F-59655 Villeneuve Dascq France Univ Sci & Technol Lille LIFL F-59655 Villeneuve Dascq France 

出 版 物：《THEORETICAL COMPUTER SCIENCE》 (理论计算机科学)

年 卷 期：2002年第271卷第1-2期

页      面：37-46页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：Kolmogorov complexity recursive infinite sequences data flow complexity 

摘      要：This paper investigates in terms of Kolmogorov complexity the differences between the information necessary to compute a recursive function and the information contained in its graph. Our first result is that the complexity of the initial parts of the graph of a recursive function, although bounded, has almost never a limit. The second result is that the complexity of these initial parts approximate the complexity of the function itself in most cases (and in the average) but not always. (C) 2002 Elsevier Science B.V. All rights reserved.