Dimension, in mathematics, is a particular way of describing the size of an object (contrasting with measure and other, different, notions of size).
Hausdorff dimension generalizes the well-known integer dimensions assigned to points, lines, planes, etc.
For example, fractal subsets of the plane may have intermediate dimension between 1 and 2, as they are "larger" than lines or curves, and yet "smaller" than filled circles or rectangles.
Effective dimension modifies Hausdorff dimension by requiring that objects with small effective dimension be not only small but also locatable (or partially locatable) in a computable sense.
An example is an algorithmically random point on a line, which has Hausdorff dimension 0 (since it is a point) but effective dimension 1 (because, roughly speaking, it can't be effectively localized any better than a small interval, which has Hausdorff dimension 1).
This article will define effective dimension for subsets of Cantor space 2ω; closely related definitions exist for subsets of Euclidean space Rn.
We will move freely between considering a set X of natural numbers, the infinite sequence
given by the characteristic function of X, and the real number with binary expansion 0.X.
A martingale on Cantor space 2ω is a function d: 2ω → R≥ 0 from Cantor space to nonnegative reals which satisfies the fairness condition: A martingale is thought of as a betting strategy, and the function
gives the capital of the better after seeing a sequence σ of 0s and 1s.
The fairness condition then says that the capital after a sequence σ is the average of the capital after seeing σ0 and σ1; in other words the martingale gives a betting scheme for a bookie with 2:1 odds offered on either of two "equally likely" options, hence the name fair.
(Note that this is subtly different from the probability theory notion of martingale.
A supermartingale on Cantor space is a function d as above which satisfies a modified fairness condition: A supermartingale is a betting strategy where the expected capital after a bet is no more than the capital before a bet, in contrast to a martingale where the two are always equal.
This allows more flexibility, and is very similar in the non-effective case, since whenever a supermartingale d is given, there is a modified function d' which wins at least as much money as d and which is actually a martingale.
However it is useful to allow the additional flexibility once one starts talking about actually giving algorithms to determine the betting strategy, as some algorithms lend themselves more naturally to producing supermartingales than martingales.
An s-supergale is a function d as above of the form for e some supermartingale.
An s-(super)gale is a betting strategy where some amount of capital is lost to inflation at each step.
A gale d succeeds on a subset X of the natural numbers if
denotes the n-digit string consisting of the first n digits of X.
After all, if one knows a sequence of coin flips in advance, it is easy to make money by simply betting on the known outcomes of each flip.
A standard way of doing this is to require the gales to be either computable or close to computable: A gale d is called constructive, c.e., or lower semi-computable if the numbers
reals (i.e. can uniformly be written as the limit of an increasing computable sequence of rationals).
The effective Hausdorff dimension of a set of natural numbers X is
[3] Kolmogorov complexity can be thought of as a lower bound on the algorithmic compressibility of a finite sequence (of characters or binary digits).
It assigns to each such sequence w a natural number K(w) that, intuitively, measures the minimum length of a computer program (written in some fixed programming language) that takes no input and will output w when run.
The effective Hausdorff dimension of a set of natural numbers X is
Every random sequence will have effective Hausdorff and packing dimensions equal to 1, although there are also nonrandom sequences with effective Hausdorff and packing dimensions of 1.
[3] Thus the effective Hausdorff and packing dimensions of a set
are simply the classical Hausdorff and packing dimensions of
Define the following: A consequence of the above is that these all have Hausdorff dimension