The standard Tile Assembly Model (TAM) of Winfree (Algorithmic self-assembly of DNA, Ph.D. thesis, 1998) is a mathematical theory of crystal aggregations via monomer additions with applications to the emerging science...
详细信息
The standard Tile Assembly Model (TAM) of Winfree (Algorithmic self-assembly of DNA, Ph.D. thesis, 1998) is a mathematical theory of crystal aggregations via monomer additions with applications to the emerging science of DNA self-assembly. Self-assembly under the rules of this model is programmable and can perform Turing universal computation. Many variations of this model have been proposed and the canonical problem of assembling squares has been studied extensively. We consider the problem of building approximate squares in TAM. Given any we show how to construct squares whose sides are within (1 +/-epsilon)N of any given positive integer N using tile types. We prove a matching lower bound by showing that tile types are necessary almost always to build squares of required approximate dimensions. In comparison, the optimal construction for a square of side exactly N in TAM uses tile types. The question of constructing approximate squares has been recently studied in a modified tile assembly model involving concentration programming. All our results are trivially translated into the concentration programming model by assuming arbitrary (non-zero) concentrations for our tile types. Indeed, the non-zero concentrations could be chosen by an adversary and our results would still hold. Our construction can get highly accurate squares using very few tile types and are feasible starting from values of N that are orders of magnitude smaller than the best comparable constructions previously suggested. At an accuracy of epsilon=0.01, the number of tile types used to achieve a square of size 10(7) is just 58 and our constructions are proven to work for all Na parts per thousand yen13130. If the concentrations of the tile types are carefully chosen, we prove that our construction assembles an LxL square in optimal assembly time O(L) where (1-epsilon)Na parts per thousand currency signLa parts per thousand currency sign(1+epsilon)N.
The statistical mechanical interpretation of algorithmic information theory (AIT, for short) was introduced and developed in our former work [K. Tadaki, Local Proceedings of CiE 2008, pp. 425-434, 2008], where we intr...
详细信息
ISBN:
(纸本)9781457704376
The statistical mechanical interpretation of algorithmic information theory (AIT, for short) was introduced and developed in our former work [K. Tadaki, Local Proceedings of CiE 2008, pp. 425-434, 2008], where we introduced the thermodynamic quantities into AIT. In this paper, we reveal a certain sort of the robustness of statistical mechanical interpretation of AIT. The thermodynamic quantities in AIT are originally defined based on the set of all programs, i.e., all halting inputs, for an optimal prefix-free machine, which is a universal decoding algorithm used to define the notion of program-sizecomplexity. We show that we can recover the original properties of the thermodynamic quantities in AIT if we replace all programs by all minimal-sizeprograms in the definitions of the thermodynamic quantities in AIT. The results of this paper illustrate the generality and validity of the statistical mechanical interpretation of AIT.
The optimal prefix-free machine U is a universal decoding algorithm used to define the notion of program-sizecomplexity H(s) for a finite binary string s. Since the set of all halting inputs for U is chosen to form a...
详细信息
ISBN:
(纸本)9781424482641
The optimal prefix-free machine U is a universal decoding algorithm used to define the notion of program-sizecomplexity H(s) for a finite binary string s. Since the set of all halting inputs for U is chosen to form a prefix-free set, the optimal prefix-free machine can be regarded as an instantaneous code for noiseless source coding scheme. In this paper, we investigate the properties of optimal prefix-free machines as instantaneous codes. In particular, we investigate the properties of the set U-1 (s) of codewords associated with a symbol s. Namely, we investigate the number of codewords in U-1 (s) and the distribution of codewords in U-1 (s) for each symbol s, using the toolkit of algorithmic information theory.
We define a program size complexity function H∞ as a variant of the prefix-free Kolmogorov complexity, based on Turing monotone machines performing possibly unending computations. We consider definitions of randomnes...
详细信息
We consider the notion of algorithmic randomness relative to an oracle. We prove that the probability beta that a program for infinite computations (a program that never halts) outputs a cofinite set is random in the ...
详细信息
We consider the notion of algorithmic randomness relative to an oracle. We prove that the probability beta that a program for infinite computations (a program that never halts) outputs a cofinite set is random in the second jump of the halting problem. Indeed, we prove that beta is exactly as random as the halting probability of a universal machine equipped with an oracle for the second jump of the halting problem, in spite of the fact that beta is defined without considering oracles.
暂无评论