Strict process machine complexity

Archive for Mathematical Logic 53 (5-6):525-538 (2014)
  Copy   BIBTEX

Abstract

We introduce a notion of description for infinite sequences and their sets, and a corresponding notion of complexity. We show that for strict process machines, complexity of a sequence or of a subset of Cantor space is equal to its effective Hausdorff dimension.

Categories

Keywords

Reprint years

DOI

10.1007/s00153-014-0378-7

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 93,932

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

Kolmogorov complexity for possibly infinite computations.Verónica Becher & Santiago Figueira - 2005 - Journal of Logic, Language and Information 14 (2):133-148.
Generalisation of disjunctive sequences.Cristian S. Calude - 2005 - Mathematical Logic Quarterly 51 (2):120.
On the computational power of random strings.Adam R. Day - 2009 - Annals of Pure and Applied Logic 160 (2):214-228.
Being low along a sequence and elsewhere.Wolfgang Merkle & Liang Yu - 2019 - Journal of Symbolic Logic 84 (2):497-516.
Effective fractal dimensions.Jack H. Lutz - 2005 - Mathematical Logic Quarterly 51 (1):62-72.
Lowness for effective Hausdorff dimension.Steffen Lempp, Joseph S. Miller, Keng Meng Ng, Daniel D. Turetsky & Rebecca Weber - 2014 - Journal of Mathematical Logic 14 (2):1450011.
Complexity of the -query Tautologies in the Presence of a Generic Oracle.Toshio Suzuki - 2000 - Notre Dame Journal of Formal Logic 41 (2):142-151.
Program Size Complexity for Possibly Infinite Computations.Verónica Becher, Santiago Figueira, André Nies & Silvana Picchi - 2005 - Notre Dame Journal of Formal Logic 46 (1):51-64.
Completeness, Compactness, Effective Dimensions.Stephen Binns - 2013 - Mathematical Logic Quarterly 59 (3):206-218.
Relative Kolmogorov complexity and geometry.Stephen Binns - 2011 - Journal of Symbolic Logic 76 (4):1211-1239.

Analytics

Added to PP
2014-03-25

Downloads
17 (#865,345)

6 months
4 (#1,005,098)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

On the Concept of a Random Sequence.Alonzo Church - 1940 - Bulletin of the American Mathematical Society 46 (2):130--135.

Add more references