bigpage.tex
\oddsidemargin  0.0in
\evensidemargin 0.0in
\textwidth      6.5in
\headheight     0.0in
\topmargin      0.0in
\textheight 	9.0in


commands.tex
\usepackage{amsfonts}
\usepackage{amsmath} 
\usepackage{amssymb}
\usepackage{enumerate}

% Decision Problems 
\newcommand{\SAT}{\mathrm{SAT}}
\newcommand{\MAXSAT}{\mathrm{MAXSAT}}
\newcommand{\MAXTSAT}{\mathrm{MAX3SAT}}

% Proof Commands
\newcommand{\PROOF}{\begin{proof}}%{{\noindent\bf{\em Proof:\/}~~}}
\newcommand{\PROOFSKETCH}{{\noindent\bf{\em Proof sketch:\/}~~}}
\newcommand{\QED}{\end{proof}}
\newcommand{\QEDbox}{\nolinebreak{\hfill $\square$}\vspace*{0.3cm}}

% Miscellaneous
\newcommand{\Prob}{\mathrm{Prob}}
\newcommand{\floor}[1]{ \left\lfloor #1 \right\rfloor }
\newcommand{\ceil}[1]{ \left\lceil #1 \right\rceil }
\newcommand{\range}{\mathrm{range}}
\newcommand{\myset}[2]{ \left\{ #1 \left| #2 \right. \right\} }
\newcommand{\mysetl}[2]{ \left\{\left. #1 \right| #2 \right\} }
\newcommand{\bval}[1]{[\![ #1 ]\!]}
\newcommand{\prefix}{\sqsubseteq}
\newcommand{\prprefix}{\underset{\neq}{\sqsubset}}
\newcommand{\st}{{\rm st}}
\newcommand{\diam}{\mathrm{diam}}
\newcommand{\doublespace}{\renewcommand{\baselinestretch}{2}\normalsize}

% Blackboard Bold Sets
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}

% Measure and Dimension
\newcommand{\poly}{{\mathrm{poly}}}
\newcommand{\rec}{{\mathrm{rec}}}
\newcommand{\comp}{{\mathrm{comp}}}
\newcommand{\mup}{\mu_{\mathrm{p}}}
\newcommand{\dimp}{\mathrm{dim}_\mathrm{p}}
\newcommand{\dimpspace}{\mathrm{dim}_\mathrm{pspace}}
\newcommand{\dimh}{\mathrm{dim}_\mathrm{H}}
\newcommand{\dimrec}{\mathrm{dim}_\mathrm{rec}}
\newcommand{\dimcomp}{\mathrm{dim}_\comp}
\newcommand{\cdim}{\mathrm{cdim}}
\newcommand{\Gconstr}{\mathcal{G}_\mathrm{constr}}
\newcommand{\C}{\mathbf{C}}
\newcommand{\p}{\mathrm{p}}

% Prediction
\newcommand{\pred}{\mathrm{pred}}
\newcommand{\unpred}{\mathrm{unpred}}
\newcommand{\predp}{\pred_\mathrm{p}}
\newcommand{\predcomp}{\pred_\comp}

% Complexity Classes
\newcommand{\co}{\mathrm{co}}
\newcommand{\strings}{\{0,1\}^*}
\newcommand{\RAND}{\mathrm{RAND}}
\newcommand{\DIM}{\mathrm{DIM}}
\newcommand{\REC}{\mathrm{REC}}
\newcommand{\RE}{\mathrm{RE}}
\newcommand{\SPARSE}{\mathrm{SPARSE}}
\newcommand{\DENSE}{\mathrm{DENSE}}
\newcommand{\DENSEio}{\mathrm{DENSE}_\mathrm{i.o.}}
\newcommand{\DTIME}{\mathrm{DTIME}}
\newcommand{\DTIMEF}{\mathrm{DTIMEF}}
\newcommand{\NP}{\mathrm{NP}}
\newcommand{\coNP}{\co-\NP}
\newcommand{\DeltaPTwo}{\Delta^{\mathrm{P}}_2}
\newcommand{\DP}{\mathrm{DP}}
\newcommand{\SUBEXP}{\mathrm{SUBEXP}}
\newcommand{\SIZE}{{\rm SIZE}}
\newcommand{\BPP}{{\rm BPP}}
\newcommand{\E}{{\rm E}}
\newcommand{\EE}{{\rm EE}}
\newcommand{\ESPACE}{{\rm ESPACE}}
\newcommand{\PSPACE}{{\rm PSPACE}}
\newcommand{\pspace}{{\mathrm{pspace}}}
\newcommand{\Etwo}{{\rm E_2}}
\newcommand{\EXP}{{\rm EXP}}
\newcommand{\DSPACE}{{\rm DSPACE}}
\newcommand{\NE}{{\rm NE}}
\newcommand{\NEE}{{\rm NEE}}
\newcommand{\Poly}{{\rm P}}
\newcommand{\Pc}{{\rm P}}
\newcommand{\PPoly}{{\rm {P/Poly}}}
\newcommand{\Psel}{{\rm {P-sel}}}
\newcommand{\WS}{{\rm WS}}

% Calligraphy
\newcommand{\calC}{{\cal C}}
\newcommand{\calD}{{\cal D}}
\newcommand{\calH}{{\cal H}}

% Kolmogorov Complexity
\newcommand{\calKS}{{\cal KS}}
\newcommand{\calKT}{{\cal KT}}
\newcommand{\calK}{{\cal K}}
\newcommand{\calCD}{{\cal CD}}
\newcommand{\calCND}{{\cal CND}}
\newcommand{\K}{{\mathrm{K}}}
\newcommand{\KS}{{\mathrm{KS}} }
\newcommand{\KT}{{\mathrm{KT}} }
\newcommand{\CD}{{\mathrm{CD}} }
\newcommand{\CND}{{\mathrm{CND}} }

% Reductions
\newcommand{\leqmp}{\leq_{\mathrm{m}}^{\mathrm{P}}}
\newcommand{\leqonettp}{\leq_{1-\mathrm{tt}}^{\mathrm{P}}}
\newcommand{\murec}[1]{{\mu({#1}\mid \REC)}}
\newcommand{\muex}[1]{{\mu({#1}\mid \Etwo)}}
\newcommand{\redu}[2]{{\leq^{\rm {{#1}}}_{{\rm{#2}}}}}
\newcommand{\predu}[1]{{\redu{P}{#1}}}
\newcommand{\pmred}{{\predu{m}}}
\newcommand{\ptred}{{\predu{T}}}
% Reduction Closures
\newcommand{\Pm}{\mathrm{P}_{\mathrm{m}}}
\newcommand{\Ponett}{\mathrm{P}_{1-\mathrm{tt}}}

numbering.tex
\usepackage{amsthm}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\newenvironment{theorem_cite}[1]
{\begin{theorem}  {\rm (#1)}}
{\end{theorem}}
\newenvironment{lemma_cite}[1]
{\begin{lemma}  {\rm (#1)}}
{\end{lemma}}
\newenvironment{corollary_cite}[1]
{\begin{corollary}  {\rm (#1)}}
{\end{corollary}}

\newenvironment{theorem_named}[1]
{\begin{theorem} {\rm (#1)}}
{\end{theorem}}
\newenvironment{lemma_named}[1]
{\begin{lemma} {\rm (#1)}}
{\end{lemma}}

\newtheorem{observation}[theorem]{Observation}
\newtheorem{observations}[theorem]{Observations}

\newtheorem{fact}[theorem]{Fact}
\newtheorem{facts}[theorem]{Facts}

\newtheorem{problem}[theorem]{Problem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\theoremstyle{definition}

\newtheorem*{definition}{Definition}
\newtheorem*{definitions}{Definitions}

\newtheorem{example}[theorem]{Example}
\newtheorem{examples}[theorem]{Examples}
\newtheorem*{example*}{Example}
\newtheorem*{examples*}{Examples}

\newtheorem{construction}[theorem]{Construction}

\newtheorem*{remarks}{Remarks}

\newtheorem*{notation}{Notation}
\newtheorem*{terminology}{Terminology}

\newtheorem*{ack}{Acknowledgment}
\newtheorem*{acks}{Acknowledgments}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\theoremstyle{remark}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\numberwithin{equation}{section}
\numberwithin{figure}{section}

diss.bbl
\begin{thebibliography}{10}

\bibitem{Besi34}
A.~S. Besicovitch.
\newblock On the sum of digits of real numbers represented in the dyadic
  system.
\newblock {\em Mathematische Annalen}, 110:321--330, 1934.

\bibitem{Bill65}
P.~Billingsley.
\newblock {\em Ergodic Theory and Information}.
\newblock John Wiley \& Sons, 1965.

\bibitem{CaiHar94}
J.~Cai and J.~Hartmanis.
\newblock On {H}ausdorff and topological dimensions of the {K}olmogorov
  complexity of the real line.
\newblock {\em Journal of Computer and Systems Sciences}, 49:605--619, 1994.

\bibitem{Chai66}
G.~J. Chaitin.
\newblock On the length of programs for computing finite binary sequences.
\newblock {\em Journal of the Association for Computing Machinery},
  13:547--569, 1966.

\bibitem{Chai69}
G.~J. Chaitin.
\newblock On the length of programs for computing finite binary sequences:
  statistical considerations.
\newblock {\em Journal of the ACM}, 16:145--159, 1969.

\bibitem{Chai75a}
G.~J. Chaitin.
\newblock A theory of program size formally identical to information theory.
\newblock {\em Journal of the Association for Computing Machinery},
  22:329--340, 1975.

\bibitem{Chai87a}
G.~J. Chaitin.
\newblock Incompleteness theorems for random reals.
\newblock {\em Advances in Applied Mathematics}, 8:119--146, 1987.

\bibitem{CovTho91}
T.~M. Cover and J.~A. Thomas.
\newblock {\em Elements of Information Theory}.
\newblock John Wiley \& Sons, Inc., New York, N.Y., 1991.

\bibitem{Eggl49}
H.G. Eggleston.
\newblock The fractional dimension of a set defined by decimal properties.
\newblock {\em Quarterly Journal of Mathematics}, Oxford Series 20:31--36,
  1949.

\bibitem{Falc85}
K.~Falconer.
\newblock {\em The Geometry of Fractal Sets}.
\newblock Cambridge University Press, 1985.

\bibitem{Falc90}
K.~Falconer.
\newblock {\em Fractal Geometry: Mathematical Foundations and Applications}.
\newblock John Wiley \& Sons, 1990.

\bibitem{Good41}
I.~J. Good.
\newblock The fractional dimensional theory of continued fractions.
\newblock {\em Proceedings of the Cambridge Philosophical Society},
  37:199--228, 1941.

\bibitem{Haus19}
F.~Hausdorff.
\newblock Dimension und {\"a}usseres {M}ass.
\newblock {\em Math. Ann.}, 79:157--179, 1919.

\bibitem{Hitchcock:CPED}
J.M. Hitchcock.
\newblock Correspondence principles for effective dimensions.
\newblock Submitted (available at {http://www.cs.iastate.edu/\textasciitilde
  jhitchco}), 2001.

\bibitem{Kaku48}
S.~Kakutani.
\newblock On the equivalence of infinite product measures.
\newblock {\em Annals of Mathematics}, 49:214--224, 1948.

\bibitem{Kolm63}
A.~N. Kolmogorov.
\newblock On tables of random numbers.
\newblock {\em Sankhy\={a}, Series A}, 25:369--376, 1963.

\bibitem{Kolm65}
A.~N. Kolmogorov.
\newblock Three approaches to the quantitative definition of `information'.
\newblock {\em Problems of Information Transmission}, 1:1--7, 1965.

\bibitem{Kolm83}
A.~N. Kolmogorov.
\newblock Combinatorial foundations of information theory and calculus of
  probabilities.
\newblock {\em Russian Mathematical Surveys}, 38:29--40, 1983.

\bibitem{Krei50}
G.~Kreisel.
\newblock Note on arithmetical models for consistent formulae of the predicate
  calculus.
\newblock {\em Fundamenta Mathematicae}, 37:265--285, 1950.

\bibitem{Levi73a}
L.~A. Levin.
\newblock On the notion of a random sequence.
\newblock {\em Soviet Mathematics Doklady}, 14:1413--1416, 1973.

\bibitem{Levi74}
L.~A. Levin.
\newblock Laws of information conservation (nongrowth) and aspects of the
  foundation of probability theory.
\newblock {\em Problems of Information Transmission}, 10:206--210, 1974.

\bibitem{LiVit97}
M.~Li and P.~M.~B. Vit\'{a}nyi.
\newblock {\em An Introduction to Kolmogorov Complexity and its Applications}.
\newblock Springer-Verlag, 1997.

\bibitem{Love66b}
D.~W. Loveland.
\newblock The {K}leene hierarchy classification of recursively random
  sequences.
\newblock {\em Transactions of the American Mathematical Society},
  125:497--510, 1966.

\bibitem{Love66a}
D.~W. Loveland.
\newblock A new interpretation of von {M}ises' concept of a random sequence.
\newblock {\em Zeitschrift f{\"u}r Mathematische Logik und Grundlagen der
  Mathematik}, 12:279--294, 1966.

\bibitem{DCC}
J.~H. Lutz.
\newblock Dimension in complexity classes.
\newblock In {\em Proceedings of the Fifteenth Annual IEEE Conference on
  Computational Complexity}. IEEE Computer Society Press, 2000.

\bibitem{MarL66}
P.~Martin-L{\"o}f.
\newblock The definition of random sequences.
\newblock {\em Information and Control}, 9:602--619, 1966.

\bibitem{MarL71}
P.~Martin-L{\"o}f.
\newblock Complexity oscillations in infinite binary sequences.
\newblock {\em Zeitschrift f{\"u}r Wahrscheinlichkeitstheory und Verwandte
  Gebiete}, 19:225--230, 1971.

\bibitem{Mayo01}
Elvira Mayordomo.
\newblock A {K}olmogorov complexity characterization of constructive
  {H}ausdorff dimension.
\newblock ECCC Technical Report TR01-059, 2001.

\bibitem{Mosc80}
Y.~N. Moschovakis.
\newblock {\em Descriptive Set Theory}.
\newblock North-Holland, Amsterdam, 1980.

\bibitem{Odif89}
P.~Odifreddi.
\newblock {\em Classical Recursion Theory}.
\newblock Elsevier, 1989.

\bibitem{Roge67}
H.~Rog{ers, Jr}.
\newblock {\em Theory of Recursive Functions and Effective Computability}.
\newblock McGraw - Hill, New York, N.Y., 1967.

\bibitem{Ryab84}
B.~Ya. Ryabko.
\newblock Coding of combinatorial sources and {H}ausdorff dimension.
\newblock {\em Soviet Mathematics Doklady}, 30:219--222, 1984.

\bibitem{Ryab86}
B.~Ya. Ryabko.
\newblock Noiseless coding of combinatorial sources.
\newblock {\em Problems of Information Transmission}, 22:170--179, 1986.

\bibitem{Ryab93}
B.~Ya. Ryabko.
\newblock Algorithmic approach to the prediction problem.
\newblock {\em Problems of Information Transmission}, 29:186--193, 1993.

\bibitem{Ryab94}
B.~Ya. Ryabko.
\newblock The complexity and effectiveness of prediction problems.
\newblock {\em Journal of Complexity}, 10:281--295, 1994.

\bibitem{Schn71a}
C.~P. Schnorr.
\newblock A unified approach to the definition of random sequences.
\newblock {\em Mathematical Systems Theory}, 5:246--258, 1971.

\bibitem{Schn71b}
C.~P. Schnorr.
\newblock {Zuf\"alligkeit} und {Wahrscheinlichkeit}.
\newblock {\em Lecture Notes in Mathematics}, 218, 1971.

\bibitem{Schn73}
C.~P. Schnorr.
\newblock Process complexity and effective random tests.
\newblock {\em Journal of Computer and System Sciences}, 7:376--388, 1973.

\bibitem{Schn77}
C.~P. Schnorr.
\newblock A survey of the theory of random sequences.
\newblock In R.~E. Butts and J.~Hintikka, editors, {\em Basic Problems in
  Methodology and Linguistics}, pages 193--210. D. Reidel, 1977.

\bibitem{Shen82}
A.~Kh. Shen$'$.
\newblock The frequency approach to the definition of a random sequence.
\newblock {\em Semiotika i Informatika}, 18:14--42, 1982.
\newblock (In Russian.).

\bibitem{Shen89}
A.~Kh. Shen$'$.
\newblock On relations between different algorithmic definitions of randomness.
\newblock {\em Soviet Mathematics Doklady}, 38:316--319, 1989.

\bibitem{Soar87}
R.~I. Soare.
\newblock {\em Recursively Enumerable Sets and Degrees}.
\newblock Springer-Verlag, Berlin, 1987.

\bibitem{Solo64}
R.~J. Solomonoff.
\newblock A formal theory of inductive inference.
\newblock {\em Information and Control}, 7:1--22, 224--254, 1964.

\bibitem{Solo75}
R.~M. Solovay, 1975.
\newblock reported in \cite{Chai87a}.

\bibitem{Stai98b}
L.~Staiger.
\newblock How much can you win when your adversary is handicapped?
\newblock Available at {http://www.informatik.uni-halle.de/\textasciitilde
  staiger/lust/publikat.html}.

\bibitem{Stai93}
L.~Staiger.
\newblock Kolmogorov complexity and {H}ausdorff dimension.
\newblock {\em Information and Computation}, 102:159--194, 1993.

\bibitem{Stai98}
L.~Staiger.
\newblock A tight upper bound on {K}olmogorov complexity and uniformly optimal
  prediction.
\newblock {\em Theory of Computing Systems}, 31:215--229, 1998.

\bibitem{Terw00}
S.~A. Terwijn.
\newblock Personal communication, 2000.

\bibitem{vanL87a}
M.~van Lambalgen.
\newblock {\em Random Sequences}.
\newblock PhD thesis, Department of Mathematics, University of Amsterdam, 1987.

\bibitem{vanL87b}
M.~van Lambalgen.
\newblock {V}on {M}ises' definition of random sequences reconsidered.
\newblock {\em Journal of Symbolic Logic}, 52:725--755, 1987.

\bibitem{Vovk87}
V.~G. Vovk.
\newblock On a randomness criterion.
\newblock {\em Soviet Mathematics Doklady}, 35:656--660, 1987.

\bibitem{ZvoLev70}
A.~K. Zvonkin and L.~A. Levin.
\newblock The complexity of finite objects and the development of the concepts
  of information and randomness by means of the theory of algorithms.
\newblock {\em Russian Mathematical Surveys}, 25:83--124, 1970.

\end{thebibliography}
