
Mutual information I in infinite sequences (and in their finite prefixes) is
essential in theoretical analysis of many situations. Yet its right definition
has been elusive for a long time. I address it by generalizing Kolmogorov
Complexity theory from measures to SEMImeasures i.e, infimums of sets of
measures. Being concave rather than linear functionals, semimeasures are quite
delicate to handle. Yet, they adequately grasp various theoretical and
practical scenarios. A simple lower bound i$(\alpha:\beta) = \sup_{x\in N}
(K(x)  K(x\alpha)  K(x\beta)) $ for information turns out tight for
MartinLof random $ \alpha,\beta $. For all sequences I$(\alpha:\beta) $ is
minimum of i$(\alpha':\beta') $ over all $ O(1) $random $ \alpha',\beta' $
such that $ U(\alpha')=\alpha, U(\beta')=\beta $.

Taxes have major costs beyond the collected revenue: deadweight from
distorted incentives, compliance and enforcement costs, etc. A simple market
mechanism, the Equity Tax, avoids these problems for the trickiest cases:
corporate, dividend, and capital gains taxes.
It exploits the ability of the share prices to reflect the expected true
annual return (as perceived by investors, not as defined by law) and works only
for publicly held corporations. Since going or staying public cannot be forced,
and for some constitutional reasons too, the conversion to equity tax must be a
voluntary contract. Repeated reconversions would be costly (all capital gains
are realized) and thus rare. The converts and their shareholders pay no income,
dividend, or capital gain taxes. Instead, they give the IRS, say, 2% of stock
per year to auction promptly. Debts are the lender's assets: its status, not
the debtor's, determines their equitytax or incometax treatment.
The system looks too simple to be right. However, it does have no loopholes
(thus lowering the revenueneutral tax rate), no compliance costs, requires
little regulation, and leaves all business decisions tax neutral. The total
capital the equity taxed sector absorbs is the only thing the tax could
possibly distort. The rates should match so as to minimize this distortion. The
equity tax enlarges the pretax profit since this is what the taxpayers
maximize, not a different aftertax net. The wealth shelter is paid for by
efficiency, not by lost tax.

NPcomplete problems should be hard on some instances but those may be
extremely rare. On generic instances many such problems, especially related to
random graphs, have been proven easy. We show the intractability of random
instances of a graph coloring problem: this graph problem is hard on average
unless all NP problem under all samplable (i.e., generatable in polynomial
time) distributions are easy. Worst case reductions use special gadgets and
typically map instances into a negligible fraction of possible outputs. Ours
must output nearly random graphs and avoid any superpolynomial distortion of
probabilities.

Here I share a few notes I used in various course lectures, talks, etc. Some
may be just calculations that in the textbooks are more complicated, scattered,
or less specific; others may be simple observations I found useful or curious.

Noncompact symmetries cannot be fully broken by randomness since noncompact
groups have no invariant probability distributions. In particular, this makes
trickier the "Copernican" random choice of the place of the observer in
infinite cosmology models.

The combined universal probability M(D) of strings x in sets D is close to
max_{x \in D} M({x}): their ~ logs differ by at most D's information j = I(D:H)
about the halting sequence H. Thus if all x have complexity K(x) > k, D carries
> i bits of information on each x where i+j ~ k. Note, there are no ways
(whether natural or artificial) to generate D with significant I(D:H).

Below is a translation from my Russian paper. I added references, unavailable
to me in Moscow. Similar results have been also given in [Schnorr Stumpf 75]
(see also [Lynch 75]). Earlier relevant work (classical theorems like
Compression, Speedup, etc.) was done in [Tseitin 56, Rabin 59, Hartmanis
Stearns 65, Blum 67, Trakhtenbrot 67, Meyer Fischer 72].
I translated only the part with the statement of the results. Instead of the
proof part I appended a later (1979, unpublished) proof sketch of a slightly
tighter version. The improvement is based on the results of [Meyer Winklmann
78, Sipser 78]. Meyer and Winklmann extended earlier versions to machines with
a separate input and working tape, thus allowing complexities smaller than the
input length (down to its log). Sipser showed the spacebounded Halting Problem
to require only additive constant overhead. The proof in the appendix below
employs both advances to extend the original proofs to machines with a fixed
alphabet and a separate input and working space. The extension has no (even
logarithmic) restrictions on complexity and no overhead (beyond an additive
constant). The sketch is very brief and a more detailed exposition is expected
later: [Seiferas Meyer].

