The complexity of linear, fixed-point arithmetic digital controllers is investigated from a Kolmogorov-Chaitin perspective. Based on the idea of Kolmogorov-Chaitin complexity, practical measures of complexity are deve...The complexity of linear, fixed-point arithmetic digital controllers is investigated from a Kolmogorov-Chaitin perspective. Based on the idea of Kolmogorov-Chaitin complexity, practical measures of complexity are developed for statespace realizations, parallel and cascade realizations, and for a newly proposed generalized implicit state-space realization. The complexity of solutions to a restricted complexity controller benchmark problem is investigated using this measure. The results show that from a Kolmogorov-Chaitin viewpoint, higher-order controllers with a shorter word-length may have lower complexity and better performance, than lower-order controllers with longer word-length.展开更多
1 Statement of Limit Theorems Let A={a<sub>1</sub>,…, a<sub>|A|</sub>} be a finite alphabet, B={0, 1}, and N={0, 1,…}. By A<sup>n</sup>（A<sup>∞</sup>, resp.）, we de...1 Statement of Limit Theorems Let A={a<sub>1</sub>,…, a<sub>|A|</sub>} be a finite alphabet, B={0, 1}, and N={0, 1,…}. By A<sup>n</sup>（A<sup>∞</sup>, resp.）, we denote the set of words with the length n（∞, resp.） from the alphabet A; let A<sup>*</sup>= A<sup>n</sup>. B<sup>n</sup>, B<sup>∞</sup> and B<sup>*</sup> are defined similarly. A<sup>n</sup>（A<sup>∞</sup>, resp.） is also considered to be the n-fold （infinite, resp.） Cartesian product of A. If x=（x<sub>i</sub>） is a finite or infinite展开更多
<正> Along the same line of research as in [1], in this paper, we consider the followingthree major problems. The first is to study, from the viewpoint of program-size complexity,the properties possessed by Mart...<正> Along the same line of research as in [1], in this paper, we consider the followingthree major problems. The first is to study, from the viewpoint of program-size complexity,the properties possessed by Martin-lof (M. L.) infinite random sequences. It is found thatM. L. infinite random sequences are normal and satisfy the law of iterated logarithm. Thesecond is to consider the effective generation of M. L. infinite random sequences. It isfound that by using a standard method (e. g., tossing a fair coin) we can choose M. L.infinite random sequences of any computable probability distribution. The last is how todefine the concept of infinite randomness for noncomputable probability distributions. Twotentative definitions are given, and one of them is discussed at length.展开更多
<正> 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 mak...<正> 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.展开更多
文摘The complexity of linear, fixed-point arithmetic digital controllers is investigated from a Kolmogorov-Chaitin perspective. Based on the idea of Kolmogorov-Chaitin complexity, practical measures of complexity are developed for statespace realizations, parallel and cascade realizations, and for a newly proposed generalized implicit state-space realization. The complexity of solutions to a restricted complexity controller benchmark problem is investigated using this measure. The results show that from a Kolmogorov-Chaitin viewpoint, higher-order controllers with a shorter word-length may have lower complexity and better performance, than lower-order controllers with longer word-length.
文摘1 Statement of Limit Theorems Let A={a<sub>1</sub>,…, a<sub>|A|</sub>} be a finite alphabet, B={0, 1}, and N={0, 1,…}. By A<sup>n</sup>（A<sup>∞</sup>, resp.）, we denote the set of words with the length n（∞, resp.） from the alphabet A; let A<sup>*</sup>= A<sup>n</sup>. B<sup>n</sup>, B<sup>∞</sup> and B<sup>*</sup> are defined similarly. A<sup>n</sup>（A<sup>∞</sup>, resp.） is also considered to be the n-fold （infinite, resp.） Cartesian product of A. If x=（x<sub>i</sub>） is a finite or infinite
文摘<正> Along the same line of research as in [1], in this paper, we consider the followingthree major problems. The first is to study, from the viewpoint of program-size complexity,the properties possessed by Martin-lof (M. L.) infinite random sequences. It is found thatM. L. infinite random sequences are normal and satisfy the law of iterated logarithm. Thesecond is to consider the effective generation of M. L. infinite random sequences. It isfound that by using a standard method (e. g., tossing a fair coin) we can choose M. L.infinite random sequences of any computable probability distribution. The last is how todefine the concept of infinite randomness for noncomputable probability distributions. Twotentative definitions are given, and one of them is discussed at length.
文摘<正> 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.
