检索结果-内蒙古大学图书馆

Optimal program-size complexity for Self-Assembled Squares at Temperature 1 in 3D

ALGORITHMICA 2017年第4期77卷 1240-1282页

作者： Furcy, David Micka, Samuel Summers, Scott M. Univ Wisconsin Oshkosh Dept Comp Sci Oshkosh WI 54901 USA Montana State Univ Dept Comp Sci Bozeman MT 59717 USA

Working in a three-dimensional variant of Winfree's abstract Tile Assembly Model, we show that, for all , there is a tile set that uniquely self-assembles into an square shape at temperature 1 with program-size complexity of (the program-size complexity, also known as tile complexity, of a shape is the minimum number of unique tile types required to uniquely self-assemble it). Note that this tile complexity is optimal for all algorithmically random values of N. Moreover, our construction is "just barely" 3D in the sense that it works even when the placement of tiles is restricted to the and planes. This result affirmatively answers an open question from Cook et al. (SODA 2011). To achieve this result, we develop a general 3D temperature 1 optimal encoding construction, reminiscent of the 2D temperature 2 optimal encoding construction of Soloveichik and Winfree (SIAM J Comput 36(6):1544-1569, 2007), and perhaps of independent interest. We also develop a more sophisticated 3D temperature 1 optimal encoding construction that places asymptotically fewer tiles than our original optimal encoding construction. We use the method of conditional determinism of Lutz and Shutters (Theory Comput Syst 51(3):372-400, 2012) to prove the correctness of our constructions.

关键词： Algorithmic self-assembly Optimal encoding DNA computing program-size complexity

来源：评论

学校读者我要写书评

暂无评论

program-size versus Time complexity Slowdown and Speed-up Phenomena in the Micro-cosmos of Small Turing Machines

引用

INTERNATIONAL JOURNAL OF UNCONVENTIONAL COMPUTING 2011年第5期7卷 353-387页

作者： Joosten, Joost J. Soler-Toscano, Fernando Zenil, Hector Univ Barcelona Dept Log Hist & Filosofia Ciencia E-08007 Barcelona Spain Univ Seville Dept Filosofia Log & Filosofia Ciencia Grp Log Lenguaje & Informac Seville Spain Univ Sheffield Regent Court Kroto Res Inst Sheffield S14DP S Yorkshire England

The aim of this paper is to undertake an experimental investigation of the trade-offs between program-size and time computational complexity. The investigation includes an exhaustive exploration and systematic study of the functions computed by the set of all 2-color Turing machines with 2 states -we will write (2,2)- and 3 states -we write (3,2)- with particular attention to the runtimes, space-usages and patterns corresponding to the computed functions when the machines have access to larger resources (more states). We report that the average runtime of Turing machines computing a function increases -with a probability close to one- with the number of states, indicating that machines not terminating (almost) immediately tend to occupy all the resources at hand. We calculated all time complexity classes to which the algorithms computing the functions found in both (2,2) and (3,2) belong to, and made comparison among these classes. For a selection of functions the comparison is extended to (4,2). Our study revealed various structures in the micro-cosmos of small Turing Machines. Most notably we observed "phase-transitions" in the halting-probability distribution. Moreover, it is observed that small initial segments fully define a function computed by a TM.

关键词： small Turing machines program-size complexity Kolmogorov-Chaitin complexity space/time complexity computational complexity algorithmic complexity

来源：评论

学校读者我要写书评

暂无评论

Entropic measures, Markov information sources and complexity

引用

APPLIED MATHEMATICS AND COMPUTATION 2002年第2-3期132卷 369-384页

作者： Calude, CS Dumitrescu, M Univ Auckland Dept Comp Sci Auckland 1 New Zealand Univ Bucharest Fac Math R-70109 Bucharest Romania

The concept of entropy plays a major part in communication theory. The Shannon entropy is a measure of uncertainty with respect to a priori probability distribution. In algorithmic information theory the information content of a message is measured in terms of the size in bits of the smallest program for computing that message. This paper discusses the classical entropy and entropy rate for discrete or continuous Markov sources, with finite or continuous alphabets, and their relations to program-size complexity and algorithmic probability. The accent is on ideas, constructions and results;no proofs will be given. (C) 2002 Elsevier Science Inc. All rights reserved.

关键词： Shannon's entropy entropy rate program-size complexity algorithmic probability

来源：评论

学校读者我要写书评

暂无评论

On partial randomness

引用

ANNALS OF PURE AND APPLIED LOGIC 2006年第1-3期138卷 20-30页

