首页    期刊浏览 2024年11月29日 星期五
登录注册

文章基本信息

  • 标题:Mutual Dimension
  • 本地全文:下载
  • 作者:Adam Case ; Jack H. Lutz
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2014
  • 卷号:2014
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    We define the lower and upper mutual dimensions mdim ( x : y ) and Mdim ( x : y ) between any two points x and y in Euclidean space. Intuitively these are the lower and upper densities of the algorithmic information shared by x and y . We show that these quantities satisfy the main desiderata for a satisfactory measure of mutual algorithmic information. Our main theorem, the data processing inequality for mutual dimension, says that, if f : R m R n is computable and Lipschitz, then the inequalities mdim ( f ( x ) : y ) m dim ( x : y ) and Mdim ( f ( x ) : y ) M dim ( x : y ) hold for all x R m and y R t . We use this inequality and related inequalities that we prove in like fashion to establish conditions under which various classes of computable functions on Euclidean space preserve or otherwise transform mutual dimensions between points.

  • 关键词:computable analysis ; data processing inequality ; effective fractal dimensions ; Kolmogorov complexity ; mutual information
国家哲学社会科学文献中心版权所有