Strict process machine complexity (Q403400): Difference between revisions

In the paper under review, a notion called \(M\)-description for a strict process machine \(M\) is introduced. Based on this notion, the author also introduces \(M\)-complexity. The major result states that the complexity of a sequence or a subset of a Cantor space is equal to its effective Hausdorff dimension.

0 references

reviewed by

Liang Yu

0 references

zbMATH Keywords

computability

0 references

algorithmic randomness

0 references

process complexity

0 references

MaRDI profile type

MaRDI publication profile

0 references

full work available at URL

https://doi.org/10.1007/s00153-014-0378-7

0 references

cites work

Q5414578

0 references

A unified approach to the definition of random sequences

0 references

Q3214803

0 references

Q3069455

0 references

Some theorems on the algorithmic approach to probability theory and information theory (1971 dissertation directed by A. N. Kolmogorov)

0 references

Q2754206

0 references

Dimension in Complexity Classes

0 references

The dimensions of individual strings and sequences

0 references

The definition of random sequences

0 references

A Kolmogorov complexity characterization of constructive Hausdorff dimension.

0 references

Q3611832

0 references

Process complexity and effective random tests

0 references

A formal theory of inductive inference. Part II

0 references

A generalization of Chaitin's halting probability \(\Omega\) and halting self-similar sets

0 references

Q5773778

0 references

THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS

0 references

Identifiers

zbMATH Open document ID

1304.68087

0 references

DOI

10.1007/s00153-014-0378-7

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:403400

@@ Property / cites work @@
+Q5414578
@@ Property / cites work: Q5414578 / rank @@
+Normal rank
@@ Property / cites work @@
+A unified approach to the definition of random sequences
+Normal rank
@@ Property / cites work @@
+Q3214803
@@ Property / cites work: Q3214803 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3069455
@@ Property / cites work: Q3069455 / rank @@
+Normal rank
@@ Property / cites work @@
+Some theorems on the algorithmic approach to probability theory and information theory (1971 dissertation directed by A. N. Kolmogorov)
+Normal rank
@@ Property / cites work @@
+Q2754206
@@ Property / cites work: Q2754206 / rank @@
+Normal rank
@@ Property / cites work @@
+Dimension in Complexity Classes
@@ Property / cites work: Dimension in Complexity Classes / rank @@
+Normal rank
@@ Property / cites work @@
+The dimensions of individual strings and sequences
+Normal rank
@@ Property / cites work @@
+The definition of random sequences
@@ Property / cites work: The definition of random sequences / rank @@
+Normal rank
@@ Property / cites work @@
+A Kolmogorov complexity characterization of constructive Hausdorff dimension.
+Normal rank
@@ Property / cites work @@
+Q3611832
@@ Property / cites work: Q3611832 / rank @@
+Normal rank
@@ Property / cites work @@
+Process complexity and effective random tests
@@ Property / cites work: Process complexity and effective random tests / rank @@
+Normal rank
@@ Property / cites work @@
+A formal theory of inductive inference. Part II
@@ Property / cites work: A formal theory of inductive inference. Part II / rank @@
+Normal rank
@@ Property / cites work @@
+A generalization of Chaitin's halting probability \(\Omega\) and halting self-similar sets
+Normal rank
@@ Property / cites work @@
+Q5773778
@@ Property / cites work: Q5773778 / rank @@
+Normal rank
@@ Property / cites work @@
+THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
+Normal rank