The combined Universal Probability M(D) of strings x in sets D is close to
max M({x}) over x in D: their ~logs differ by at most D's information j=I(D:H)
about the halting sequence H. Thus if all x have complexity K(x) >k, D carries
>i bits of information on each its x where i+j ~ k. Note that there are no ways
to generate D with significant I(D:H).

Goedel Incompleteness Theorem leaves open a way around it, vaguely perceived
for a long time but not clearly identified. (Thus, Goedel 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 Goedel effects.) I consider
extensions U of the universal partial recursive predicate (or, say, Peano
Arithmetic). I prove that any U either leaves an nbit input (statement)
unresolved or contains nearly all information about the nbit prefix of any
r.e. real r (which is n bits for some r). I argue that creating significant
information about a SPECIFIC math sequence is impossible regardless of the
methods used. Similar problems and answers apply to other unsolvability results
for tasks allowing multiple solutions, e.g. nonrecursive tilings.

Exponentiation makes the difference between the bitsize of this line and the
number (<< 2^{300}) of particles in the known Universe. The expulsion of
exponential time algorithms from Computer Theory in the 60's broke its
umbilical cord from Mathematical Logic. It created a deep gap between
deterministic computation and  formerly its unremarkable tools  randomness
and nondeterminism. Little did we learn in the past decades about the power of
either of these two basic "freedoms" of computation, but some vague pattern is
emerging in relationships between them. The pattern of similar techniques
instrumental for quite different results in this area seems even more
interesting. Ideas like multilinear and lowdegree multivariate polynomials,
Fourier transformation over lowperiodic groups seem very illuminating. The
talk surveyed some recent results. One of them, given in a stronger form than
previously published, is described below.

We consider asynchronous networks of identical finite (independent of
network's size or topology) automata. Our automata drive any network from any
initial configuration of states, to a coherent one in which it can carry
efficiently any computations implementable on synchronous properly initialized
networks of the same size.
A useful data structure on such networks is a partial orientation of its
edges. It needs to be flat, i.e. have null holonomy (no excess of up or down
edges in any cycle). It also needs to be centered, i.e. have a unique node with
no down edges.
There are (interdependent) selfstabilizing asynchronous finite automata
protocols assuring flat centered orientation. Such protocols may vary in
assorted efficiency parameters and it is desirable to have each replaceable
with any alternative, responsible for a simple limited task. We describe an
efficient reduction of any computational task to any such set of protocols
compliant with our interface conditions.

This is a 1971 dissertation. Only its extended abstract was published at the
time. While some results appeared in other publications, a number of details
remained unpublished and may still have relevance.

We study the minimal complexity of tilings of a plane with a given tile set.
We note that every tile set admits either no tiling or some tiling with O(n)
Kolmogorov complexity of its nbyn squares. We construct tile sets for which
this bound is tight: all nbyn squares in all tilings have complexity at least
n. This adds a quantitative angle to classical results on nonrecursivity of
tilings  that we also develop in terms of Turing degrees of unsolvability.
Keywords: Tilings, Kolmogorov complexity, recursion theory

[Gacs, Kurdiumov, Levin, 78] proposed simple onedimensional cellular
automata with 2 states. In an infinite array they are selfstabilizing: if all
but a finite minority of automata are in the same state, the minority states
disappear. Implicit in the paper was a stronger result that a sufficiently
small minority of states vanish even in a finite circular array. The following
note makes this strengthening explicit.

Classical results on aperiodic tilings are rather complicated and not widely
understood. Below, an alternative approach is discussed in hope to provide
additional intuition not apparent in classical works.

Byzantine Agreement introduced in [Pease, Shostak, Lamport, 80] is a widely
used building block of reliable distributed protocols. It simulates broadcast
despite the presence of faulty parties within the network, traditionally using
only private unicast links. Under such conditions, Byzantine Agreement requires
more than 2/3 of the parties to be compliant. [Fitzi, Maurer, 00], constructed
a Byzantine Agreement protocol for any compliant majority based on an
additional primitive allowing transmission to any two parties simultaneously.
They proposed a problem of generalizing these results to wider channels and
fewer compliant parties. We prove that 2f < kh condition is necessary and
sufficient for implementing broadcast with h compliant and f faulty parties
using kcast channels.

The existence of oneway functions is arguably the most important problem in
computer theory. The article discusses and refines a number of concepts
relevant to this problem. For instance, it gives the first combinatorial
complete owf, i.e., a function which is oneway if any function is. There are
surprisingly many subtleties in basic definitions. Some of these subtleties are
discussed or hinted at in the literature and some are overlooked. Here, a
unified approach is attempted.