Strict process machine complexity

DOI10.1007/S00153-014-0378-7MaRDI QIDQ403400zbMATH OpenOpenAlexFDO

Authors Ferit Toska

Publication date 29 August 2014

Published in Archive for Mathematical Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00153-014-0378-7

zbMATH Keywords

algorithmic randomnesscomputabilityprocess complexity

Mathematics Subject Classification ID

Algorithmic randomness and dimension (03D32) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Review text

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.

Recommendations

• On process complexity
• On minimal-program complexity measures
• Kolmogorov-Complexity Based on Infinite Computations
• Descriptive complexity of computable sequences
• scientific article; zbMATH DE number 1304316

Cites work

• A formal theory of inductive inference. Part II
• A generalization of Chaitin's halting probability \(\Omega\) and halting self-similar sets
• A Kolmogorov complexity characterization of constructive Hausdorff dimension.
• A unified approach to the definition of random sequences
• Computability and randomness
• Dimension in Complexity Classes
• scientific article; zbMATH DE number 1670880 (Why is no real title available?)
• scientific article; zbMATH DE number 5841426 (Why is no real title available?)
• scientific article; zbMATH DE number 3427210 (Why is no real title available?)
• scientific article; zbMATH DE number 3034029 (Why is no real title available?)
• On process complexity
• Process complexity and effective random tests
• Some theorems on the algorithmic approach to probability theory and information theory (1971 dissertation directed by A. N. Kolmogorov)
• THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
• The definition of random sequences
• The dimensions of individual strings and sequences

Cited in

(3)

• Effective complexity of stationary process realizations
• On process complexity
• Randomness extraction in computability theory

This page was built for publication: Strict process machine complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q403400)