\vspace*{-3pc} Forbidden Information
Leonid A.~Levin
111 Cummington Street
Boston
G\"odel Incompleteness Theorem leaves open a way around it, vaguely perceived for a long time but not clearly identified. (Thus, G\"odel believed informal arguments can answer any math question.) Closing this loophole does not seem obvious and involves Kolmogorov complexity. (This is unrelated to, well studied before, complexity quantifications of the usual G\"odel effects.) I consider extensions $U$ of the universal partial recursive predicate (or, say, Peano Arithmetic). I prove that any $U$ either leaves an $n$-bit input (statement) unresolved or contains nearly all information about the $n$-bit prefix of any \re real {\r} (which is $n$ bits for some \r). I argue that creating significant information about a \trm {specific} math sequence is impossible regardless of the methods used. Similar problems and answers apply to other unsolvability results for tasks allowing non-unique solutions, \eg non-recursive tilings.
cs0203029.tex
\documentclass[11pt]{article}\textwidth 6.5in\textheight 9in
 \usepackage{amssymb} \usepackage [colorlinks] {hyperref}
 \topmargin -3pc \oddsidemargin 0in \evensidemargin 0in \begin{document}

 \newcommand{\trm}[1]{{\bf\em #1}} \newcommand\emm[1]{{\ensuremath{#1}}}
 \newtheorem{thr} {Theorem} \newtheorem{lem} {Lemma}
 \newtheorem{dfn} {Definition} \newtheorem{ntn} {Notation}
 \newtheorem{prp} {Proposition} \newtheorem{cor} {Corollary}
 \newtheorem{rem}{Remark}\newtheorem{nt}{Note}\newtheorem{cmt}{Comment}
 \newcommand\edf{{\stackrel{\mbox{\scriptsize df}}=}}

 \newcommand\m{\mbox{\bf m}} \newcommand\K{\mbox{\bf K}}
 \renewcommand\d{\mbox{\bf d}} \renewcommand\Pr{\mbox{\bf Pr}}
 \newcommand\I{\mbox{\bf I}} \newcommand\ov[1]{{\overline{#1}}}
 \newcommand\floor[1]{{\lfloor#1\rfloor}} \newcommand\ceil[1]{{\lceil#1\rceil}}

 \newcommand\etc{{\em etc}} \newcommand\ie{{\em i.e.,\ }}
 \newcommand\eg{{\em e.g.,\ }} \newcommand\re{{\em r.e.\ }}
 \newcommand\RE{{\em R.e.\ }} \newcommand\M{\mbox{\bf M}}
 \newcommand\KM{\mbox{\bf KM}} \newcommand\E{\mbox{\bf E}}
 \newcommand\W{{\emm\Omega}} \renewcommand\a{{\emm\alpha}}
 \renewcommand\b{{\emm\beta}} \newcommand\g{{\emm\gamma}}
 \newcommand\w{{\emm\omega}} \newcommand\R{{\emm{\mathbb R}}}
 \renewcommand\r{{\emm\rho}} \newcommand\drop[1]{}
 \renewcommand\l{{\emm\lambda}} \newcommand\Es{{\mbox{$\cal E$}}}

 \newcommand\II{{\makebox[0pt][l]{\hspace*{1pt}I}}}
 \newcommand\N{{\mbox{\II N}}} \newcommand\Q{{\mbox{\II Q}}}
 \newcommand\hreff[1]{\href {http://#1} {\small http://#1}}
 \newcommand\suf{{\mbox{\bf sf}}} \newcommand\qed{\rule{1em}{1.5ex} }

\title{\vspace*{-3pc} Forbidden Information}

\author {Leonid A.~Levin\\ Boston University\thanks
 {Computer Science department, 111 Cummington Street, Boston, MA 02215.
 This research was partially conducted by the author for the
 Clay Mathematics Institute and supported by NSF grant CCF-0830719.
 \hspace{5pc} An earlier version written for FOCS 2002 while the
 author worked at the Institut Des Hautes Etudes Scientifiques.}}

\date {\hfill\parbox{228pt}
 {\em To the memory of Andrei Kolmogorov,\\*
 In the 100th year since his birth (4/25/1903).}}

\maketitle\begin{abstract} G\"odel Incompleteness Theorem leaves open a
way around it, vaguely perceived for a long time but not clearly
identified. (Thus, G\"odel believed informal arguments can answer any
math question.) Closing this loophole does not seem obvious and involves
Kolmogorov complexity. (This is unrelated to, well studied before,
complexity quantifications of the usual G\"odel effects.)
 I consider extensions $U$ of the universal partial recursive predicate
(or, say, Peano Arithmetic). I prove that any $U$ either leaves an
$n$-bit input (statement) unresolved or contains nearly all information
about the $n$-bit prefix of any \re real {\r} (which is $n$ bits for
some \r). I argue that creating significant information about a \trm
{specific} math sequence is impossible regardless of the methods used.
Similar problems and answers apply to other unsolvability results for
tasks allowing non-unique solutions, \eg non-recursive tilings.
\end{abstract}

\section {Introduction.}

D.Hilbert asked if Peano Arithmetic (PA: consisting of logic and
algebraic axioms and an infinite family of Induction Axioms) can be
consistently extended to a complete theory. The question was somewhat
vague since an obvious answer was ``yes'': just add to PA axioms a
maximal consistent set, clearly existing albeit hard to find.\footnote
{I assume PA is consistent: another can of worms.}
 K.G\"odel formalized this question as existence, among such extensions,
of recursively enumerable (\trm {r.e.}) ones and gave it a negative
answer. Its mathematical essence is the absence of total recursive
extensions of universal partial recursive predicate.

This negative answer apparently was never accepted by Hilbert, and
G\"odel himself \cite {goedel} had reservations:
 ``Namely, it turns out that in the systematic establishment of the
 axioms of mathematics, new axioms, which do not follow by formal logic
 from those previously established, again and again become evident.
 It is not at all excluded by the negative results mentioned
 earlier that nevertheless every clearly posed mathematical
 yes-or-no question is solvable in this way. For it is just this
 becoming evident of more and more new axioms on the basis of the
 meaning of the primitive notions that a machine cannot imitate.''

As is well known, the absence of algorithmic solutions is no obstacle
when the requirements do not make a solution unique.
 A notable example is generating strings of linear Kolmogorov
complexity, \eg those that cannot be compressed to half their length.
Algorithms fail, but a set of dice does a perfect job!\footnote
 {Note that no such problems arise for the weaker and less dramatic
version of G\"odel Theorem which makes the extension unique by requiring
\w-consistency (it means $\exists x A(x)$ cannot be proven if $A(x)$
can be refuted for each specific constant $x$). \cite {LMSS} proved that
no randomized algorithm has a positive probability to solve a task with
a unique non-recursive solution. \cite {brzd2} and \cite {soare}
observed that this is no longer the case when the solution is not
unique, \eg for such interesting tasks as listing infinite subsets of an
immune co-\re set.}

Thus, while \re sets of axioms cannot complete PA, completion by other
realistic means remained a possibility. In fact, it is easy to construct an
\re theory $R$ that, like PA, allows no consistent completion with \re
axiom sets. Yet, \cite {brzd2,soare} showed that this theory (though not
PA itself) allows a recursive set of {\em pairs} of axioms such that
random choice of one in each pair assures such completion with
probability 99\%.

Of course, G\"odel's remark envisioned more sophisticated ways to choose
axioms :-). However, the impossibility of a task can be formulated more
generically. \cite {K65} defined a concept of {\bf mutual information}
in two finite strings. It can be refined and extended to infinite
sequences, so that it satisfies conservation inequalities: cannot be
increased by deterministic algorithms or in random processes or with any
combinations of both. In fact, it seems reasonable to assume that no
physically realizable process can increase information about a specific
sequence.

In this framework one can ask if non-mechanical means could really
enable the Hilbert-G\"odel task of consistent completion for PA
(as they do for the artificial system R just mentioned). A negative
answer follows from the existence of a {\em specific} sequence {\r}
that has infinite mutual information with {\em all} total extensions of
a universal partial recursive predicate. {\r} plays a role of a
password: no substantial information about it can be guessed, no matter
what methods are allowed.

Note that invoking G\"odel's name, does not mean my intent to consider
widely discussed complexity aspects and implications of incompleteness
theorem. In particular, I ignore complexity of completions of PA. Much
of this was considered in the 60-s,\footnote
 {The original publications, such as \cite {brzd1}, gave the technical
cores of the results and avoided discussion of straightforward
implications for formal theories, G\"odel Theorem, etc. These
implications were discussed in talks. An example is \cite {K71} where
also relevant names of the technical authors can be found. I do not
provide the bibliography, since these results are only superficially
related to the issues I address here.}
 but does not answer our question: are such completions really possible?
Strings of {\em any} complexity are easy to generate.

There are other interesting situations with a similar gap between the
proven result and its usual interpretation. Let me mention tiling, a
cute task studied in many areas of CS, Math, Physics, etc. A tile is a
unit size square with colored edges. A \trm {palette} is a finite set of
tiles with copies of which one can tile the plane so that the colors of
adjacent tiles match. Classical papers by Berger, Meyers, and others
constructed palettes $P$ that can tile an infinite plane, but only
non-recursively, which is typically interpreted as an impossibility of
tiling. That is, all programs $t(i,j)\in P$ have bounds on sizes $n$ of
squares $S_n=\{i,j<n\}$ they tile so that $t(S_n)$ can appear on
$P$-tiled planes. \cite {DLS} pushes these results to the limit, with a
palette for which $n<\|t\|$. Such palettes, thus, only allow tilings
with square borders of maximal complexity.
 This stronger result, though, makes the standard interpretation
suspicious: may these borders be just random, thus easy to tile with
dice? Or could more sophisticated and yet realistic means work?

For some palettes this is, indeed, the case, but not for all. Like all
co-\re sets, the set of planar tilings with any given palette has
members with information about any specific sequence growing with radius
$n$ as slowly as $\log n$. Still, this bound cannot be improved for
some palettes. The same holds for complete extensions of universal
{p.r.p.} and formal systems. Thus, G\"odel Theorem is not really
misleading. The proof does not seem to be obvious and is the main point
of this article.

\newpage\section {Complexity Tools.}

\paragraph {Conventions.} Let \R, \Q, \N, $B{=}\{0,1\}$, $S{=}B^*$,
$\W{=}B^\N$ be, respectively, the sets of non-negative reals, rationals,
integers, bits, finite, and infinite binary sequences (\N, $S$ usually
identified); $x _{[n]}$ is the $n$-bit prefix and $\|x\|$ is the
bit-length of $x{\in}S$. A real function $f$ and its values are \trm
{enumerable} or \re (co-\re for $-f$) if its subgraph $\{(x,q): f(x)>q
\in\Q\}$ is. \trm {Elementary} ($f{\in}\Es$) are functions $f:\W\to\Q$
depending on a finite number of digits. \trm {Majorant} is an \re\
function largest, up to a constant factor, among \re functions in its
class.

\subsection {Integers: Complexity, Randomness.}

Let us define Kolmogorov \trm {complexity} $\K(x)$ as $\ceil{{-}\log\m
(x)}$ where $\m:\N\to\R$ is the \trm {universal measure}, \ie a majorant
\re function with $\sum_x\m(x){\le}1$. It was introduced in \cite{ZL},
and noted in \cite {L73,L74,Gacs74} to be a modification (restriction to
self-delimiting codes) of the least length of binary programs for $x$
defined in \cite {K65}. While technically different, {\m} relies on
intuition similar to that of \cite {Sol}. The proof of the existence of
the largest function was a straightforward modification of proofs in
\cite {Sol, K65} which have been a keystone of the informational
complexity theory.

For $x{\in}\N,y{\in}\N$ or $y{\in}\W$, similarly, $\m(\cdot|\cdot)$ is
the largest \re real function with $\sum_x\m(x|y){\le}1$; $\K(x|y)
\edf\ceil{{-}\log\m(x|y)}$ (and is the least length of self-delimiting
programs transforming $y$ into $x$).

\cite {K65} defines \trm {randomness} deficiency $\d(x)$ of uniformly
distributed $x$ as $\|x\|{-}\K(x)$. Our modified {\K} allows extending
this to other measures $\mu$ on $\N$. A $\mu$-test is $f:\N\to\R$ with
mean $\mu(f){\le}1$ (and, thus, small values $f(x)$ on randomly chosen
$x$). For computable $\mu$, a majorant \re test is $\m(x)/\mu(x)$.
 This suggests defining $\d(x|\mu)$ as $|\log\mu(x)|-\K(x)=
\floor{\log(\m(x)/\mu(x))}{\pm}O(1)$.

\subsection {Integers: Information.}

In particular, $x{=}(a,b)$ distributed with $\mu{=}\m\otimes\m$, is a
pair of two independent, but otherwise completely generic, finite
objects. Then, $\I(a:b)\edf\d((a,b)|\m \otimes\m){=}\K(a){+}\K(b){-}\K
(a,b)$ is seen as deficiency of \trm {independence} and also measures
\trm {mutual information} in $a,b$. It was shown (see \cite {ZL}) by
Kolmogorov and Levin to be close (within ${\pm}O(\log\K(a,b))$) to the
expression $\K(a){-}\K(a|b)$ of \cite{K65}. Unlike this earlier
expression (see \cite {Gacs74}), our {\I} is symmetric and monotone:
$\I(a:b)\le\I((a,a'):b){+}O(1)$ (which will allow extending {\I} to
$\W$); it equals $\K(a)-\K(a|(b,\K(b))){\pm}O(1)$ and satisfies the
following Independence Conservation Inequalities \cite {L74,L84}:
 For any computable transformation $A$ and measure $\mu$, and some
family $t_{a,b}$ of $\mu$-tests \[\I(A(a):b)\le \I(a:b)+O(1),
\hspace{4pc} \I((a,w):b)\le \I(a:b)+\log t_{a,b}(w)+O(1).\]
 (The $O(1)$ error terms reflect the constant complexities of $A,\mu$.)
 So, independence of $a$ from $b$ is preserved in random processes,
 in deterministic computations, their combinations, etc. These
inequalities are not obvious (and false for the original 1965 expression
$\I(a:b){=}\K(a){-}\K(a/b)$~) even with $A$, say, simply cutting off
half of $a$. An unexpected aspect of $\I$ is that $x$ contains all
information about $k{=}\K(x)$, $\I(x:k)=\K(k){\pm}O(1)$, despite
$\K(k|x)$ being ${\sim}\|k\|$ or ${\sim}\log\|x\|$, in the worst case
\cite{Gacs74}. One can view this as an ``Occam Razor'' effect: with no
initial information about it, $x$ is as hard to obtain as its simplest
($k$-bit) description.

All the above works as well for the $\I_z$ variation of $\I$ allowing
all algorithms access to oracle $z$.

\newpage\subsection {Randomness and Information for Reals.}

We now extend the above concepts to reals $\a{\in}\W$. This abstraction
is often convenient (if not taken too far) for concealing $O(1)$
terms and other small mismatches in formulas for finite objects.
 A {measure} on $\W$ is a function $\mu(x){=}\mu(x0){+}\mu(x1)$, for $x
{\in}S$. Its mean $\mu(f)$ is a linear functional on \Es: $\mu(f{+}g)
{=}\mu(f) {+}\mu(g)$. It extends to other functions, as usual.
 $\mu$-tests are lower semi-continuous $f$, $\mu(f){\le}1$; computable
$\mu$ have a \trm {universal} (\ie majorant {\em r.e.}) $\mu $-test
$T_\mu$. The deficiency of $\mu$-randomness is $\d(\a|\mu)\edf$
$\floor{\log T_\mu(\a)}$.
 Martin-Lof $\mu$-random are those reals $\a$ with $\d(\a|\mu)<\infty$.

P. Martin-Lof noted that some random reals are definable in arithmetic.
In fact, the smallest in [0,1] real with the minimal deficiency of
randomness (see \cite {ZL}, sec.~4.4) is random and \re If
$(Y{+}Z)/X{\in}\Q$, we say $X$ \trm {dominates} \re reals $Y,Z$ (Solovay
reducibility, \cite {Slv,dhn}). Random are exactly those \re reals that
dominate all others (see \cite {KS}). %\drop
 {\footnote {Indeed, let $t_{a,b}(x)$ be $1$ for $a<x<b$ and $0$
elsewhere. Let an \re $T{=}\sum_ic_it_{a_i,b_i}$ be an \re test with
$T(X{+}Y){=}\infty$, $\sum_ic_i(b_i{-}a_i){\le}1$. Since $X,Y,T$ are
\re, we can modify $T$ by blocking the intervals $(a_i,b_i)$ if
$a_i{\ge}X{+}Y$ or shifting them by $y_i<Y$ to $(a_i{-}y_i,b_i{-}y_i)$
with $a_i{-} y_i<X$. Then $T$ remains an \re test with $T(X){=}\infty$.

Conversely, let $Z,X\in[0,1]$ be enumerated as $Z{=}\sup_iz_i$, $X{=}2^k
\sup_ix_i$, $x'_i{=}x_i{-}x_{i{-}1}{\ge}0$. Let $s_i{=}\max \{z_i,s_{i
{-}1}{+} x'_i\}$ and $t_k(V)$ be $1$ for $s_{i{-}1}<V<s_i{=}s_{i{-}1}{+}
x'_i$ and $0$ elsewhere. Then $2^kt_k$ and $T(V){=}\sum_k(2^k/k^2)t_k$
are \re tests.\\
 Let $y'_i{=}s_i{-}(s_{i{-}1}{+}x'_i)$, and $Y{=}\sum_iy'_i$.
If $Z{=}\sup_is_i$ for some $k$, then $Z{=}Y{+}2^{-k}X$ dominates $X$.\\
 Otherwise $s_{i{-}1}<Z< s_i{=} s_{i{-}1}{+}x'$ for some $i$,
 so $t_k(Z){=}1$ for all $k$ and $T(Z){=}\infty$.}
 }
 (Any random \re {\r} is $\sum_n\m(n)$ for some universal \m: {\r}
dominates all such sums and replacing {\m} with $\m{+}x/i$ for an \re
$x$ concentrated in $0$, preserves universality. \cite {Chaitin}
contains probably the first published discussion of randomness of
$\sum_n\m(n)$.)

\paragraph {Reals: Information.}
 \cite {L74} extends $\I$ to reals as $\I(\a:\b) \edf\floor{\log\sum_{i,j}
\m(i|\a)\m(j|\b)2^{\I(i:j)}}$.\\ (As always, we average in the linear
scale and switch to the logarithmic scale for the final expression.)

 For $\a,\b\in\N$, this equals our previous expression
 $\K(\a){+}\K(\b){-}\K(\a,\b){\pm}O(1)$ since both satisfy
 the above Independence Conservation Inequalities.
 In fact, the above extension of $\I$ to $\W$ is the smallest satisfying
the independence conservation. (The largest is described below.)

\subsection
{Complexity Randomness and Information for Reals: Stronger Version.}

\cite {L84} gives a stronger than \cite {L74} expression for $\I$ on
reals. It exceeds the needs of our paper, but I mention it here for
interested readers. \cite {L84} treats {\em partial} continuous $A:\W\to
\W$ as homogeneous concave operators $g{=}A(f)$ for $f{\in}\Es$:
$g(\w){=}\inf_{A'} f(A'(\w))$ ($A'$ are all total extensions of $A$).
$A$ turns measures $\phi$ into \trm {semimeasures} $A(\phi){=}\mu,\mu(f)
{=}\phi(A (f))$, which are homogeneous concave functionals: $\mu(f{+}g)
{\ge}\mu(f){+}\mu(g)$, $\mu(x){\ge}\mu(x0){+}\mu(x1)$, for $x{\in}S$.
\cite {ZL} used a universal (majorant r.e.) semimeasure {\M} to define
complexity of prefixes $x$ of $\a{\in}\W$ as $\KM(x)\edf\ceil {-\log\M
(x)}$.

\cite {L84} extends $\d(\a|\mu)$ to all semimeasures $\mu$, computable
or not. It lets a universal Turing machine use random input $\w$ to
enumerate subgraphs of lower semi-continuous functions $f_\w(\a)$.
To make $f_\w$ a $\mu$-test $f^\mu_\w$, it is truncated to $0$ when
$\mu(f_\w)>1$.
 \cite {L84} then defines $f^\mu(\a)$ as mean over $\w$ of $f^\mu_\w$,
$\d(\a|\mu)$ as $\floor{\log f^\mu(\a)}$, and $\I(\a:\b)$ as
$\d((\a,\b)|\M\otimes\M)$.

Thus defined, $\I$ satisfies Conservation Inequalities, due to similar
inequalities for $\d$. The {\em largest} version of $\d$ satisfying
 them can be obtained for \re semimeasures $\mu$ as follows.
 (Whether it differs from the one of \cite{L84} is unknown
 and which is best is unclear.) The idea is for $\d(\a|\mu)$
 to be bounded by $\d(\w|\l)$ if $\a=A(\w), \mu=A(\l)$.

Let an algorithm $A$ transform uniform distribution $\l$ into a
semimeasure $A(\l){\le}\mu$. Then $\d_A(\cdot|\mu)\edf\sup\{f:
A(f)\le\d(\cdot|\l)\}$. For \re $\mu$, a universal $U_\mu$ exists
with the smallest $\d_{U_\mu}(\a|\mu)+ O(1)$. Then $\d(\a|\mu)\edf
\d_{U_\mu}(\a|\mu)$ and $\I(\a:\b)\edf\d((\a,\b)| \M\otimes\M)$.

\newpage\section {Consistent Objects.}

Consistency of theories and of other objects can be expressed as
membership in co-\re sets of reals. It is convenient to define such sets
via co-\re \trm {trees}, \ie infinite sets $T{\subset}S$ containing all
prefixes and {\bf some extensions of each} member. Let $\tilde T$ be the set
of those $\w\in\W$ with all prefixes in $T$. Some co-\re trees have only
strings of linear Kolmogorov complexity. Contrast this with
 \begin{prp}\label{log} For each $\b\in\W$, each co-\re tree $T$ has
$\a\in\tilde T$ with $\I(\a_{[n]}:\b)\le 5\log n{+}O(1)$.\end{prp}
 \begin{lem}\label{hint} For each co-\re tree $T$ there is a measure
$\mu(x){=}\mu (x0){+}\mu(x1)$ with $\mu (\tilde T)>1/2$,\\ computable as
$\mu(x){=}G(x,\r_{[5\log\|x\|]})$ by an algorithm $G$ using $5\log\|x\|$
digits of a \trm {hint} $\r\in\W$.\end{lem}
 Lemma~\ref {hint} implies Proposition~\ref {log}. Indeed, algorithms
can transform uniform distribution of inputs {\w} into any computable
one; same holds for computations with oracle \r. Consider an algorithm
using {\r} to compute $\mu$ and transforming {\w} into a
$\mu$-distributed {\a} ($\in\tilde T$ with high probability).
$\I(\r_{[O(\log\|x\|)]}:\b)= O(\log\|x\|)$; random {\w} cannot add
information with high probability, and the algorithm cannot increase it
either (due to conservation inequalities).
 \paragraph {Proof of Lemma~\ref{hint}:} $G$ uses {\r} to list all
converging $k$-bit programs. As \cite {brzd1} noted, for this it needs
just one of them, the slowest. {\r} can be any \re real with
$\K(\r_{[n]}){=} k{=}n{-}o(n)$, \eg a random one. Programs that use
$\r_{[n]}$ waiting for enumeration of \r's lower bounds to exceed
$\r_{[n]}$, are slower than any programs $P$ of complexity $<k{-}2\log
n$: otherwise $\r_{[n]}$ can be generated from $P,n$.

$G$ computes $\mu$ recursively in slices $\mu_i(x)$ for $\|x\|{=}n{=}
2^{2^i}$, assuming $\mu_{i{-}1}$ already computed.\\ It will approximate
$T\cap B^n$ as $T_i{=}T_i(\r)$ by limited co-enumeration and distribute
$\mu_{i{-}1}(x)$ uniformly on all $n$-bit extensions of $x$ (which
always exist in $T$).

Let $h_i$ be the Shannon entropy of $\mu_i$, with the fractional part
rounded up to $2\log 2i$ bits.\\ Given $\mu_{i{-}1}$, shrinking $T_i$
lowers $h_i$. $G$ uses {\r} to compute the least possible $h_i$ and
co-enumerates $T_i$ until it reaches this bound. Rounding $h_i$, leaves
a fraction $f_i$ of $x\in T_i\setminus T$. Yet, $\sum_i f_i<1/2$. \qed

In particular, randomized algorithms can generate strings of length $\ge
n$ of any co-\re tree $T$ with probability $1/k^2n, k{=}\ceil{\log n}$
by guessing $k,\floor{\log\|T\cap B^{2^k}\|}$.

\subsection {Example: Tiling}

An illustration is the tiling question from the introduction. \cite
{DLS} constructs a palette $P$ forcing, on each $P$-tiling, high
complexity of all horizontal tile strings not crossing one specific
column. The same construction works if complexity restriction is
replaced with membership in any \trm {bi-tree}, \ie a (co-{\em r.e.})
tree containing all substrings (not only prefixes) of its members. To
use it, we need to encode any co-\re tree $T$ as an equivalent bi-tree
$T_2$.

Let $b(2^k(2l{+}1))\edf$ $(l\bmod2)$. The pattern of $b(n)$ for $2^a$
consecutive $n$ determines the $a{-}2$ tail bits of $n$.
 Let $\ov i$ double each bit of $i$ and alter the result's first bit.
 If $n$ ends with $k$ followed by $\ov {\|k\|}$, let $\suf(n){\edf}k$.
Let $\tilde T_1$ be a tree of sequences $\a:\N{\to}B^2$ such that $\a(n)
{=}(b(n),t)$ and for some $s{\in}\tilde T$, whenever $\suf(n)$ is
defined, $t{=}s(\suf(n))$. Let $T_2$ be a bi-tree of all segments of
members of $\tilde T_1$. Each $n$-bit $T_2$-string represents the first
$n/O(\|n\|^2)$ bits\footnote
 {Optimizing $\ov i$ coding to $\|\ov i\|{=}\K(i)$ improves the
 overhead $\|n\|^2$ to $1/\m(\|n\|)$ but cannot eliminate it.}
 of a $T$-string $s$.

In particular, $T$ (and $T_2$) can force $s$ to be random \ie have
maximal complexity. This illustrates the point: all such tilings are
highly non-recursive, yet easy to generate (with dice). They can be
expressed in a formal system that allows trivial completions but no
recursive ones.

\newpage\section {The Taboo.}

The above example does not show that all co-\re trees, such as tilings
with an arbitrary palette, allow easily generated members.
Proposition~\ref {log} sets a small but growing bound on the information
needed for that, leaving open the question the article started with. It
is resolved by the following observation central to this paper. We
represent in {\W} partial predicates as their graphs listed in arbitrary
order. Let $u$ be a universal partial recursive predicate (p.r.p ).

\begin{thr}\label{cens} Let $\r_{{\sim}n}$ be an $n{+}\K(n)$ bit prefix
of a random \re real {\r} and $U$ be a partial\\ predicate that on $B^n$
is a total extension\footnote
 {One can weaken this total extension condition to being consistent with
$u$ and defined on the specific input $px_n$ if the simple $\I$ of \cite
{L74} is strengthened to one of \cite {L84} and $\M(P(0^{\|x\|})\ldots
P(x{-}1))$ replaces $m_{x,i}$ in $P$ defined below.}
 of $u$. Then $\I(U:\r_{{\sim}n})\ge n-\K(\K(n)|n) {-}O(1)$. \end{thr}
 (This almost suffices to compute $\r_{{\sim}n}$ from
 the $B^n$-restriction $U_n$ of $U$ and $\K(U_n)$.\\
 Same holds for all \re {\r} since they reduce to same-length segments
of any random one.\\ The $\K(\K(n)|n)$ decrement is small; yet \cite
{Gacs74} ingeniously proves it ${\sim}\log\log n$, not $O(1)$.))

\paragraph {Proof.} We define a p.r.p.~$P:S{\to}B$ inductively on $B^n$.
If $x{=}0^n$ or $P(x{-}1)$ is defined, let $m_{x,i}$ denote the combined
universal measure $\sum_Q\m(Q|n)$ of all total predicates $Q$
 on $B^n$ that agree with $P$ on $[0^n,x{-}1]$ and $Q(x){\ne}i{\in}B$.
Then $P(x)$ enumerates lower bounds for $m_{x,i}$ until either exceeds
$2^{-n}$ and yields $P(x){=}i$, decreasing $\sum_i m_{x{+}1,i}$ by ${>}2
^{-n}$. For some $x_n$, $m_{x_n,i}{\le}2^{-n}$ and $P$ diverges on $[x_n,
1^n]$ with $\sum_Q\m(Q|n){\le}2/2^n$ for all total extensions $Q$ of $P$
on $B^n$.

For all such $Q$, this bound allows $2^n/O(1)$-fold increase of
$\m(Q|x_n)$,\footnote
 {This also means $I_n(x_n:Q){=}n{\pm}O(1)$ (and already implies
  Corollary~\ref {pr}, even simplifies its bound to $O(2^{-n})$ ).
  So, $\K(x_n|(Q,\K(Q|n))=O(1)$ thus the $B_n$-restriction $u_n$ of
  $u$ can be computed from $U_n,\K(U_n|n)$, if not from $U_n$ itself.}
 compared to just $\m(Q|n)=\m(\K(n)|n)\m(Q)/O(\m(n))$.
 Now, $u(px)$, with a fixed $p$, computes $P(x)$, and $U(px)$ extends
 $P(x)$ on $B_n$ to a total $Q_n$, with $\m(Q_n|U)=\m(n)/O(1)$.
 Also, $x_n,\r_{{\sim}n},\K(n)=\|\r _{{\sim}n}\|{-}n$ are {\em r.e.},
 so can be computed from one of them whose enumeration ends latest.
 This could only be $\r_{{\sim}n}$, being random and long enough
 to dominate in complexity (which computations cannot increase).

Thus, $\m(Q_n|\r_{{\sim}n})=\m(Q_n|x_n)/O(1)=2^n\m(\K(n)|n)\m(Q_n)/O(\m
(n))$. Then, $\I(U:\r_{{\sim}n})\ge$ $\log(\m(Q_n|\r_{{\sim}n})\m(Q_n|U)/\m
(Q_n))\ge \log2^n\m(\K(n)|n)-O(1)\ge n{-}\K(\K(n)|n){-}O(1)$. \qed

Since random strings contain $k$ bits of information about {\r} only
with probability $2^{-k}$ and algorithms do not increase information
(due to the Conservation Inequalities), Theorem~\ref {cens} implies
 \begin{cor}\label{pr} The probability that a randomized algorithm computes
 on $B^n$ a total extension\\ of $u$ is at most $O(2^{-n})/\m(\K(n)|n)$.
 {\em (Strengthening the $o(1)$ bound of \cite {soare}.)} \end{cor}
 (Thus, not all palettes, formal theories, etc.
 allow randomness-based tilings, completions, etc.)

Of course, nobody envisioned choosing fundamental Math axioms by coin
flips. Yet, Theorem~\ref{cens} supports a more general impossibility.
 Just like the usual interpretation of G\"odel Theorem is a matter
 of accepting Church's Thesis, judging if Theorem~\ref {cens}
 makes the completion task impossible is a matter of accepting
 the Independence Postulate discussed in the appendix.

\section* {Acknowledgments} I am grateful to Robert Solovay,
 Alexander Shen, and Bruno Durand for insightful discussions and to
 Rod Downey, Denis Hirschfeldt, and Stephen Simpson for three references.

\newpage\appendix\section* {Appendix: The Independence Postulate.}

\paragraph {IP:} {\em Let $X$ be a sequence defined with an $n$-bit
mathematical statement (\eg in PA or set theory).\\ Suppose a sequence $Y$
can be located in the physical world with a $k$-bit instruction set.\\
 Then $\I(X:Y)<k{+}n{+}c $, for some small absolute constant
$c$.}\vspace{1pc} \\ (Note that $X$ and $Y$ can each have much more than
$k{+}n{+}c$ bits of information.)

Thus, a (physical) sequence of all mathematical publications has little
information about the (mathematical) sequence of all true statements of
arithmetic. This is of little concern because the latter has, in turn,
little information about the stock market (a physical sequence). :-)

Of course, Kolmogorov information is not the only desirable commodity.
Yet, IP has interesting applications \cite {L84}. It can be restated as
a ``finitary'' version of the Church-Turing thesis (CT) by calling \trm
{recursive} those finite sequences with recursive descriptions nearly as
short as any their ``higher-level'' math descriptions.
 IP postulates that only such recursive sequences exist in reality.

Let me add (in order of increasing relevance) some comparisons between
 IP and CT:\begin{enumerate}

\item IP is stated with greater care than CT: Obviously not all strings we
generate are algorithmic (non-communist election results better not be :-).
Only mathematically defined strings need be algorithmic to be
generatable. IP includes this math clause explicitly, CT rarely does.
 \item IP is simpler, CT more abstract. All sequences we ever see are
computable just by being finite: CT is useless for them!
 IP works equally well for finite and infinite sequences.
 \item IP is easier to support: CT is usually stated with vague
reasoning. IP has broad conservation laws to support it and a general
intuition that target information cannot be increased.
 \item IP is much stronger: CT prohibits only generating the target math
sequence itself;\\ IP bars all strings with any significant information
about it. \end{enumerate}

One application is dousing G\"odel's hope cited in the Introduction,
regardless of any realizable process of axiom selection.
 The argument is ``inductive''. It seems, complicated processes we
observe, can ultimately be {\em explained}, \ie reduced to simpler ones.
These reductions use deterministic models and random ones, but neither
can {\bf\em increase} the starting information about a target.
 The toolkit of our models may change (\eg quantum amplitudes work
somewhat differently than probabilities) but it is hard to expect
new realistic primitives allowing such ``information leaks''.

 So, if {\em complicated} processes generate unlimited target
information, so must do some {\em elementary} processes,
 that admit no further explanations (reductions to simpler processes).
The existence of such elementary unexplainable information Sources
cannot be ruled out. Yet Infidels :-) can postulate it away.
 Just like the impossibility of generating power from uniform heat,
 this is an unprovable postulate, supported by proven arguments.

Note that the above argument is based on Independence Conservation
Inequalities (ICI) of \cite{L74,L84}. They deal with generation of
strings by deterministic algorithms or by random processes {\bf\em from
other strings}. If the preexisting string has no significant target
information, neither will the generated one. And despite being
intuitive, ICI are not technically trivial and should {\bf not be
confused with the easy remark} that randomized algorithms cannot
generate {\bf\em from scratch} information about math targets, such as
\eg \re reals. (Math community never tried choosing their fundamental
axioms this way :-). But the difficulty pays off, being essential for
the inductive nature of the support ICI give to IP.

\newpage\begin{thebibliography}{99}

\bibitem [DAN]{DAN} {\em Doklady} AN SSSR (= Soviet {Math.} Doclady).

\bibitem [Barzdin 68] {brzd1} Janis M. Barzdin. Complexity of programs
to determine whether natural numbers not greater than $n$ belong to a
recursively enumerable set. \cite {DAN}, 9:1251-1254,
1968.

\bibitem [Barzdin 69] {brzd2} Janis M. Barzdin'. O Vychislimosti na
Verojatnostnyh Mashinah. \cite {DAN} 189(4), 1969.

\bibitem [Berger ] {berger} R.~Berger. The undecidability of the domino
problem. {\em Memoirs of AMS}, 66, 1966.

\bibitem [Chaitin 75] {Chaitin} G.J. Chaitin.. A Theory of Program Size
Formally Identical to Information Theory. J.ACM, 22:329-340, 1975.

\bibitem [Gacs 74] {Gacs74}Peter Gacs. On the Symmetry of Algorithmic
Information. \cite {DAN} 15:1477, 1974.

\bibitem [G\"odel 61] {goedel} Kurt G\"odel. The modern development of
the foundations of mathematics in the light of philosophy. 1961. In:
Kurt G\"odel. Collected Works. Volume III. Oxford University Press.
\hreff {evans-experientialism.freewebspace.com/godel.htm}

\bibitem [Downey Hirschfeldt Nies 02] {dhn}
 Rod Downey, Denis Hirschfeldt, Andre Nies.\\
 Randomness, Computability, and Density. SICOMP 31:1169-1183, 2002.

\bibitem [Durand, Levin, Shen 01] {DLS} Bruno Durand, Leonid A. Levin,
Alexander Shen. Complex Tilings.\\ {\em J.Symb.Logic} 73/2:593-613, 2008.
Also: STOC 2001. \hreff {arXiv.org/abs/cs.CC/0107008}

\bibitem [Jockusch, Soare 72] {soare} Carl G. Jockusch, Jr., Robert I.
Soare. $\Pi^0_1$ Classes and Degrees of Theories. Trans. Am.Math.Soc.
173:35--56 1972.

\bibitem [Kolmogorov 65] {K65} Andrei N. Kolmogorov. Three Approaches to
the Concept of the Amount of Information. {\em {Probl.} {Inf.} Transm.},
1(1):1-7, 1965.

\bibitem [Kolmogorov 72] {K71} Andrei N. Kolmogorov. Complexity of
specifying and complexity of constructing mathematical objects. Part 4.
Talk at the 11/23 Meeting of Moscow {Math.} Society, 1971. Abstract in
{\em Uspekhy {Mat.} Nauk} 27(2), 1972. (In Russian.)

\bibitem [Kucera, Slaman 01] {KS} A. Kucera, T.A. Slaman. Randomness
and recursive enumerability. SIAM J. Comput. 31:199-211, 2001.

\bibitem [dLMSS 65] {LMSS} Karel deLeeuw, Edward F. Moore, Claude E.
Shannon, N. Shapiro. Computability by probabilistic machines. In {\em
Automata Studies}, Ann.Math.Studies 34. Princeton U. Press, 1965.
 %pp. 183-212

\bibitem [L 73] {L73} Leonid A. Levin. On the Concept of a Random
Sequence. \cite {DAN} 14(5):1413-1416, 1973.

\bibitem [L 74] {L74} Leonid A. Levin. Laws of Information
Conservation (Non-growth) and Aspects of the Foundations of Probability
Theory. {\em Probl {Pered.} Inf.= {Probl.} {Inf.} Transm.}
10(3):206-210, 1974.

\bibitem [L 84] {L84} Leonid A. Levin. Randomness Conservation
Inequalities. {\em Inf.\& Control} 61(1):15-37, 1984.

\bibitem [Myers 74] {myers} D.~Myers. Nonrecursive tilings of the plane.
ii. {\em J. Symb. Logic}, 39(2):286--294, 1974.

\bibitem [Solomonoff 64] {Sol} R.J. Solomonoff. A Formal Theory of
Inductive Inference. {\em Inf.\&Cntr} 7(1), 1964.

\bibitem [Solovay 75] {Slv} R. Solovay. Unpublished manuscript.
 IBM Watson Res. Ctr, New York 1975.

\bibitem [ZL 70] {ZL} Alexander Zvonkin, Leonid A. Levin. The complexity
of finite objects and the algorithmic concepts of information and
randomness. {\em UMN = Russian Math.~Surveys} 25(6):83-124, 1970.

\end{thebibliography} \end{document}

cs0203029.extracted_bib
\begin{thebibliography}{99}

\bibitem [DAN]{DAN} {\em Doklady} AN SSSR (= Soviet {Math.} Doclady).

\bibitem [Barzdin 68] {brzd1} Janis M. Barzdin. Complexity of programs
to determine whether natural numbers not greater than $n$ belong to a
recursively enumerable set. \cite {DAN}, 9:1251-1254,
1968.

\bibitem [Barzdin 69] {brzd2} Janis M. Barzdin'. O Vychislimosti na
Verojatnostnyh Mashinah. \cite {DAN} 189(4), 1969.

\bibitem [Berger ] {berger} R.~Berger. The undecidability of the domino
problem. {\em Memoirs of AMS}, 66, 1966.

\bibitem [Chaitin 75] {Chaitin} G.J. Chaitin.. A Theory of Program Size
Formally Identical to Information Theory. J.ACM, 22:329-340, 1975.

\bibitem [Gacs 74] {Gacs74}Peter Gacs. On the Symmetry of Algorithmic
Information. \cite {DAN} 15:1477, 1974.

\bibitem [G\"odel 61] {goedel} Kurt G\"odel. The modern development of
the foundations of mathematics in the light of philosophy. 1961. In:
Kurt G\"odel. Collected Works. Volume III. Oxford University Press.
\hreff {evans-experientialism.freewebspace.com/godel.htm}

\bibitem [Downey Hirschfeldt Nies 02] {dhn}
 Rod Downey, Denis Hirschfeldt, Andre Nies.\\
 Randomness, Computability, and Density. SICOMP 31:1169-1183, 2002.

\bibitem [Durand, Levin, Shen 01] {DLS} Bruno Durand, Leonid A. Levin,
Alexander Shen. Complex Tilings.\\ {\em J.Symb.Logic} 73/2:593-613, 2008.
Also: STOC 2001. \hreff {arXiv.org/abs/cs.CC/0107008}

\bibitem [Jockusch, Soare 72] {soare} Carl G. Jockusch, Jr., Robert I.
Soare. $\Pi^0_1$ Classes and Degrees of Theories. Trans. Am.Math.Soc.
173:35--56 1972.

\bibitem [Kolmogorov 65] {K65} Andrei N. Kolmogorov. Three Approaches to
the Concept of the Amount of Information. {\em {Probl.} {Inf.} Transm.},
1(1):1-7, 1965.

\bibitem [Kolmogorov 72] {K71} Andrei N. Kolmogorov. Complexity of
specifying and complexity of constructing mathematical objects. Part 4.
Talk at the 11/23 Meeting of Moscow {Math.} Society, 1971. Abstract in
{\em Uspekhy {Mat.} Nauk} 27(2), 1972. (In Russian.)

\bibitem [Kucera, Slaman 01] {KS} A. Kucera, T.A. Slaman. Randomness
and recursive enumerability. SIAM J. Comput. 31:199-211, 2001.

\bibitem [dLMSS 65] {LMSS} Karel deLeeuw, Edward F. Moore, Claude E.
Shannon, N. Shapiro. Computability by probabilistic machines. In {\em
Automata Studies}, Ann.Math.Studies 34. Princeton U. Press, 1965.
 %pp. 183-212

\bibitem [L 73] {L73} Leonid A. Levin. On the Concept of a Random
Sequence. \cite {DAN} 14(5):1413-1416, 1973.

\bibitem [L 74] {L74} Leonid A. Levin. Laws of Information
Conservation (Non-growth) and Aspects of the Foundations of Probability
Theory. {\em Probl {Pered.} Inf.= {Probl.} {Inf.} Transm.}
10(3):206-210, 1974.

\bibitem [L 84] {L84} Leonid A. Levin. Randomness Conservation
Inequalities. {\em Inf.\& Control} 61(1):15-37, 1984.

\bibitem [Myers 74] {myers} D.~Myers. Nonrecursive tilings of the plane.
ii. {\em J. Symb. Logic}, 39(2):286--294, 1974.

\bibitem [Solomonoff 64] {Sol} R.J. Solomonoff. A Formal Theory of
Inductive Inference. {\em Inf.\&Cntr} 7(1), 1964.

\bibitem [Solovay 75] {Slv} R. Solovay. Unpublished manuscript.
 IBM Watson Res. Ctr, New York 1975.

\bibitem [ZL 70] {ZL} Alexander Zvonkin, Leonid A. Levin. The complexity
of finite objects and the algorithmic concepts of information and
randomness. {\em UMN = Russian Math.~Surveys} 25(6):83-124, 1970.

\end{thebibliography}