Abstract
Following Lutz's approach to effective (constructive) dimension, we define a notion of dimension for individual sequences based on Schnorr's concept(s) of randomness. In contrast to computable randomness and Schnorr randomness, the dimension concepts denned via computable martingales and Schnorr tests coincide. Furthermore, we give a machine characterization of Schnorr dimension, based on prefix free machines whose domain has computable measure. Finally, we show that there exist computably enumerable sets which are Schnorr irregular: while every c.e. set has Schnorr Hausdorff dimension 0 there are c.e. sets of Schnorr packing dimension 1, a property impossible in the case of effective (constructive) dimension, due to Barzdin's Theorem.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 96-105 |
| Number of pages | 10 |
| Journal | Lecture Notes in Computer Science |
| Volume | 3526 |
| DOIs | |
| State | Published - Jan 1 2005 |
| Event | First Conference on Computability in Europe, CiE 2005: New Computational Paradigms - Amsterdam, Netherlands Duration: Jun 8 2005 → Jun 12 2005 |
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- General Computer Science