Sophistication vs Logical Depth
Lu\'is Antunes
Bruno Bauwens
Andr\'{e} Souto
Andreia Teixeira
\thanks{This work was partially supported by the national science foundation: Funda\c{c}\~{a}o para a Ci\^{e}ncia e Tecnologia
through the scholarships SFRH/BPD/76231/2011
SFRH/BPD/75129/2010 and SFRH/BD/33234/2007
Sophistication and logical depth are two measures that express how complicated the structure in a string is. Sophistication is defined as the minimal complexity of a computable function that defines a two-part description for the string that is shortest within some precision; the second can be defined as the minimal computation time of a program that is shortest within some precision. We show that the Busy Beaver function of the sophistication of a string exceeds its logical depth with logarithmically bigger precision, and that logical depth exceeds the Busy Beaver function of sophistication with logarithmically bigger precision. We also show that this is not true if the precision is only increased by a constant (when the notions are defined with plain Kolmogorov complexity). Finally we show that sophistication is unstable in its precision: constant variations can change its value by a linear term in the length of the string.
paper_ieee_toit.tex

%% bare_jrnl.tex
%% V1.4
%% 2012/12/27
%% by Michael Shell
%% see http://www.michaelshell.org/
%% for current contact information.
%%
%% This is a skeleton file demonstrating the use of IEEEtran.cls
%% (requires IEEEtran.cls version 1.8 or later) with an IEEE journal paper.
%%
%% Support sites:
%% http://www.michaelshell.org/tex/ieeetran/
%% http://www.ctan.org/tex-archive/macros/latex/contrib/IEEEtran/
%% and
%% http://www.ieee.org/



% *** Authors should verify (and, if needed, correct) their LaTeX system  ***
% *** with the testflow diagnostic prior to trusting their LaTeX platform ***
% *** with production work. IEEE's font choices can trigger bugs that do  ***
% *** not appear when using other class files.                            ***
% The testflow support page is at:
% http://www.michaelshell.org/tex/testflow/


%%*************************************************************************
%% Legal Notice:
%% This code is offered as-is without any warranty either expressed or
%% implied; without even the implied warranty of MERCHANTABILITY or
%% FITNESS FOR A PARTICULAR PURPOSE! 
%% User assumes all risk.
%% In no event shall IEEE or any contributor to this code be liable for
%% any damages or losses, including, but not limited to, incidental,
%% consequential, or any other damages, resulting from the use or misuse
%% of any information contained here.
%%
%% All comments are the opinions of their respective authors and are not
%% necessarily endorsed by the IEEE.
%%
%% This work is distributed under the LaTeX Project Public License (LPPL)
%% ( http://www.latex-project.org/ ) version 1.3, and may be freely used,
%% distributed and modified. A copy of the LPPL, version 1.3, is included
%% in the base LaTeX documentation of all distributions of LaTeX released
%% 2003/12/01 or later.
%% Retain all contribution notices and credits.
%% ** Modified files should be clearly indicated as such, including  **
%% ** renaming them and changing author support contact information. **
%%
%% File list of work: IEEEtran.cls, IEEEtran_HOWTO.pdf, bare_adv.tex,
%%                    bare_conf.tex, bare_jrnl.tex, bare_jrnl_compsoc.tex,
%%                    bare_jrnl_transmag.tex
%%*************************************************************************

% Note that the a4paper option is mainly intended so that authors in
% countries using A4 can easily print to A4 and see how their papers will
% look in print - the typesetting of the document will not typically be
% affected with changes in paper size (but the bottom and side margins will).
% Use the testflow package mentioned above to verify correct handling of
% both paper sizes by the user's LaTeX system.
%
% Also note that the "draftcls" or "draftclsnofoot", not "draft", option
% should be used if it is desired that the figures are to be displayed in
% draft mode.
%
\documentclass[journal]{IEEEtran}
%
% If IEEEtran.cls has not been installed into the LaTeX system files,
% manually specify the path to it like:
% \documentclass[journal]{../sty/IEEEtran}





% Some very useful LaTeX packages include:
% (uncomment the ones you want to load)


% *** MISC UTILITY PACKAGES ***
%
%\usepackage{ifpdf}
% Heiko Oberdiek's ifpdf.sty is very useful if you need conditional
% compilation based on whether the output is pdf or dvi.
% usage:
% \ifpdf
%   % pdf code
% \else
%   % dvi code
% \fi
% The latest version of ifpdf.sty can be obtained from:
% http://www.ctan.org/tex-archive/macros/latex/contrib/oberdiek/
% Also, note that IEEEtran.cls V1.7 and later provides a builtin
% \ifCLASSINFOpdf conditional that works the same way.
% When switching from latex to pdflatex and vice-versa, the compiler may
% have to be run twice to clear warning/error messages.






% *** CITATION PACKAGES ***
%
%\usepackage{cite}
% cite.sty was written by Donald Arseneau
% V1.6 and later of IEEEtran pre-defines the format of the cite.sty package
% \cite{} output to follow that of IEEE. Loading the cite package will
% result in citation numbers being automatically sorted and properly
% "compressed/ranged". e.g., [1], [9], [2], [7], [5], [6] without using
% cite.sty will become [1], [2], [5]--[7], [9] using cite.sty. cite.sty's
% \cite will automatically add leading space, if needed. Use cite.sty's
% noadjust option (cite.sty V3.8 and later) if you want to turn this off
% such as if a citation ever needs to be enclosed in parenthesis.
% cite.sty is already installed on most LaTeX systems. Be sure and use
% version 4.0 (2003-05-27) and later if using hyperref.sty. cite.sty does
% not currently provide for hyperlinked citations.
% The latest version can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/cite/
% The documentation is contained in the cite.sty file itself.






% *** GRAPHICS RELATED PACKAGES ***
%
\ifCLASSINFOpdf
  % \usepackage[pdftex]{graphicx}
  % declare the path(s) where your graphic files are
  % \graphicspath{{../pdf/}{../jpeg/}}
  % and their extensions so you won't have to specify these with
  % every instance of \includegraphics
  % \DeclareGraphicsExtensions{.pdf,.jpeg,.png}
\else
  % or other class option (dvipsone, dvipdf, if not using dvips). graphicx
  % will default to the driver specified in the system graphics.cfg if no
  % driver is specified.
  % \usepackage[dvips]{graphicx}
  % declare the path(s) where your graphic files are
  % \graphicspath{{../eps/}}
  % and their extensions so you won't have to specify these with
  % every instance of \includegraphics
  % \DeclareGraphicsExtensions{.eps}
\fi
% graphicx was written by David Carlisle and Sebastian Rahtz. It is
% required if you want graphics, photos, etc. graphicx.sty is already
% installed on most LaTeX systems. The latest version and documentation
% can be obtained at: 
% http://www.ctan.org/tex-archive/macros/latex/required/graphics/
% Another good source of documentation is "Using Imported Graphics in
% LaTeX2e" by Keith Reckdahl which can be found at:
% http://www.ctan.org/tex-archive/info/epslatex/
%
% latex, and pdflatex in dvi mode, support graphics in encapsulated
% postscript (.eps) format. pdflatex in pdf mode supports graphics
% in .pdf, .jpeg, .png and .mps (metapost) formats. Users should ensure
% that all non-photo figures use a vector format (.eps, .pdf, .mps) and
% not a bitmapped formats (.jpeg, .png). IEEE frowns on bitmapped formats
% which can result in "jaggedy"/blurry rendering of lines and letters as
% well as large increases in file sizes.
%
% You can find documentation about the pdfTeX application at:
% http://www.tug.org/applications/pdftex





% *** MATH PACKAGES ***
%
\usepackage[cmex10]{amsmath}
% A popular package from the American Mathematical Society that provides
% many useful and powerful commands for dealing with mathematics. If using
% it, be sure to load this package with the cmex10 option to ensure that
% only type 1 fonts will utilized at all point sizes. Without this option,
% it is possible that some math symbols, particularly those within
% footnotes, will be rendered in bitmap form which will result in a
% document that can not be IEEE Xplore compliant!
%
% Also, note that the amsmath package sets \interdisplaylinepenalty to 10000
% thus preventing page breaks from occurring within multiline equations. Use:
%\interdisplaylinepenalty=2500
% after loading amsmath to restore such page breaks as IEEEtran.cls normally
% does. amsmath.sty is already installed on most LaTeX systems. The latest
% version and documentation can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/required/amslatex/math/





% *** SPECIALIZED LIST PACKAGES ***
%
%\usepackage{algorithmic}
% algorithmic.sty was written by Peter Williams and Rogerio Brito.
% This package provides an algorithmic environment fo describing algorithms.
% You can use the algorithmic environment in-text or within a figure
% environment to provide for a floating algorithm. Do NOT use the algorithm
% floating environment provided by algorithm.sty (by the same authors) or
% algorithm2e.sty (by Christophe Fiorio) as IEEE does not use dedicated
% algorithm float types and packages that provide these will not provide
% correct IEEE style captions. The latest version and documentation of
% algorithmic.sty can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/algorithms/
% There is also a support site at:
% http://algorithms.berlios.de/index.html
% Also of interest may be the (relatively newer and more customizable)
% algorithmicx.sty package by Szasz Janos:
% http://www.ctan.org/tex-archive/macros/latex/contrib/algorithmicx/




% *** ALIGNMENT PACKAGES ***
%
\usepackage{array}
% Frank Mittelbach's and David Carlisle's array.sty patches and improves
% the standard LaTeX2e array and tabular environments to provide better
% appearance and additional user controls. As the default LaTeX2e table
% generation code is lacking to the point of almost being broken with
% respect to the quality of the end results, all users are strongly
% advised to use an enhanced (at the very least that provided by array.sty)
% set of table tools. array.sty is already installed on most systems. The
% latest version and documentation can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/required/tools/


% IEEEtran contains the IEEEeqnarray family of commands that can be used to
% generate multiline equations as well as matrices, tables, etc., of high
% quality.




% *** SUBFIGURE PACKAGES ***
%\ifCLASSOPTIONcompsoc
%  \usepackage[caption=false,font=normalsize,labelfont=sf,textfont=sf]{subfig}
%\else
%  \usepackage[caption=false,font=footnotesize]{subfig}
%\fi
% subfig.sty, written by Steven Douglas Cochran, is the modern replacement
% for subfigure.sty, the latter of which is no longer maintained and is
% incompatible with some LaTeX packages including fixltx2e. However,
% subfig.sty requires and automatically loads Axel Sommerfeldt's caption.sty
% which will override IEEEtran.cls' handling of captions and this will result
% in non-IEEE style figure/table captions. To prevent this problem, be sure
% and invoke subfig.sty's "caption=false" package option (available since
% subfig.sty version 1.3, 2005/06/28) as this is will preserve IEEEtran.cls
% handling of captions.
% Note that the Computer Society format requires a larger sans serif font
% than the serif footnote size font used in traditional IEEE formatting
% and thus the need to invoke different subfig.sty package options depending
% on whether compsoc mode has been enabled.
%
% The latest version and documentation of subfig.sty can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/subfig/




% *** FLOAT PACKAGES ***
%
%\usepackage{fixltx2e}
% fixltx2e, the successor to the earlier fix2col.sty, was written by
% Frank Mittelbach and David Carlisle. This package corrects a few problems
% in the LaTeX2e kernel, the most notable of which is that in current
% LaTeX2e releases, the ordering of single and double column floats is not
% guaranteed to be preserved. Thus, an unpatched LaTeX2e can allow a
% single column figure to be placed prior to an earlier double column
% figure. The latest version and documentation can be found at:
% http://www.ctan.org/tex-archive/macros/latex/base/


%\usepackage{stfloats}
% stfloats.sty was written by Sigitas Tolusis. This package gives LaTeX2e
% the ability to do double column floats at the bottom of the page as well
% as the top. (e.g., "\begin{figure*}[!b]" is not normally possible in
% LaTeX2e). It also provides a command:
%\fnbelowfloat
% to enable the placement of footnotes below bottom floats (the standard
% LaTeX2e kernel puts them above bottom floats). This is an invasive package
% which rewrites many portions of the LaTeX2e float routines. It may not work
% with other packages that modify the LaTeX2e float routines. The latest
% version and documentation can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/sttools/
% Do not use the stfloats baselinefloat ability as IEEE does not allow
% \baselineskip to stretch. Authors submitting work to the IEEE should note
% that IEEE rarely uses double column equations and that authors should try
% to avoid such use. Do not be tempted to use the cuted.sty or midfloat.sty
% packages (also by Sigitas Tolusis) as IEEE does not format its papers in
% such ways.
% Do not attempt to use stfloats with fixltx2e as they are incompatible.
% Instead, use Morten Hogholm'a dblfloatfix which combines the features
% of both fixltx2e and stfloats:
%
% \usepackage{dblfloatfix}
% The latest version can be found at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/dblfloatfix/




%\ifCLASSOPTIONcaptionsoff
%  \usepackage[nomarkers]{endfloat}
% \let\MYoriglatexcaption\caption
% \renewcommand{\caption}[2][\relax]{\MYoriglatexcaption[#2]{#2}}
%\fi
% endfloat.sty was written by James Darrell McCauley, Jeff Goldberg and 
% Axel Sommerfeldt. This package may be useful when used in conjunction with 
% IEEEtran.cls'  captionsoff option. Some IEEE journals/societies require that
% submissions have lists of figures/tables at the end of the paper and that
% figures/tables without any captions are placed on a page by themselves at
% the end of the document. If needed, the draftcls IEEEtran class option or
% \CLASSINPUTbaselinestretch interface can be used to increase the line
% spacing as well. Be sure and use the nomarkers option of endfloat to
% prevent endfloat from "marking" where the figures would have been placed
% in the text. The two hack lines of code above are a slight modification of
% that suggested by in the endfloat docs (section 8.4.1) to ensure that
% the full captions always appear in the list of figures/tables - even if
% the user used the short optional argument of \caption[]{}.
% IEEE papers do not typically make use of \caption[]'s optional argument,
% so this should not be an issue. A similar trick can be used to disable
% captions of packages such as subfig.sty that lack options to turn off
% the subcaptions:
% For subfig.sty:
% \let\MYorigsubfloat\subfloat
% \renewcommand{\subfloat}[2][\relax]{\MYorigsubfloat[]{#2}}
% However, the above trick will not work if both optional arguments of
% the \subfloat command are used. Furthermore, there needs to be a
% description of each subfigure *somewhere* and endfloat does not add
% subfigure captions to its list of figures. Thus, the best approach is to
% avoid the use of subfigure captions (many IEEE journals avoid them anyway)
% and instead reference/explain all the subfigures within the main caption.
% The latest version of endfloat.sty and its documentation can obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/endfloat/
%
% The IEEEtran \ifCLASSOPTIONcaptionsoff conditional can also be used
% later in the document, say, to conditionally put the References on a 
% page by themselves.




% *** PDF, URL AND HYPERLINK PACKAGES ***
%
%\usepackage{url}
% url.sty was written by Donald Arseneau. It provides better support for
% handling and breaking URLs. url.sty is already installed on most LaTeX
% systems. The latest version and documentation can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/url/
% Basically, \url{my_url_here}.




% *** Do not adjust lengths that control margins, column widths, etc. ***
% *** Do not use packages that alter fonts (such as pslatex).         ***
% There should be no need to do such things with IEEEtran.cls V1.6 and later.
% (Unless specifically asked to do so by the journal or conference you plan
% to submit to, of course. )


%%%%%our stuff%%%%%%

\usepackage{amsfonts,amssymb,bbm,amsthm}

\usepackage{enumerate}
\usepackage{epsf}
\usepackage{multirow}
\usepackage{tikz}
%\usepackage{a4}
%\usepackage{fullpage}
\usepackage[final]{epsfig}
\renewcommand{\thefootnote}{\fnsymbol{footnote}}

\newcounter{unit}
\newtheorem{definition}[unit]{Definition}
\newtheorem{theorem}[unit]{Theorem}
\newtheorem{proposition}[unit]{Proposition}
\newtheorem{pppdef}[unit]{Prop/Definition}
\newtheorem{corollary}[unit]{Corollary}
\newtheorem{pnot}[unit]{Notation}
\newtheorem{pconv}[unit]{Convention}
\newtheorem{algorithm}[unit]{algorithm}
\newtheorem{protocol}[unit]{Protocol}
\newtheorem{claim}[unit]{Claim}
\newtheorem{example}[unit]{Example}
\newtheorem{lemma}[unit]{Lemma}


%%%%%%%%%%%%%% - parties
\def\nn{\mathbb N}
\def\P{\mathcal P}
\def\V{\mathcal V}
\def\R{\mathcal R}
\def\S{\mathcal S}
\def\O{\mathcal O}
\def\E{\mathcal E}

%%%%%%%%%%%%% - problems
\def\iso{\mathbb{ISO}}
\def\GI{\mathbb{GI}}
\def\HAM{\mathbb{HAM}}
\def\qr{\mathbb{QR}}
\def\sat{\mathbb{SAT}}
\def\tsat{3\mathbb{SAT}}
\def\ham{\mathbb{HAM}}
\def\fham{\mathbb{FHAM}}
\def\3col{\mathbb{C}3\mathbb {L}}


%%%%%%%%%%%%% - classes of problems
\def\p{\bf P}
\def\fewp{\bf FewP}
\def\up{\bf UP}
\def\np{\bf NP}
\def\bpp{\bf BPP}
\def\IP{\bf IP}

%%%%%%%%%%%%% - others

\def\C{\{0,1\}}
\def\B{\{0,1\}\as}
\def\as{{}^{\ast}}
\def\ds{\displaystyle}
\def\eps{\varepsilon}
\def\nn{\mathbb N}
\def\non{\nonumber}
\def\imp{\Rightarrow}
\def\eqv{\Leftrightarrow}
%\newcommand{\bpp}{\mbox{\rm BPP}}
\newcommand{\EXP}{\mbox{\rm EXP}}
\newcommand{\deep}{\mbox{\rm DEEP}}
\def\nn{\mathbb N}

\newcommand{\soph}[1]{\mbox{soph}_{#1}}
\newcommand{\seq}[2]{#1_{[1:#2]}}
\newcommand{\ld}[1]{\mbox{depth}_{#1}}
\newcommand{\halttime}{\mbox{time}}

\newcommand{\ovl}[1]{\overline{#1}}

\DeclareMathOperator{\Dom}{Dom}





% correct bad hyphenation here
\hyphenation{}


\begin{document}
%
% paper title
% can use linebreaks \\ within to get better formatting as desired
% Do not put math or special symbols in the title.
\title{Sophistication vs Logical Depth}
%
%
% author names and IEEE memberships
% note positions of commas and nonbreaking spaces ( ~ ) LaTeX will not break
% a structure at a ~ so this keeps an author's name from being broken across
% two lines.
% use \thanks{} to gain access to the first footnote area
% a separate \thanks must be used for each paragraph as LaTeX2e's \thanks
% was not built to handle multiple paragraphs
%


\author{	
					Lu\'is Antunes,
					Bruno Bauwens,
					Andr\'{e} Souto,
					Andreia Teixeira,
					
					
\thanks{This work was partially
supported by the national science foundation: Funda\c{c}\~{a}o para a
Ci\^{e}ncia e Tecnologia, through the scholarships SFRH/BPD/76231/2011,
SFRH/BPD/75129/2010 and SFRH/BD/33234/2007, through the project $CSI^2$
with the reference PTDC/EIA-CCO/099951/2008 and grants of Instituto de
Telecomunica\c{c}\~oes. The second author was also supported by 
NAFIT ANR-08-EMER-008-01 project.}
% <-this % stops a space
\thanks{Lu\'is Antunes is currently working in the Security and Quantum Information group of Instituto de Telecomunica\c{c}\~oes and in the Departamento de Ci\^{e}ncia de Computadores of Faculdade de Ci\^{e}ncias da Universidade do Porto. email:lfa@dcc.fc.up.pt}
\thanks{Bruno Bauwens is currently working at the LORIA department of the Universit\'e de Lorraine. 
Part of the work was done while he was a pos-doc at Security and Quantum Information group of
Instituto de Telecomunica\c{c}\~oes. email:bruno.bauwens@telenet.be}
\thanks{Andr\'e Souto is currently working in the Security and Quantum Information group of Instituto de Telecomunica\c{c}\~oes and in the Departamento de Matem\'atica of Instituto Superior T\'ecnico. His work was also supported by Funda\c{c}\~{a}o para a Ci\^{e}ncia e Tecnologia, through the scholarship SFRH/BPD/76231/2011. email:a.souto@math.ist.utl.pt
}
% <-this % stops a space
%
\thanks{Andreia Teixeira is currently working in the Security and Quantum Information group of Instituto de Telecomunica\c{c}\~oes and in the Departamento de Ci\^encia de Computadores of Faculdade de Ci\^encias da Universidade do Porto.}
%
%
\thanks{Manuscript sent in April, 2013; ...}}

% note the % following the last \IEEEmembership and also \thanks - 
% these prevent an unwanted space from occurring between the last author name
% and the end of the author line. i.e., if you had this:
% 
% \author{....lastname \thanks{...} \thanks{...} }
%                     ^------------^------------^----Do not want these spaces!
%
% a space would be appended to the last name and could cause every name on that
% line to be shifted left slightly. This is one of those "LaTeX things". For
% instance, "\textbf{A} \textbf{B}" will typeset as "A B" not "AB". To get
% "AB" then you have to do: "\textbf{A}\textbf{B}"
% \thanks is no different in this regard, so shield the last } of each \thanks
% that ends a line with a % and do not let a space in before the next \thanks.
% Spaces after \IEEEmembership other than the last one are OK (and needed) as
% you are supposed to have spaces between the names. For what it is worth,
% this is a minor point as most people would not even notice if the said evil
% space somehow managed to creep in.



% The paper headers
\markboth{Submitted to IEEE Transactions of Information Theory}%
{Sophistication vs Logical Depth}
% The only time the second header will appear is for the odd numbered pages
% after the title page when using the twoside option.
% 
% *** Note that you probably will NOT want to include the author's ***
% *** name in the headers of peer review papers.                   ***
% You can use \ifCLASSOPTIONpeerreview for conditional compilation here if
% you desire.




% If you want to put a publisher's ID mark on the page you can do it like
% this:
%\IEEEpubid{0000--0000/00\$00.00~\copyright~2012 IEEE}
% Remember, if you use this you must call \IEEEpubidadjcol in the second
% column for its text to clear the IEEEpubid mark.



% use for special paper notices
%\IEEEspecialpapernotice{(Invited Paper)}




% make the title area


\maketitle

% As a general rule, do not put math, special symbols or citations
% in the abstract or keywords.
\begin{abstract}
  Sophistication and logical depth are two measures that express how complicated the structure in 
  a string is. Sophistication is defined as the minimal complexity of a computable function 
  that defines a two-part description for the string that is shortest within some precision; 
  the second can be defined as the minimal computation time of a program that is shortest 
  within some precision.
  We show that the Busy Beaver function of the sophistication of a string 
  exceeds its logical depth with logarithmically bigger precision, and that logical depth exceeds the
  Busy Beaver function of sophistication with logarithmically bigger precision. 
  We also show that this is not true if the precision is only increased by a constant
  (when the notions are defined with plain Kolmogorov complexity).
  Finally we show that sophistication is unstable in its precision: constant variations 
  can change its value by a linear term in the length of the string.
\end{abstract}

% Note that keywords are not normally used for peerreview papers.
\begin{IEEEkeywords}
Sophistication, logical depth, Kolmogorov complexity, algorithmic sufficient statistics, Busy Beaver function.
\end{IEEEkeywords}
% As a general rule, do not put math, special symbols or citations
% in the abstract or keywords.




\section{Introduction} \label{sec:intro}



Solomonoff~\cite{Sol64}, Kolmogorov~\cite{kol65} and Chaitin~\cite{Cha66} independently defined a
measure of information contained in a bit string~$x$ as the length of a shortest program that
produces~$x$ on a universal Turing machine. This measure, usually represented by~$C(x)$, is called
Kolmogorov complexity.  
Kolmogorov complexity does not express whether the string contains sophisticated structure.
For example, consider for some $n$ a randomly generated $n$-bit string. With high probability 
the complexity is about $n$ and the string has no (complicated) structure. On the other hand, 
the $(2^n-1)$-bitstring representing the Halting problem for programs of length less than $n$ 
has also complexity close to~$n$ but has very complicated structure.
Informally, ``sophistication of structure'' can be measured by the computation time of a program 
modelling the structure or by the minimal size of a program that models the structure.


The first notion is Bennett's \em logical
depth\em~\cite{ben88}. At significance level~$c$, it is defined as the minimal
time to compute $x$ by a program $p$ that is $c$-incompressible on a universal prefix-free Turing
machine (of some type), i.e. $C(p) \ge |p| - c$. Bennett~\cite{ben88} showed that this measure is
closely related to the minimal time for which some time-bounded version of algorithmic probability
 converges within a factor $2^{-c}$. We will use the
following simpler  variant (which is closely related, see further):
\begin{quote} \em 
``the time required to compute $x$ by a program no more than $c$~bits
longer than a shortest program''.
\end{quote}

Examples of strings that are non-deep accordingly to this definition are
the random strings and the (efficiently) computable ones. 
In~\cite{afmv06}, this notion was used to show that if the complexity class $\np$ reduces to a sequence for which every initial segment is not deep, up to ``polylog'' precision in the length of the string, then the polynomial time hierarchy collapses. In particular, it would imply a collapse if $\np$ reduces to a sparse or to a random set.

Koppel~\cite{koppel87} defined a different notion of depth for infinite sequences based on monotone
complexity. 
The class of deep sequences is defined by the ones for which the depth of initial segments is not
bounded by a computable function of their length.  In particular, the set of such sequences is disjoint from the set
of random ones, and hence, they define a set of measure zero. Lutz~\cite{DepthAndReducibility}
showed that deep sequences contain useful information in the following computational sense: the
class of sequences that true-table reduces to them has non-zero measure in the class of computable
sequences.

Kolmogorov~\cite{KolmogorovTallinn,KolmogorovAbstract} defined for each string the notion of
structure function dividing a shortest program for a string in two parts -- one part accounting for
useful regularities and another accounting for the remaining information presented in the string --
in such a way that this two-part description is as small as the shortest one-part description. He
represented the regularities in the string, by finite sets. Later,
Koppel~\cite{koppel87,koppel88,koppel91} expressed regularities as monotone computable functions and
called the minimal complexity of the function defining a shortest two-part code {\it
sophistication}. Following Koppel's work, Li and Vitanyi~\cite[p. 100]{livi} and independently
Antunes and Fortnow~\cite{soph} revisited the notion of sophistication considering computable
functions (that are not necessarily monotone).  
It was observed that there are strings with
near maximum sophistication, and such strings encode the halting problem for smaller
programs (see e.x.~\cite{soph}).
Furthermore, in~\cite{soph} the authors introduced the notion of coarse
sophistication, and showed that it is roughly equivalent to a variation of computational depth based
on the Busy Beaver function. In Section~\ref{sec:overview} we present a more detailed overview of
the literature on these sophistication measures. 

Sophistication and logical depth are conceptually very different since the former measures program
lengths while the latter running times. In order to establish a relationship between these
measures, we rescale logical depth from running time to program length using the Busy Beaver
function. In this scenario, we prove that up to logarithmic changes of the significance of
both measures, they are equal up to logarithmic terms. 
From this, we conclude that all sophistication measures defined using Kolmogorov complexity, 
are equivalent in this sense.
Then we prove that such an equivalence of sophistication and logical depth is not possible up 
to constant changes in significance. 
Finally, we study the stability of sophistication under changes of significance. 
From \cite[Theorem IV.4]{vv04}, one concludes that a logarithmic change of the significance
can change sophistication maximally (i.e. almost $|x|$).
We show this also holds for constant changes of the significance.


The rest of the paper is organized as follows: in the next section we overview several variants of
sophistication.
In Section~\ref{sec:prel}
we introduce some definitions used in the rest of the paper. In Sections~\ref{sec:relacoes}
and~\ref{sec:sophunstable} we present and prove the new results mentioned in the previous paragraph.




\section{Structure function, sophistication and variants}\label{sec:overview}


Kolmogorov~\cite{KolmogorovTallinn,KolmogorovAbstract}, see~\cite{CGG89}, 
raised the question whether there exist a string~$x$ for which no 
finite set of small Kolmogorov complexity\footnote[1]{
  The Kolmogorov complexity of a set is the length of 
  a shortest program that print all its elements and halts.}
exists in which it is a ``typical element''.
He defined $x$ to be $c$-typical in $S \ni x$
iff $\log |S| - C(x|S) \le c$, i.e.,  
a literal representation of the lexicographic index of $x$ in $S$ 
(of length $\log |S| + O(1)$) is almost a shortest description 
for $x$ given $S$. 
Note that by a counting argument, at most a fraction $2^{-c+1}$ 
of elements in the set can be non-typical.\footnote[2]{
  The converse is also true: any set has
  non-typical elements unless the set contains a lot of 
  mutual information with the Halting problem~\cite{EpsteinLevin}.}


In~\cite{Shen83,Vyu87,GTV01} it was shown that absolutely non-stochastic objects exist, i.e.,
some strings are only typical in sets of complexity close to the length of the string.
Such strings have high mutual information with the Halting sequence and with high probability they do not appear in statistical experiments. 

\begin{figure}
  \centering
  \begin{tikzpicture}[scale=0.5]
    \fill[gray!20] (0,6) -- (0,5.5) -- (1,5) -- (1.5,3.5) -- (4,2) -- (4.5,0) -- (5,0) -- (5,6) -- cycle;  
    \draw[<->] (0,6) node[anchor=south] {$\log |S|$} -- (0,0) -- (5,0) node[anchor=west] {$C(S)$} ;
    \draw (0,5.5) node[anchor=east] {$|x|$} 
	-- (1,5) -- (1.5,3.5) -- (4,2) -- (4.5,0);
   \draw[red,thick] (0,2.3) node[anchor=east,black] {$C(x)$} -- (4.7,0) node[anchor=north,black] {$C(x)$};
  \end{tikzpicture}
  \caption{Structure function}
  \label{fig:structureFunction}
\end{figure}

Kolmogorov also considered a more restrictive class of good set-models for a string $x$.
To understand this criterion, consider the  {\em structure set}, which is the set of 
all pairs $(i,j)$ for which there is an $x$-containing set 
of complexity at most $i$ and cardinality at most $2^j$, see Figure~\ref{fig:structureFunction}. 
For $x$ of length $n$, the set contains the points $(0, n)$ and $(C(x),0)$ 
witnessed by the sets $\{x\}$ and the set of all $n$-bit strings (we ignore $O(\log n)$-terms). 
Note that if the set contains $(i,j)$, then it also contains all pairs $(i+k, j-k)$ for $k \le j$.\footnote[3]{
 Partition the set in subsets of size at most $2^{j-k}$, this 
 increases the complexity of the $x$-containing set by at most~$k$.}
Hence the lower border of the set, called structure function, is decreasing (still ignoring $O(\log n)$ terms).
No point appears below the line $i+j = C(x)$, otherwise the corresponding set could be used to construct 
a program for $x$ of size less then $C(x)$.
Cover~\cite{Cover85} (see also~\cite[Sect. 14.12]{CoverElements} and~\cite[Sect 5.5.1]{livi}) 
mentioned explicitly the left-most place where the set approaches this line, 
which we will call  {\em set sophistication} of~$x$: 
 \[
 \soph{c}(x) = \min \{C(S) : x \in S \wedge C(S) + \log |S| \le C(x) + c\}.
 \]
It is not hard to show that if $S$ is $c$-sufficient for $x$ 
(i.e. satisfies the conditions in Definition \ref{AF} of $\soph{c}(x)$), 
then $x$ is $c+O(\log |x|)$-typical in $S$, where $|x|$ denotes the length of $x$. 
In~\cite{vv04} it was shown that if there exist a set $S$ in which $x$ is $c$-typical, then there exists a set of complexity $C(S) + O(\log |x|)$ which is $(c+O(\log |x|))$-sufficient for $x$. 
Hence, if sophistication was defined in terms of $c$-typical sets, 
then we would obtain a function that is $O(\log |x|)$-close; here 
two non-increasing functions $f$ and $g$ are said to be {\em $\varepsilon$-close} for some natural
number $\varepsilon$ if $f(c+\varepsilon) \le g(c) + \varepsilon$ and $g(c+\varepsilon) \le f(c) + \varepsilon$ for all $c$.
From~\cite[Theorem IV.4]{vv04} it follows that every decreasing function $f$ 
is $(C(f)+O(\log |x|))$-close to the structure function of some string of length $f(0)$, 
which implies that every non-increasing function with $f(k)=0$ is close to the sophistication of some string of length $f(0)+k$ and complexity~$k$ (in the interval $[0,k]$).\footnote{ 
  This result is stated in terms of the MDL function $\lambda_x(c)$, 
  and by unfolding the definitions, one can observe that for fixed $x$,
  the inverse of $\lambda_x(c)-C(x)$ equals set sophistication $\soph{c}(x)$.
  }
This also implies that sophistication is unstable, increasing its parameter $c$ by $O(\log |x|)$, the sophistication can drop from its maximal value $|x|-O(\log |x|)$ to $O(\log |x|)$.


In~\cite{GTV01} it is shown that a sufficient set of almost minimal complexity of a string~$x$ can be computed from an initial segment of the binary code of the number of 
halting programs of length~$C(x)$. Hence, such a set contains high mutual information with the Halting problem for short programs.
(See~\cite{ShenAlgorithmicStatistics} for the proofs of this and the above results).
In~\cite{SSS,SSSdifferent} it is concluded that this statistic can hardly be interpreted as a denoised version of~$x$. 
In fact, compared to $x$, a sufficient two part-code $(S,z)$ 
(where $z$ is the lexicographic index of $x$ in $S$) can contain different computational information from $x$, although $C(x|S,z)$ and 
$C(S,z|x)$ are small. The proposed solution is to impose the existence of a 
computable bijection of small complexity between $x$ and $(S,z)$. 
This is equivalent to the requirement that there exist a short total program computing $S$ from $x$.
In~\cite{SSSdifferent} it was shown that this leads to a notion of sophistication 
that is different from set-sophistication.

By varying the model type and the type of Kolmogorov complexity in the notion of 
minimal sufficient sets, many variants of sophistication measures have been introduced.
We say that a function $f$ is $c$-sufficient for $x$ if there is a string $d$ 
such that $f(d) = x$ and $C(f) + |d| \le C(x)+c$.
A computable probability density function $P$ is $c$-sufficient for $x$ if
$C(P) + \log (1/P(x)) \le C(x)+c$~\cite{GTV01}.\footnote{\label{fn:prefixplain}
  This probabilistic sufficiency criterion was defined in~\cite{GTV01} in terms of 
  prefix-free complexity, because $2^{-K(x|P)}$ defines a probability 
  distribution and hence, it is natural to compare it with $P(x)$. 
  Prefix complexity and plain complexity differ
  by at most $O(\log |x|)$~\cite{livi}, and this precision is sufficient for our discussion.}
In an analogue way, probabilistic and function sophistication at 
significance level $c$ are defined as the computable functions and 
probabilistic density functions of minimal complexity that are $c$-sufficient.
In~\cite[Lemmas 7.1 and 7.2]{Vit06} it is proved that set, function, and probabilistic 
sophistication are all $O(\log |x|)$-close. 
In order to generalize the notion of sophistication for (infinite) sequences, 
Koppel~\cite{koppel87,koppel88,koppel91} considered monotone computable functions $f$ as models. The sufficiency criterion for the two-stage code for $x$ is the existence 
of a string $d$ such that $f(d)=x$ and $Km(f) + |d| \le H(x)+c$ where $H(x)$ is the 
minimal length of a such two-part description for $x$ on some special monotone machine and $Km(x)$
denotes the monotone Kolmogorov complexity corresponding to the machine.
It is not hard to show that $H(x) = Km(x) + O(\log |x|)$ and also that this notion of sophistication is $O(\log |x|)$-close to 
the aforementioned notions.\footnote{
 It is unclear whether $H(x) = Km(x) + O(1)$.
 }
On this model, Koppel defined sophistication and depth for sequences in two variants, 
and for each variant he showed that sophistication and depth are equal up to $O(1)$-constants.

%Later Li and Vitanyi~\cite[Sect. 2.1.1,p100]{LiVi97} %and Antunes and Fortnow~\cite{soph} 
%(see also~\cite{soph}  and \cite{Vit06})
%considered a simpler variant of Koppel's notion of sophistication for strings.
%They use computable functions as model and $C(x)$ as complexity measure. 
%A computable function $f$ is $c$-sufficient for $x$ 
%if there exist a string $d$ such that $f(d) = x$ and $C(f) + |d| \le C(x) + c$. 
%%In~\cite{soph} it is shown that strings with near maximum
%%sophistication which can encode the halting problem for smaller strings. 
%%They also defined coarse sophistication, and showed that it is roughly
%%equivalent to a variation of logical depth based on the Busy Beaver function. 
%In~\cite{GTV01} probabilistic sufficient statistics for a string $x$ are introduced,
%which are discrete computable probability density functions such that 
%$C(P) + \log (1/P(x)) \le C(x)+c$. 


A last variant of sophistication is called effective complexity~\cite{GML96,GML04}. 
This notion uses a probability density function $P$. 
Inspired by an information-theoretic solution of the problem of Maxwell's Demon, total entropy of
$P$ has been defined as $C(P) + H(P)$, where $H(P) = \sum_x P(x) \log_2 (1/P(x))$ denotes the Shannon
entropy of $P$.\footnote{The definition of total entropy used in~\cite{GML96,GML04} is $K(P) +
H(P)$. Notice that plain and prefix complexity are sufficiently close ($|K(P) - C(P)| \le O(\log
C(P)$). See also footnote~\ref{fn:prefixplain}.} A probability density function $P$ is a $c$-good
model for $x$ if
$C(P) + H(P) \le C(x)+c$ and $\log (1/P(x)) \le H(P)+c$.\footnote{
  In fact, in~\cite{GML96} the precision 
  for which these inequalities should hold is not discussed. 
  Also, the authors suggest that the computation time of 
  a program for $P$ is bounded by some computable function.
  In~\cite{effCompVsDepth}
  the first requirement $c = \delta|x|$ is chosen for some $\delta>0$ and in the second 
  requirement a different parameter is chosen. 
  Furthermore, $P$ should be computable as a real function 
  and no restrictions on the computation time are considered. 
  Also, $K(P)$ is replaced by $K(P, H(P))$.} 
The $c$-effective complexity is the minimal complexity of a $c$-good model.
In~\cite[Lemma 21]{effCompVsDepth}, it is shown that effective complexity is 
close to set-sophistication. Indeed, 
if $P$ is $c$-good than it is $2c$-sufficient. 
For the other direction, note that at most $1 + H(P)2^{H(P)+c+1}$ elements satisfy 
$\log (1/P(x)) \le \lceil H(P)\rceil + c$,\footnote{
  Let $N$ be the number of strings $x$ such that $P(x) \ge 2^{-H(P)-c}$.
  Remark that for at most $1$ element we have $\log_2(1/P(x)) < 1$.
  Hence $H(P) \ge (N-1) \sum_x P(x) \ge (N-1)2^{-H(P)-c}$.
  }
and these elements can be computed given $P$ and $\lceil H(x) \rceil \le C(x) + c \le |x|+c+O(1)$.
Hence a $c$-good model defines a $(c+O(\log |x|))$-sufficient set.
In~\cite[Theorem 18]{effCompVsDepth} it is also shown that strings with 
high effective complexity have very high computational depth. Moreover, 
the proof shows that effective complexity is upper bounded by the 
inverse Busy Beaver function of logical depth with slightly bigger significance.
Our Theorem~\ref{th:ldepthVsSoph} implies also the other direction,  {\em i.e.} 
that effective complexity is $O(\log |x|)$-close to the inverse Busy Beaver of 
logical depth. 




\section{Preliminaries}\label{sec:prel}

In this work $x,y,p,q$ is used for strings and $n,c$ for natural numbers. 
$|x|$ is the length of $x$. $\log n$ means $\lfloor \log_2 n \rfloor$.
Turing machines are associated to partial functions $U$ that map pairs of strings to strings. 
We fix a reference Turing machine $U$ that is universal in the following sense: for any other
machine $V$, there is a string $w_V$ such that $U(w_Vp,y) = V(p,y)$ if $V(p,y)$ is defined. 
If $y$ is the empty string we write $U(p)$ rather than $U(p,y)$.

The {\em Kolmogorov complexity} of $x$ is defined as 
\[ C(x)=
\min_{p}\{|p| : U(p)= x \}.
\]
Note that changing the universal machine $U$ affects Kolmogorov complexity  by less than an
additive constant.



Koppel~\cite{koppel87}, using monotone functions as a model, defined sophistication for infinite strings. Later, Li and Vit\'anyi~\cite{LiVi97} and Antunes and Fortnow~\cite{soph} independently simplified Koppel's definition of sophistication for finite strings, using computable functions (that are not necessarily monotone). %See~\cite{antunes}, \cite{GTV01} and \cite{Vit06} for more background. 

\begin{definition}[as in \cite{soph}]\label{AF}
The \em sophistication \em of $x$ with significance $c$ (also called $c$-sophistication) is:
\[
\soph{c}(x)=\min_p\left\{|p|: \begin{array}{l}\mbox{$U(p,d)$ is defined for all $d$}\\ \mbox{ and there is a~$d$ \mbox{s.t. } U(p,d)=x}
  \\ \mbox{ and }|p|+|d|\leq C(x)+c\end{array}\right\} .
  \] 
\end{definition}





Bennett~\cite{ben88} defined the $c$-significant logical depth of an object $x$ as the time required by the machine $U$ to generate $x$ with a program $p$ that is $c$-incompressible ({\em i.e.} $C(p) \ge |p|-c$). 
We use a more intuitive version of logical depth (also discussed in~\cite{ben88}), 
and argue at the end of this section that for our purposes this notion is sufficiently close
to Bennett's definition.
%\begin{definition}[Logical Depth]\label{true-def}
%\rm
%The logical depth of a string $x$ at a significance level $c$ is
%\[
%ldepth_c(x)=\min \left\{t(|x|): \frac{Q^t_U(x)}{Q_U(x)} \geq 2^{-c}\right\},
%\]
%where the minimum is taken over all time constructible $t$. 
%\end{definition}
%
%\begin{definition}[Logical depth]\label{logicaldepth}
A string's \em logical depth \em at significance level $c$ is
\[
\ld{c}(x) = \min\{\halttime(p) : |p| \leq C(x) + c \textnormal{ and } U(p) = x\} ,
\] 
where $\halttime(p)$ denotes the amount of computation steps made by $U$ to reach a halting state.

%\end{definition}
%
One can, scale down the running time to program length using the inverse Busy Beaver function 
%, similar to the notion of Busy Beaver computational depth introduced in \cite{soph}. 
\[bb(n) = \min\left\{|p|:U(p) \mbox{ halts and } \halttime(p) \ge n\right\}.\] 
Based on this function one can consider the following variant of logical depth.

\begin{definition}%[Busy Beaver logical depth]
  The \em Busy Beaver logical depth \em of $x$ with significance $c$ is:
  \begin{eqnarray*}
    \ld{c,U}^{bb}(x) &=& bb(\ld{c}(x)) \\
    &=& \min_{p,q}\left\{|q|:\begin{array}{l} |p| \leq C_U(x) + c \mbox{ and } U(p)=x\\ \mbox{and } \halttime(p) \le \halttime(q)\end{array}\right\}
  \end{eqnarray*}
\end{definition}
%
From the definition it is easy to see that $\ld{c}^{bb}(x) \le C(x) \le |x| + O(1)$. 
Recall the definition of {\em $\varepsilon$-close} functions in section~\ref{sec:overview}. 
For some machines $U$ we have $\ld{c,U}(x) \ge |x|$, for example if every halting program 
on $U$ always scans the full input. Changing two such machines changes 
the Busy Beaver logical depth to an $O(1)$-close function: 
\begin{lemma}\label{lem:depthIsInvariant}
  For all universal\footnote{In fact the proof only requires that $U$ and $V$ are
    optimal, i.e. for all machines $W$ there exist $c_W$ 
    such that $C_U(x) \le C_W(x) + c_W$ and similar for $V$.}
  Turing machines $U$ and $V$, there exist a constant~$c'$ 
  such that for all $c$ and $x$: $\ld{c,U}(x) \ge |x|$ [no Busy Beaver here!] implies
  \[\ld{c+c',V}^{bb}(x) \le \ld{c,U}^{bb}(x) + c'.\]
\end{lemma}


\begin{proof}
  Let $w_V$ be the prefix such that  $V(w_Vp)$ simulates $U(p)$ for all~$p$. 
  Our result would follow easily if we assume that for any halting programs $p,q$ on $U$ such that
  $\halttime(p) \le \halttime(q)$ we have $\halttime(w_Vp) \le \halttime(w_Vq)$ on~$V$;  {\em i.e.}
  simulating $U$ on $V$ preserves the order of computation time.  
  Indeed, any pair~$(p,q)$ usable in the definition of depth on $U$ defines a pair~$(w_Vp, w_Vq)$ that can be used in the definition of depth on~$V$. 
  The program $w_Vp$ is minimal on~$V$ within $c + |w_V| + |w_U|$ error 
  (where $w_U$ is the string that allows to simulate~$U$ on~$V$).
  Hence, the pair~$(w_Vp, w_Vq)$ witnesses an increase of sophistication by at most~$|w_V|$ 
  for an increase of the significance of at most $c + |w_V| + |w_U|$. 

  In the case where the assumption is not true, we need to find $c'$ and a program of length at most
  $|q|+c'$ on $V$ that computes longer than~$\halttime(w_Vp)$ (where $c'$ that does not depend on
  $p,q,c$). 
  Let us try the following algorithm on input $q$: determine all programs $p$ that have running time at most
  $\halttime(q)$ on~$U$,  determine for all these $p$'s the maximal running time
  $T$ of a program $w_Vp$ on $V$, and finally print a string of length~$T$.  For $(p,q)$ 
  usable in the definition of $\ld{c,U}(x)$, the algorithm with input $q$
  produces an output longer than $\halttime(w_Vp)$, and by universality there is a program
  of length $|q|+c'$ on~$V$ that print this string and hence computes longer than $T$. 

  This reasoning has a bug, we assumed that only finitely many programs on $U$ have 
  halting time at most $\halttime(q)$. To fix this, we use the additional assumption
  $\ld{c,U}(x) \ge |x|$:
  we only need to consider pairs $(p,q)$ on $U$ such that
  $|p| \le |x| + O(1)$ and $|x| \le \halttime(q)$, which implies $|p| \le \halttime(q) + O(1)$.
  Adding this condition to the considered set of programs makes it finite.
\end{proof}

Recall that Bennett's definition of logical depth is the minimal computation time of a 
program on a prefix-free machine $W$ (of some type) that is $c$-incompressible. 
We show that when scaled by inverse Busy Beaver functions, 
both notions of depth are $O(\log |x|)$-close. 
On a prefix-free machine~$W$, both (unscaled) depths are closely related:
Bennett's logical depth of $x$ at significance $c$ is at most $\ld{c+O(\log |x|),W}(x)$, 
because any $c$-shortest program $p$ for $x$ is $c+O(1)$-incompressible on $W$. 
On the other hand, by~\cite[Lemma 5.3]{DepthAndReducibility} (attributed to Bennett~\cite{ben88}),
$\ld{c+O(1)}(x)$ is bounded by a computable function of Bennett's logical depth of $x$ with
significance $c$.  Hence, after rescaling with the inverse Busy Beaver function, both notions are
$O(1)$-close. Exchanging prefix-free machine by a plain machine, both depth notions are $O(\log
|x|)$-close; indeed this follows by the same argument as Lemma~\ref{lem:depthIsInvariant} for $W=V$
and replacing $|w_V|$ by $O(\log |x|)$-terms in the proof (since $|K_W(x)-C_U(x)| \le O(\log |x|)$).



\section{Sophistication and Busy Beaver logical depth are close}\label{sec:relacoes}

Koppel~\cite{koppel87} claimed the equivalence between logical depth and sophistication for infinite
sequences. For such sequences, depth is defined as the minimal complexity of a total function rather
than the complexity of a number.  In this section we study the relationship between sophistication
and Busy Beaver logical depth by showing that if we allow logarithmic terms in the significance
levels these two measures are $O(\log n)$-close.

\begin{theorem}\label{theo:close}
  The functions $\ld{c}^{bb}(x)$ and $\soph{c}(x)$ are $O(\log |x|)$-close, i.e.  for some $e$ and
  for all $c$ and $x$ with $|x| \ge e$:
  \begin{eqnarray*}
    \ld{c}^{bb}(x) &\le& \soph{c + e\log |x|}(x)+e\log |x| \\
    \soph{c}(x) &\le& \ld{c + e\log |x|}^{bb}(x) + e\log |x|.
  \end{eqnarray*}
\end{theorem}

A short and more technical proof involving $\Omega$-numbers is given in the appendix. 
\begin{proof} 
  \textbf{Here and below implicit $O(\cdot)$ constants do not depend on~$c$}, for example 
  $f_{O(h_c(n))}(n) \le O(g_c(n))$ means
  that there exist $N,M$ such that for all $c$ and $n \ge N$ we have 
  $f_{Mh_c(n)}(n) \le Mg_c(n)$. 
  
  Let $x$ be of large length $n$.
  To prove the first inequality, note that we can assume that $c + 2\log (n) \le n + O(1)$ 
  because otherwise the printing program would witness $\ld{c+2\log n}^{bb}(x) \le O(\log n)$.
 
  Let $(p,d)$ be a two part code with total program $p$ 
  witnessing $\soph{c}(x)$.  This code $(p,d)$ naturally defines a one-part code $\ovl{p}d$ where
  $\ovl{p}$ is a self-delimiting code of length at most $|p| + 2\log n$ such that $U(\ovl{p}d)$ 
  evaluates $U(p,d)$. It remains to show that $\halttime(\ovl{p}d)$ is bounded by the computation time
  of a program of length $|p| + O(\log n)$.
  Indeed, the computation time is bounded by 
  $$
  \ds{t=\max \left\{ \halttime(\ovl{p}e) : |e| \le n \right\}} \,,
  $$ 
  and $t$ can be computed from $\ovl{p}$ and $n$; hence, 
  a shortest program that prints $t$ zeros satisfies the conditions.

\smallskip

  Now we prove the second inequality. For each $k,l$ such that $l \le k$ consider a sequence of strings and markers 
    $$ \ds{x_1, x_2, \dots, x_i, \Box, x_{i+1}, \dots, x_j, \Box, x_{j+1}, \dots} 
   $$ 
  enumerated as follows: dovetail all programs of length $l$ and $k$, and enumerate their output in order of computation
  time. Each time a program of length $l$ is enumerated, also append a marker to the series (if other programs with the same computation time appear, append the marker last).
    One easily observes that:
    \begin{enumerate}[i)]
      \item\label{en:uniform} the sequence is enumerated uniformly from $k,l$,
      \item \label{en:markers} there are at most $2^l$ markers, and at most $2^k$ strings, 
      \item if a program of length $k$ outputs $x$ in time at most $BB(l)  = \max\left\{ \halttime(p) : |p| \le l \right\}$, 
	then $x$ appears in the sequence before its last marker. 
    \end{enumerate}

  \noindent
  The second inequality follows from:
  \begin{claim}\label{claim}
    Every string that appears before the last marker in a sequence satisfying properties
    \ref{en:uniform} and \ref{en:markers}, 
    satisfies $\soph{k - C(x) + O(\log k)}(x) \le l + O(\log k)$.
  \end{claim}
  Indeed, notice that if $l = \ld{c}(x)$ then there is a program for $x$ of length at most $C(x)+c$ that
  runs in time at  most $BB(l)$. Also, if $k$ is the length of this program then $l \le k \le C(x) +
  c$. Notice that $x$ appears in the sequence before the last marker.  By the claim, we have
  $$
    \soph{c + O(\log k)}(x) \le l + O(\log k).
    $$ 
  We have $\log k \le \log (n+c) \le \log n + \log c$.
  Without loss of generality we can assume that
  $c \le n + O(1)$ because otherwise, $\soph{c}(x) \le O(\log n)$ and the theorem would
  follow  trivially.  This implies $\log k \le O(\log n)$, and hence the second inequality.

In order to complete the proof of Theorem \ref{theo:close} we now prove Claim \ref{claim}. 
  For any $x$ as in the Claim,  we need to show that there exist a total program $p$ such that $|p| \le l + O(\log k)$, and $U(p,d) = x$ and $|p| + |d| \le k + O(\log k)$ for some $d$.

  With every segment of strings $x_{i+1}, \dots, x_j$ in the sequence, separated by two markers $\Box$, we associate a function $f$ that maps the lexicographic first $j-i$ strings to  $x_{i+1}, \dots, x_j$ and all other strings to the empty string. 
 Notice that  $f$ is total, and can be computed from $k,l$ and the amount of markers that  proceed the defining segment. Therefore there exists a program $p$ for $f$ such that  $|p| \le l + O(\log kl) = l + O(\log k)$.
  
  Now we only need to show that for any segments containing  $x$, 
  there exists also a total program $p$ for $f$ such that
  $U(p,d)=x$ and $|p| + |d| \le k + O(\log k)$ for some $d$.
  Assume that the logarithmic size of the segment is $\delta$. 
  Observe that there are at most
  $2^{k-\delta}$ segments of size at least $2^\delta$ (by condition \ref{en:markers}).
  Hence, there is a program $p$ for $f$ such that
  $|p| \le k - \delta + O(\log kl\delta)$. 
  Since the segment contains $x$, there is a $d$ such that $f(d)=x$, 
  and by construction $|d| \le \delta$.  Hence 
  $|p| + |d| \le (k - \delta) + \delta + O(\log kl\delta) \le k + O(\log k)$.  
\end{proof}





One can ask if an equivalence between sophistication and Busy Beaver logical depth is possible with
constant precision in the significance levels. The answer is negative:

\begin{theorem}\label{th:ldepthVsSoph}
For all large $l$ there exist infinitely many strings $x$ such that
$\ld{l}^{bb}(x) \geq |x| - O(l)$ and $\soph{0}(x)\leq O(l^2 2^l)$.
\end{theorem}

Note that choosing $c=0$ in $\soph{c}(x)$ makes the theorem stronger,
because $\soph{c}(x)$ is a non-increasing in~$c$.

The difference between logical depth and sophistication
is not so surprising; the first one is based on one part descriptions while the latter is based on
two-part descriptions for $x$,  {\em i.e.} the Turing machine computes $x$ from two strings
separated by a blank.  The position of the blank can be encoded as a logarithmic amount of
information, and this sometimes allows us to make a two-part code shorter than the Kolmogorov
complexity (see  Lemma \ref{lem:twopartShorter}). A different question is whether
an equivalence holds with $O(1)$-precision when the notions are defined with prefix-free complexity. 
The answer is negative which follows by~\cite[Proposition 3.2.2 p. 3-14]{BauwensPhd}.
The proof of Theorem \ref{th:ldepthVsSoph}  uses the two subsequent lemmas.


\begin{lemma}\label{lem:twopartShorter}
 For some $c'$ and for all $k$ and $x$ such that $k + \log k \leq |x|$ we have
  \[
   \soph{|x|-C(x)-\log k + c'}(x) \le k + c'.
  \]
\end{lemma}

\begin{proof}
  Let $n = |x|$. In order to prove the lemma it is sufficient to show that there is a two-part
  description $(p,d)$ for $x$ satisfying  $|p|+|d| \leq n - \log k + O(1)$ and $|p| \leq k + O(1)$.
  The idea to prove it, is to use the length of $|p|$ to encode the last $\log k-1$~bits of~$x$.
  Let~$i$ be the index of the last $\log k-1$~bits of $x$ in the lexicographic order of strings; ({\em
  i.e.}, $x_{n - \log k + 2}\dots x_n$ is the $i$-th string in the sequence $\varepsilon, 0, 1, 00, 01,
  \dots$). Notice that $i < k$.

  Let $p$ be the program that on input $d$ first prints $x_1\dots x_i$, subsequently prints $d$,
  and finally prints $x_{n-\log k+2}\dots x_n$. Notice that this defines a total function.  Moreover,
  only the information in $x_1\dots x_i$ is needed to evaluate this function, since the last part of
  the output can be computed from $i$.
  Hence, we can construct $p$ such that $|p| = i + O(1) \leq k + O(1)$.
  Furthermore, for $d = x_{i+1}\dots x_{n-\log k+1}$ we have $U(p,d) = x$ and 
  $|p| + |d| \leq (i + O(1)) + (n - i - \log k) \le n - \log k + O(1)$.  
\end{proof}



\begin{lemma}\label{lem:controlLdepthAndC}
 For some $c$ for all large $d$ and for all $n$ there exist $x$ of length $n$ such that
  \[\begin{array}{c}
     C(x) \geq n - d \,, \\ \ \\
     \ld{d - 2\log d - c}^{bb}(x) \geq n - d \,.
  \end{array}\]
\end{lemma}


\begin{proof}
Assume that $n>d$, since otherwise  the lemma would be trivial. We choose $x$ to be the lexicographically first string of length $n$  which  is incompressible in time $BB(n - d)$, {\em i.e.} no program strictly shorter than $n$ computes $x$ in time $BB(n - d)$.
 To show the inequalities of the lemma, it suffices to show that
 \[
   n - d < C(x) \leq n - d + 2\log d + O(1).
 \]
 For the right inequality, notice that we can compute $x$ from $BB(n -d)$ and $n$. Furthermore, with $O(1)$ bits of information, $n$ can be computed from $d$ and the length of a witnessing program for $BB(n - d)$ (notice that a program witnessing $BB(n-d)$ has length $n-d + O(1)$). 
 Hence $x$ has a program of length $n - d + 2\log d + O(1)$.
 
For the left inequality, notice that by the right inequality we have $C(x) < n$ for large~$d$. 
By choice of $x$, any program
producing $x$ of length at most $n-1$ must do it in time longer than $BB(n-d)$, and by definition of
$BB(n-d)$ this program must be strictly longer than $n-d$.  
\end{proof}


\begin{proof}[Proof of Theorem \ref{th:ldepthVsSoph}]
  Let $c'$ be the constant from Lemma \ref{lem:twopartShorter}.
  For any large $k$ we apply  Lemma \ref{lem:controlLdepthAndC} with $d = \log k - c'$ to obtain a
  string $x$ of complexity $C(x) \ge |x|-\log k + c'$. Let us apply this bound to Lemma
  \ref{lem:twopartShorter}; the significance of the sophistication is at most  $|x| - (|x|-\log k + c')
  - \log k + c' = 0$ and  we conclude that $\soph{0}(x) \le k \le O(2^d)$.

  At the same time $x$ satisfies $\ld{d - 2\log d -c}(x) \ge |x|-d$. Hence by substituting  $l = d -
  2\log d -c$ the equations of the theorem are satisfied. 
  Because $k$ can be any large number, also $d$ and $l$ can be any large number.
\end{proof}




\section{Sophistication is unstable}\label{sec:sophunstable}

In~\cite{soph} the authors conjecture that Koppel's definition of sophistication might not be stable, in the sense that small changes in the constant $c$ of the significance level could drastically change the value of $\soph{c}(x)$. 
To avoid this potential problem, they incorporated the significance level as a penalty in the formula trying to obtain a more robust measure, called coarse sophistication. 
However, this measure is not robust in the sense that drastic changes can happen for slight changes of the weight of the penalty function~\cite{SSS}.

In this section, we prove that with small changes in the significance level $c$ of sophistication
its value can change almost maximally, answering affirmatively to the conjecture in \cite{soph} discussed above. 
%This also implies that for unchanged significance sophistication is machine dependant in an almost maximal way.


From the results mentioned in Section~\ref{sec:overview} we know that all sophistication measures
are unstable if the significance is increased by $O(\log |x|)$. Moreover, the theorem below can be
proven for probabilistic and set sophistication when defined in terms of prefix-free complexity with
the same proof technique as~\cite[Theorem IV.4]{vv04}.  However, for plain Kolmogorov complexity
this is not longer true  and hence it could be the case that 
the sophistication measure considered here is more stable.  The next theorem shows that this is not the case.


\begin{theorem}\label{th:sophUnstable}
For some $e$ and for all large $c$ there are infinitely many $x$ such that\footnote[1]{
  For any $\varepsilon>0$, we can replace the term $\tfrac{3}{4}|x|$ by $(1-\varepsilon)|x|$ 
  if the significance of the second sophistication term is replaced by $c + \log 1/\varepsilon + O(\log c)$.
  }
\[
\soph{c}(x) - \soph{c+e\log c}(x) \ge  \tfrac{3}{4}|x|. 
\]
\end{theorem}

\begin{proof}
Recall that in our notation, the implicit $O(\cdot)$ constants do not depend on $c$.
It is sufficient to show that for all $k,c$ there is a string $x$ of length $n = k + \log k + 2$  such that $\soph{c-O(1)}(x) \ge k$ and $\soph{c + O(\log c)}(x) \le k/8 + O(1)$.
 
Our construction of $x$ implies that $C(x) \le k - c + O(\log c)$. 
Hence, applying Lemma \ref{lem:twopartShorter} with $k \leftarrow k/8$ implies that $\soph{c +
O(\log c)}(x) \le k/8 + O(1)$  [the significance is $(k + \log k + 2) -
(k - c + O(\log c)) - \log (k/8) + O(1) \le c + O(\log c)$]. Furthermore, $\soph{c-O(1)}(x) \ge k-c$ if
we consider $x$ such that $C(x) \ge k-c$ and such that there is no pair $(p,d)$ satisfying the
following properties 
\begin{enumerate} [i)]
   \item $U(p,d) = x$ and $|p|+|d| < k$, \label{en:condX}
   \item $|p| < k-c$ and $U(p,y)$ is defined for all~$y$ 
     such that $|p|+|y| < k$.\label{en:condProg}
 \end{enumerate}

Now we describe how we construct such $x$. We keep a list of all strings of length $n$, which
received marks. At each stage we mark strings that do not satisfy the conditions above.
At each time, the lexicographic first string that has no mark is the current candidate 
to satisfy the conditions above. 
Marks are given as follows: we dovetail all programs, and if a program of length less than $k-c$
halts with an output of length $n$, then that output is marked. Clearly, there are less than $2^{k-c}$
strings that are marked in this way. Moreover,  if a program $p$ is found satisfying
condition \ref{en:condProg}),  then all corresponding strings $U(p,y)$ of length $n$ are
simultaneously marked. Thus these marks appear in less than $2^{k-c}$ different moments, and the
amount of such marks is less than $\sum_{i=0}^k 2^i2^{k-i} < (k+1)2^{k}$.  Hence, the total amount
of marked strings is less than $(k+1)2^{k+1} \le 2^n$ which means there is always a
candidate for $x$ and at some point a candidate $x$ is selected that will not anymore be replaced.
By construction, $C(x) \ge k-c$ and there is no pair $(p,d)$ for which both conditions
\ref{en:condX}) and \ref{en:condProg}) are satisfied.

Now we have to prove that $C(x) \le k - c + O(\log c)$.
Since there are  less than $2^{k-c} + 2^{k-c}$ moments where new marks are given, the candidate to
$x$ is replaced less than $2^{k-c+1}$ times and hence $C(x|k,c) \le k-c + O(1)$.  In fact, $x$~can
be computed from the total number $N$ of replacements. Hence from $c$ and from $N$ represented 
in binary with $k-c$ bits we can compute $x$. ($k$ can be computed from $c$ and the length of $N$ in binary.) 
 Thus $C(x|c) \le k-c + O(1)$ and hence $C(x) \le k-c + O(\log c)$.
\end{proof}

%We remark that with essentially the same argument this result 
%holds for set sophistication defined with prefix complexity.

\section*{Acknowledgments}
The authors are grateful to Alexander Shen and 
Nikolay Vereshchagin for useful discussion.
We also thank the anonymous referees for 
suggesting the proof in the appendix and for useful comments.




\bibliographystyle{plain}
%\bibliographystyle{alpha}
%\bibliographystyle{unsrt}
%\bibliographystyle{abbrv}
\bibliography{bibtex,kolmogorov}



%
%\bibitem{IEEEhowto:kopka}
%H.~Kopka and P.~W. Daly, \emph{A Guide to \LaTeX}, 3rd~ed.\hskip 1em plus
%  0.5em minus 0.4em\relax Harlow, England: Addison-Wesley, 1999.
%
%\end{thebibliography}
%
%% biography section
%% 
%% If you have an EPS/PDF photo (graphicx package needed) extra braces are
%% needed around the contents of the optional argument to biography to prevent
%% the LaTeX parser from getting confused when it sees the complicated
%% \includegraphics command within an optional argument. (You could create
%% your own custom macro containing the \includegraphics command to make things
%% simpler here.)
%%\begin{IEEEbiography}[{\includegraphics[width=1in,height=1.25in,clip,keepaspectratio]{mshell}}]{Michael Shell}
%% or if you just want to reserve a space for a photo:
%
%\begin{IEEEbiography}{Michael Shell}
%Biography text here.
%\end{IEEEbiography}
%
%% if you will not have a photo at all:
%\begin{IEEEbiographynophoto}{John Doe}
%Biography text here.
%\end{IEEEbiographynophoto}
%
%% insert where needed to balance the two columns on the last page with
%% biographies
%%\newpage

%\begin{IEEEbiographynophoto}{Jane Doe}
%Biography text here.
%\end{IEEEbiographynophoto}
%
% You can push biographies down or up by placing
% a \vfill before or after them. The appropriate
% use of \vfill depends on what kind of text is
% on the last page and whether or not the columns
% are being equalized.

%\vfill

% Can be used to pull up biographies so that the bottom of the last one
% is flush with the other column.
%\enlargethispage{-5in}



% that's all folks
\section{Appendix}

An alternate proof is given for the second equation in  Theorem~\ref{th:ldepthVsSoph}, i.e. 
there exist $e$ such that for all $c$ and $x$ with $|x| \ge e$ we have
\[
    \soph{c}(x) \le \ld{c + e\log |x|}^{bb}(x) + e\log |x|\,.
\]
using more advanced concepts in Kolmogorov complexity: prefix stable machines and the $\Omega$-number. 
This proof appeared in older versions of the manuscript and was also suggested by one of the anonymous referees.

We start with defining these notions. A {\em prefix stable} machine $V$ is a plain machine (used above)
such that for all strings $p$ and extentions $q$ of $p$: if $p \in \Dom V$ then $q \in \Dom V$ and
$V(p) = V(q)$. For (infinite) sequences $\omega$ let $V(\omega)$ be $V(p)$ if a prefix $p$ of
$\omega$ exists such that $V(p)$ is defined, and undefined otherwise.
For any string or sequence $\omega$, let $0.\omega$ be the real $\sum_i \omega_i 2^{-i}$. 
A prefix stable machine is  {\em left computable}~\cite{EpsteinLevin} 
if for $p$ $V(p)$ is defined than for all $q$ such that $0.q \le 0.p$, also $V(q)$ is defined. There exist
universal prefix stable machines that are left computable (just rearrange the programs on a
universal machine).
Let $\Omega = \sup\{0.p: V(p) \textnormal{is defined} \}$.

It suffices to show $\soph{c + 2\log |x|,U}(x) \le \ld{c,W}^{bb}(x) + 2\log |x|$ for large $x$, 
where $W$ is a universal left computable machine and $U$ is as defined above (translating programs from 
prefix to plain machines affects theire sizes by at most $O(\log |p|)$ precision and there depth
by a computable function and this is sufficient for the theorem).
Let $p$ be a program satisfying the conditions in the definition of $\ld{c}^{bb}(x)$.
We show that the initial segment where $p$ and $\Omega$ 
are equal defines a computable function that satisfies the conditions in the definition of sophistication.
More precisely, let $i$ be the length of the common initial segment, then 
$F(d) = V(\Omega_1\dots \Omega_i0d)$ satisfies the conditions.
Clearly $F(p_{i+2}\dots p_{|p|}) = x$.
Note that, $p_1\dots p_i = \Omega_1\dots \Omega_{i-1}0$ and $\Omega_i = 1$ by construction of~$i$.
 Hence, for any $d$ 
we have $\Omega_1\dots \Omega_i0d < \Omega$ and by left computability this is in $\Dom V$, thus $F$ is computable.
It remains to show that $C(F) \le \ld{c,W}(x)+O(\log \ld{c,W}(x))$. 
This follows from $C(\Omega_1\dots \Omega_{i-1}) \le \ld{c,W}(x) + O(\log i)$.
Indeed, given $i$ and a $t$ that exceeds the computation time of $p$, we can enumerate $w$ in the 
domain of $V$ and look to the maximal value $0.w$ for all $w$ that halt in $t$ computation steps. 
We know that $0.p \le 0.w \le \Omega$, hence we can compute the first $i-1$ bits of $\Omega$. 
\end{document}



paper_ieee_toit.bbl
\begin{thebibliography}{10}

\bibitem{soph}
L.~Antunes and L.~Fortnow.
\newblock Sophistication revisited.
\newblock {\em Theory of Computing Systems}, 45(1):150--161, Springer--Verlag,
  2009.

\bibitem{afmv06}
L.~Antunes, L.~Fortnow, D.~van Melkebeek, and N.~Vinodchandran.
\newblock Computational depth: concept and applications.
\newblock {\em Theoretical Computer Science}, 354(3):391--404, 2006.

\bibitem{BauwensPhd}
B.~Bauwens.
\newblock {\em Computability in statistical hypotheses testing, and
  characterizations of independence and directed influences in time series
  using Kolmogorov complexity}.
\newblock PhD thesis, Ugent, May 2010.

\bibitem{ben88}
C.~Bennett.
\newblock Logical depth and physical complexity.
\newblock In {\em A half-century survey on The Universal Turing Machine}, pages
  227--257, New York, NY, USA, 1988. Oxford University Press, Inc.

\bibitem{Cha66}
G.~Chaitin.
\newblock On the length of programs for computing finite binary sequences.
\newblock {\em Journal of ACM}, 13(4):547--569, ACM Press, 1966.

\bibitem{Cover85}
T.~Cover.
\newblock {\em The Impact of Processing Techniques on Communications.}, chapter
  Kolmogorov Complexity, Data Compression and Inference., pages 23--33.
\newblock J. Skwyrzynski, Martinus Nijhoff Publishers, 1985.

\bibitem{CGG89}
T.~Cover, P.~Gacs, and R.M. Gray.
\newblock Kolmogorov's contributions to information theory and algorithmic
  complexity.
\newblock {\em The Annals of Probability}, 17(3):840--865, 1989.

\bibitem{CoverElements}
T.~Cover and T.~Joy.
\newblock {\em Elements of Information Theory}.
\newblock John Wiley \& sons, 1991.

\bibitem{EpsteinLevin}
S.~Epstein and L.~Levin.
\newblock On sets of high complexity strings.
\newblock {\em CoRR}, abs/1107.1458, 2011.

\bibitem{GTV01}
P{\'e}ter G{\'a}cs, John Tromp, and Paul M.~B. Vit{\'a}nyi.
\newblock Algorithmic statistics.
\newblock {\em IEEE Transactions on Information Theory}, 47(6):2443--2463,
  2001.

\bibitem{GML96}
M.~Gell-Mann and S.~Lloyd.
\newblock Information measures, effective complexity, and total information.
\newblock {\em Complexity}, 2(1):44--52, 1998.

\bibitem{GML04}
M.~Gell-Mann and S.~Lloyd.
\newblock Effective complexity.
\newblock {\em Nonextensive entropy}, pages 387--398, 2004.

\bibitem{DepthAndReducibility}
D.~Juedes, J.~Lathrop, and J.~Lutz.
\newblock Computational depth and reducibility.
\newblock {\em Theoretical Computer Science}, 132:37--70, 1994.

\bibitem{kol65}
A.~Kolmogorov.
\newblock Three approaches to the quantitative definition of information.
\newblock {\em Problems of Information Transmission}, 1(1):1--7,
  Springer--Verlag, 1965.

\bibitem{KolmogorovTallinn}
A.N. Kolmogorov.
\newblock Talk in information theory symposium.
\newblock In {\em Tallinn, Estonia}, 1973.

\bibitem{KolmogorovAbstract}
A.N. Kolmogorov.
\newblock Complexity of algorithms and objective definition of randomness.
\newblock 29(4):155, 1974.
\newblock Russian abstract of talk at Moscow Math. Soc. meeting. 4/16/1974.
  English abstract in \cite[p.438]{livi}.

\bibitem{koppel87}
M.~Koppel.
\newblock Complexity, depth, and sophistication.
\newblock {\em Complex Systems}, 1:1087--1091, 1987.

\bibitem{koppel88}
M.~Koppel.
\newblock Structure.
\newblock In R.Herken, editor, {\em The Universal Turing Machine: a
  Half-Century Survey, 2nd edition}, pages 403--419. Springer-Verlag, 1995.

\bibitem{koppel91}
M.~Koppel and H.~Atlan.
\newblock An almost machine-independent theory of program-length complexity,
  sophistication, and induction.
\newblock {\em Information Scinces}, 56(1-3):23--33, Elsevier Science
  Publishers Ltd., 1991.

\bibitem{LiVi97}
Ming Li and P.~Vit\'{a}nyi.
\newblock {\em An Introduction to Kolmogorov Complexity and Its Applications}.
\newblock Springer-Verlag, 1997.

\bibitem{livi}
Ming Li and P.~Vit\'{a}nyi.
\newblock {\em An Introduction to Kolmogorov Complexity and Its Applications}.
\newblock Springer-Verlag, 2008.

\bibitem{effCompVsDepth}
A.~Nihat, M.~Muller, and A.~Szkola.
\newblock Effective complexity and its relation to logical depth.
\newblock {\em IEEE Transactions on Information Theory}, 56(9):4593--4607,
  2010.

\bibitem{Shen83}
A.~Shen.
\newblock The concept of (alpha, beta)-stochasticity in the kolmogorov sense
  and its properties.
\newblock {\em Soviet Mathematics Doklady}, 28(1):295--299, 1983.

\bibitem{ShenAlgorithmicStatistics}
A.~Shen.
\newblock Algorithmic statistics: main results, 2013.
\newblock In preparation.

\bibitem{Sol64}
R.~Solomonoff.
\newblock A formal theory of inductive inference, \textnormal{Part I}.
\newblock {\em Information and Control}, 7(1):1--22, Academic Press Inc., 1964.

\bibitem{SSS}
N.~Vereshchagin.
\newblock Algorithmic minimal sufficient statistic revisited.
\newblock {\em Mathematical Theory and Computational Practice}, pages 478--487,
  2009.

\bibitem{vv04}
N.~Vereshchagin and P.~Vitanyi.
\newblock Kolmogorov's structure functions and model selection.
\newblock {\em IEEE Transactions on Information Theory}, 50:3265--3290,
  Computer Society, 2004.

\bibitem{SSSdifferent}
N.~Verschagin.
\newblock On algorithmic strong sufficient statistics.
\newblock In {\em Proceedings of Computability in Europe}, July 2013.

\bibitem{Vit06}
Paul M.~B. Vit{\'a}nyi.
\newblock Meaningful information.
\newblock {\em IEEE Transactions on Information Theory}, 52(10):4617--4626,
  2006.

\bibitem{Vyu87}
V.~V’yugin.
\newblock On the defect of randomness of a finite object with respect to
  measures with given complexity bounds.
\newblock {\em Theory Prob. Appl.}, 32(3):508--512, 1987.

\end{thebibliography}