作者： Calude, CS Staiger, L Terwijn, SA Univ Auckland Dept Comp Sci Auckland New Zealand Univ Halle Wittenberg Inst Informat D-06099 Halle Saale Germany Vienna Tech Univ Inst Discrete Math & Geometry A-1040 Vienna Austria

If x = x(1)x(2) center dot center dot center dot x(n)center dot center dot center dot is a randorn sequence, then the sequence y = 0x(1)0x(2) center dot center dot center dot 0x(n)center dot center dot center dot is clearly not random;however, y seenis to be "about half' random", L. Staiger [Kolmogorov complexity and Hausdorff dimension, Inform. and Comput. 103 (1993) 159-194 and A tight upper bound on Kolmogorov complexity and uniformly optimal prediction, Theory Comput. Syst. 31 (1998) 215-229] and K. Tadaki [A generalisation of Chaitin's halting probability Q and halting self-similar sets, Hokkaido Math. J. 31 (2002) 219-253] have studied the degree of randomness of sequences or reals by measuring their "degree of compression". This line of study leads to various definitions of partial randomness. In this paper we explore some relations between these definitions. Among other results we obtain a characterisation of Sigma(1)-dimension (as defined by Schnorr and Lutz in terms of martingales) in terms of strong Martin-Lof epsilon-tests (a variant of Martin-Lof tests), and we show that epsilon-randomness for epsilon epsilon (0, 1) is different (and more difficult to study) than the classical 1-randomness. (c) 2005 Elsevier B.V. All rights reserved.

关键词： program-size complexity Hausdorff dimension Martingales (partial) randomness

来源：评论

学校读者我要写书评

暂无评论

The halting probability omega: Irreducible complexity in pure mathematics

引用

MILAN JOURNAL OF MATHEMATICS 2007年第1期75卷 291-304页

作者： Chaitin, Gregory IBM Corp Thomas J Watson Res Ctr Yorktown Hts NY 10598 USA

Some Godel centenary reflections on whether incompleteness is really serious, and whether mathematics should be done somewhat differently, based on using algorithmic complexity measured in bits of information.

关键词： incompleteness uncomputability algorithmic randomness program-size complexity algorithmic complexity irreducible complexity halting problem halting probability oracle for halting problem metamathematics quasi-empirical mathematics experimental mathematics algorithmic information theory

来源：评论

学校读者我要写书评

暂无评论

Computable approximations of reals: an information-theoretic analysis

引用

Fundamenta Informaticae 1998年第2期33卷 105-120页

作者： Calude, Cristian S. Hertling, Peter H. Department of Computer Science University of Auckland Private Bag 92019 Auckland New Zealand. {cristianhertling}@cs.auckland.ac.nz

How fast can one approximate a real by a computable sequence of rationals? Rather surprisingly, we show that the answer to this question depends very much on the information content in the finite prefixes of the binary expansion of the real. Computable reals, whose binary expansions have a very low information content, can be approximated (very fast) with a computable convergence rate. Random reals, whose binary expansions contain very much information in their prefixes, can be approximated only very slowly by computable sequences of rationals (this is the case, for example, for Chaitin's Ω numbers) if they can be computably approximated at all. We also show that one can computably approximate any computable real very slowly, with a convergence rate slower than any computable function. However, there is still a large gap between computable reals and random reals: any computable sequence of rationals which converges (monotonically) to a random real converges slower than any computable sequence of rationals which converges (monotonically) to a computable real.

关键词： Computable reals random reals approximations program-size complexity information content

来源：评论

学校读者我要写书评

暂无评论

CHAITIN complexity,SHANNON INFORMATION CONTENT OF A SINGLE EVENT AND INFINITE RANDOM SEQUENCES(Ⅰ)

引用

Science China Mathematics 1991年第11期34卷 1183-1193页

作者：杨恩辉沈世镒 Department of Mathematics Nankai University Tianjin 300071 PRC

Based on program-size complexity, a logical basis for information theory and probabilitytheory has been proposed by A. N. Kolmogorov. The aim of this paper is to furtherstrengthen this logical basis and make it more ... 详细信息

<正> Based on program-size complexity, a logical basis for information theory and probabilitytheory has been proposed by A. N. Kolmogorov. The aim of this paper is to furtherstrengthen this logical basis and make it more perfect. First, for the general case of com-putable probability distributions. sufficient and necessary conditions are given for an infinitesequence x∈A~∞ to be a Martin-lof (M. L.) infinite random sequence of a computable proba-bility distribution. These sufficient and necessary conditions give a complexity-baseddefinition of an infinite random sequence which is equivalent to P. Martin-lof’s statisticaldefinition of the concept of randomness. Consequently, a common complexity-based theoryof finite and infinite random sequences is established. Finally, inequalities between Chaitincomplexity and Shannon information content of a single event are given, and asymptoticallyequivalent relationships between them are also presented.

关键词： program-size complexity Chaitin complexity sequential tests the law of iterated logarithm.

来源：评论

学校读者我要写书评

暂无评论

Chaitin Ω Numbers and Halting Problems

Chaitin Ω Numbers and Halting Problems

引用

5th Conference on Computability in Europe (CiE 2009)

作者： Tadaki, Kohtaro Chuo Univ Res & Dev Initiat JST CRESTBunkyo Ku Tokyo 1128551 Japan

ISBN: (纸本)9783642030727

Chaitin [G. J. Chaitin, J. Assoc. Comput. Mach.;vol. 22, pp. 329-340, 1975] introduced his Omega number as a concrete example of random real. The real Omega is defined as the probability that an optimal computer halts, where the optimal computer is a universal decoding algorithm used to define the notion of program-size complexity. Chaitin showed Omega to be random by discovering the property that the first n bits of the base-two expansion of Omega solve the halting problem of the optimal computer for all binary inputs of length at most n. In the present paper we investigate this property from various aspects. It is known that the base-two expansion of Omega and the halting problem are Turing equivalent. We consider elaborations of both the Turing reductions which constitute the Turing equivalence. These elaborations can be seen as a variant of the weak truth-table reduction, where a computable bound on the use function is explicitly specified. We thus consider the relative computational power between the base-two expansion of Omega and the halting problem by imposing the restriction to finite size oil both the problems.

关键词： algorithmic information theory Chaitin Omega number halting problem Turing reduction algorithmic randomness program-size complexity

来源：评论

学校读者我要写书评

暂无评论

Partial Randomness and Dimension of Recursively Enumerable Reals

引用

34th International Symposium on Mathematical Foundations of Computer Science

作者： Tadaki, Kohtaro Chuo Univ Res & Dev Initiat JST CRESTBunkyo Ku Tokyo 1128551 Japan

ISBN: (纸本)9783642038150

A real alpha is called recursively enumerable ("r.e." for short) if there exists a computable, increasing sequence of rationals which converges to alpha. It is known that the randomness of an r.e. real alpha can be characterized in various ways using each of the notions;program-size complexity, Martin-Lof test, Chaitin Omega number, the domination and Omega-likeness of alpha, the universality of a computable, increasing sequence of rationals which converges to alpha, and universal probability. In this paper, we generalize these characterizations of randomness over the notion of partial randomness by parameterizing each of the notions above by a real T is an element of (0, 1] where the notion of partial randomness is a stronger representation of the Compression rate by means, of program-size complexity. As it result, we present tell equivalent Characterizations of the partial randomness of all r.e. real. The resultant characterizations of partial randomness are powerful and have many important applications. One of them is to present equivalent characterizations of the dimension of an individual r.e. The equivalence between the notion of Hausdorff dimension and compression rate by program-size complexity (or partial randomness) has been established at present by a series of works of many researchers over the last two decades. We present ten equivalent, characterizations of the dimension of an individual r.e. real.

关键词： algorithmic randomness recursively enumerable real partial randomness dimension Chaitin Omega number program-size complexity universal probability

来源：评论

学校读者我要写书评

暂无评论

A New Representation of Chaitin Ω Number Based on Compressible Strings

A New Representation of Chaitin Ω Number Based on Compressi...

引用

9th International Conference on Unconventional Computation

作者： Tadaki, Kohtaro Chuo Univ JST CREST Res & Dev Initiat Bunkyo Ku Tokyo 1128551 Japan

ISBN: (纸本)9783642135224

In 1975 Chaitin introduced his Omega number as a concrete example of random real. The real Omega is defined based on the set of all halting inputs for an optimal prefix-free machine U, which is a universal decoding algorithm used to define the notion of program-size complexity. Chaitin showed Omega to be random by discovering the property that the first n bits of the base-two expansion of Omega solve the halting problem of U for all binary inputs of length at most n. In tins paper, we introduce a new representation Theta of Chaitin Omega number. The real Theta is defined based on the set of all compressible strings. We investigate the properties of Theta and show that Theta is random. In addition, we generalize Theta to two directions Theta(T) and (Theta) over bar (T) with a real T > 0. We then study their properties. In particular, we show that the computability of the real Theta(T) gives a sufficient condition for a real T is an element of (0, 1) to be a fixed point on partial randomness, i.e., to satisfy the condition that the compression rate of T equals to T.

关键词： algorithmic information theory Chaitin Omega number randomness partial randomness fixed point program-size complexity

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：