KOLMOGOROV COMPLEXITY

AS A HIDDEN FACTOR OF SCIENTIFIC DISCOURSE:

arXiv:1301.0081v1 [math.HO] 1 Jan 2013

FROM NEWTON’S LAW TO DATA MINING1

Yuri I. Manin
Max–Planck–Institut für Mathematik, Bonn, Germany,

Summary
The word ”complexity” is most often used as a meta–linguistic expression re-
ferring to certain intuitive characteristics of a natural system and/or its scientific
description. These characteristics may include: sheer amount of data that must be
taken into account; visible “chaotic” character of these data and/or space distribu-
tion/time evolution of a system etc.
This talk is centered around the precise mathematical notion of ”Kolmogorov
complexity”, originated in the early theoretical computer science and measuring
the degree to which an available information can be compressed.
In the first part, I will argue that a characteristic feature of basic scientific theo-
ries, from Ptolemy’s epicycles to the Standard Model of elementary particles, is their
splitting into two very distinct parts: the part of relatively small Kolmogorov com-
plexity (”laws”, ”basic equations”, ”periodic table”, ”natural selection, genotypes,
mutations”) and another part, of indefinitely large Kolmogorov complexity (”initial
and boundary conditions”, ”phenotypes”, “populations”). The data constituting
this latter part are obtained by planned observations, focussed experiments, and
afterwards collected in growing databases (formerly known as ”books”, ”tables”,
”encyclopaedias” etc). In this discussion Kolomogorov complexity plays a role of
the central metaphor.
The second part and Appendix 1 are dedicated to more precise definitions and
examples of complexity.
Finally, the last part briefly touches upon attempts to deal directly with Kol-
mogorov complex massifs of data and the “End of Science” prophecies.

1 Talkat the Plenary Session of the Pontifical Academy of Sciences on “Complexity and Analogy
in Science: Theoretical, Methodological and Epistemological Aspects” , Casina Pio IV, November
5–7, 2012.
1
2

1. Bi–partite structure of scientific theories

In this section, I will understand the notion of “compression of information”

intuitively and illustrate its pervasive character with several examples from the
history of science.
Planetary movements. Firstly, I will briefly remind the structure of several
models of planetary motions in the chronological order of their development.
After the discovery that among the stars observable by naked eye on a night sky
there exist several exceptional ”moving stars” (planets), there were proposed several
successful models of their movement that allowed predict the future positions of the
moving stars.
The simplest of them placed all fixed stars on one celestial sphere that rotated
around the earth in a way reflecting nightly and annual visible motions. The plan-
ets, according to Apollonius of Perga (3rd century B. C.), Hipparchus of Rhodes,
and Ptolemy of Alexandria (2nd century A. D.), were moving in a more compli-
cated way: along circular “epicyles” whose centers moved along another system of
circles, “eccentrics” around Earth. Data about radii of eccentrics and epicycles and
the speed of movements were extracted from observations of the visible movements,
and the whole model was then used in order to predict the future positions at any
given moment of observation.
As D. Park remarks ([Pa], p. 72), “[...] in the midst of all this empiricism sat the
ghost of Plato, legislating that the curves drawn must be circles and nothing else,
and that the planets and the various connectiong points must move along them
uniformly and in no other way.”
Since in reality observable movements of planets involved accelerations, backward
movements, etc., two circles in place of one for each planet at least temporarily saved
face of philosophy. Paradoxically, however, much later and much more developed
mathematics of modernity returned to the image of “epicycles”, that could since
then form an arbitrarily high hierarchy: the idea of Fourier series and, later, Fourier
integral transformation does exactly that!
It is well known, at least in general outline, how Copernicus replaced these
geocentric models by a heliocentric one, and how with the advent of Newton’s

m1 m2
gravity law F = G , dynamic law F = ma,
r2
 3

and the resulting solution of the “two–body problem”, planets “started moving”
along ellipsoidal orbits (with Sun as one focus rather than center). It is less well
known to the general public that this approximation as well is valid only insofar as
we can consider negligible the gravitational forces with which the planets interact
among themselves.
If we intend to obtain a more precise picture, we have to consider the system of
differential equations defining the set of curves parametrized by time t in the 6n–
dimensional phase space where n is the number of planets (including Sun) taken in
consideration:
n
d2 qi X mi mj ((qi − qj )
=
dt2 i=1
|qi − qj |3

Both Newton laws are encoded in this system.

The choice of one curve, corresponding to the evolution of our Solar system,
dqi
is made when we input initial conditions qi (0), (0) at certain moment of time
dt
t = 0; they are supplied, with a certain precision, by observations.
At this level, a new complication emerges. Generic solutions of this system of
equations, in the case of three and more bodies, cannot be expressed by any simple
formulas (unlike the equations themselves). Moreover, even qualitative behavior
of solutions depends in extremely sensitive way on the initial conditions: very
close initial positions/velocities may produce widely divergent trajectories. Thus,
the question whether our Solar system will persist for the next, say, 108 years
(even without disastrous external interventions) cannot be solved unless we know
its current parameters (masses of planets, positions of their centers of mass, and
speeds) with unachievable precision. This holds even without appealing to much
more precise Einstein’s description of gravity, or without taking in account comets,
asteroid belts and Moons of the Solar system (the secondary planets turning around
planets themselves).
It goes without saying that a similarly detailed description of, say, our Galaxy,
taking in account movements of all individual celestial bodies, constituting it, is
unachievable from the start, because of sheer amount of these bodies. Hence,
to understand its general space–time structure, we must first construct models
involving averaging on a very large scale. And of course, the model of space–time
itself, now involving Einstein’s equations, will describe an “averaged” space–time.
4

Information compression: first summary. In this brief summary of con-

secutive scientific models, one can already see the following persisting pattern: the
subdivision into a highly compressed part (“laws”) and potentionally indefinitely
complex part. The first part in our brief survey was represented by formulas that
literally became cultural symbols of Western civilization: Newton’s laws, that were
h
followed by Einstein’s E = mc2 and Heisenberg’s pq − qp = . The second part is
2πi
kinematically represented by “initial” or “boundary” conditions, and dynamically
by a potentially unstable character of dependence of the data we are interested in
from these initial/boundary conditions.
More precisely, a mathematical description of the “scene” upon which devel-
ops kinematics and dynamics in these models is also represented by highly com-
pressed mathematical images, only this time of geometric nature. Thus, the pos-
tulate that kinematics of a single massive point is represented by its position in an
ideal Euclidean space represents one of the ”laws” as well. To describe kinematics,
one should amplify this “configuration space” and replace it by the “phase space”
parametrizing positions and velocities, or, better, momenta. For one massive point
it is a space of dimension six: this is the answer of mathematics to Zeno’s “Achilles
and the Turtle” paradox. For a planet system consisting of n planets (including
Sun) the phase space has dimension 6n.
For Einstein’s equations of gravitation, the relevant picture is much more com-
plicated: it involves configuration and phase spaces that have infinite dimension,
and require quite a fair amount of mathematics for their exact description. Never-
theless, this part of our models is still clearly separated from the one that we refer
to as the part of infinite Kolmogorov complexity, because mathematics developed
a concise language for description of geometry.
One more lesson of our analysis is this: “laws” can be discovered and efficiently
used only if and when we restrict our attention to definite domains, space–time
scales, and kinds of matter and interactions. For example, there was no place for
chemistry in the pictures above.
From macroworld to microworld: the Standard Model of elementary
particles and interactions. From astronomy, we pass now to the deepest known
level of microworld: theory of elementary particles and their interactions.
I will say a few words about the so called Standard Model of the elementary
particles and their interactions, that took its initial form in the 1970’s as a theo-
 5

retical construction in the framework of the Quantum Field Theory. The Standard
Model got its first important experimental correlates with the discovery of quarks
(components of nuclear “elementary” particles) and W and Z bosons, quanta of
ineractions. For a very rich and complex history of this stage of theoretical physics,
stressing the role of experiments and experimenters, see the fascinating account [Zi]
by Antonio Zichichi. The Standard Model recently reappeared on the first pages
of the world press thanks to the renewed hopes that the last critically missing
component of the Model, the Higgs boson, has finally been observed.
Somewhat paradoxically, one can say that mathematics of the Standard Model
is firmly based on the same ancient archetypes of the human thought as that of
Hipparchus and Ptolemy: symmetry and uniform movement along circles.
More precisely, the basic idea of symmetry of modern classical (as opposed to
quantum) non–relativistic physics involves the symmetry group of rigid movements
of the three–dimensional Euclidean space, that is combinations of parallel shifts
and rotations around a point. The group of rotations is denoted SO(3), and ce-
lestial spheres are the unique objects invariant with respect to rotations. Passing
from Hipparchus and Ptolemy to modernity includes two decisive steps: adding
shifts (Earth, and then Sun, cease being centers of the Universe), and, crucially,
understanding the new meta–law of physics: symmetry must govern laws of physics
themselves rather than objects/processes etc that these laws are supposed to govern
(such as Solar System).
When we pass now to the quantum mechanics, and further to the Quantum Field
Theory (not involving gravitation), the group of SO(3) (together with shifts) should
be extended, in particular, by several copies of such groups as SU (2) and SU (3)
describing rotations in the internal degrees of freedom of elementary particles, such
as spin, colour etc. The basic ”law” that should be invariant with respect to this
big group, is encoded in the Lagrangian density: it is a “mathematical formula”
that is considerably longer than everything we get exposed to in our high school
and even college courses: cf. Appendix 2.
Finally, the Ptolemy celestial movements, superpositions of rotations of rigid
spheres, now transcends our space–time and happens in the infinite–dimensional
Hilbert space of wave–functions: this is the image describing, say, a hydrogen atom
in the paradigm of the first decades of the XXth century.

Information compression: second summary. I will use the examples above

in order to justify the following viewpoint.
6

Scientific laws (at least those that are expressed by mathematical constructions)
can be considered as programs for computation, whereas observations produce in-
puts to these programs.
Outputs of these computations serve first to check/establish a domain of applica-
bility of our theories. We compare the predicted behavior of a system with observed
one, we are happy when our predictions agree quantitatively and/or qualitatively
with observable behaviour, we fix the border signs signalling that at this point we
went too far.
Afterwards, the outputs are used for practical/theoretical purposes, e. g. in en-
gineering, weather predictions etc, but also to formulate the new challenges arising
before the scientific thinking.
This comparison of scientific laws with programs is, of course, only a metaphor,
but it will allow us to construct also a precise model of the kind of complexity,
inherently associated with this metaphor of science: Kolmogorov complexity.
The next section is dedicated to the sketch of this notion in the framework of
mathematics, again in its historical perspective.

2. Integers and their Kolmogorov complexity

Positional notations as programs. In this section, I will explain that the well
known to the general public decimal notations of natural numbers are themselves
programs.
What are they supposed to calculate?
Well, the actual numbers that are encoded by this notation, and are more ade-
quately represented by, say, rows of strokes:

7: |||||||, 13 : |||||||||||||, ... , 1984 : ||||...||||

Of course, in the last example it is unrealistic even to expect that if I type here 1984
strokes, an unsophisticated reader will be able to check that I am not mistaken.
There will be simply too much strokes to count, whereas the notation–program
“1984” contains only four signs chosen from the alphabet of ten signs. One can
save on the size of alphabet, passing to the binary notation, then “1984” will be re-
placed by a longer program “11111000000”. However, comparing the length of the
program with the “size” of the number, i. e. the respective number of strokes, we
see that decimal/binary notation gives an immense economy: the program length
 7

is approximately the logarithm of the number of strokes (in the base 10 or 2 re-
spectively).
More generally, we can speak about “size”, or “volume” of any finite text based
upon a fixed finite alphabet.
The discovery of this logarithmic upper bound of the Kolmogorov complexity of
numbers was a leap in the development of humanity on the scale of civilizations.
However, if one makes some slight additional conventions in the system of no-
tation, it will turn out that some integers admit a much shorter notation. For
10
example, let us allow ourselves to use the vertical dimension and write, e. g. 1010 .
The logarithm of the last number is about 1010 , much larger than the length of
the notation for which we used only 6 signs! And if we are unhappy about non–
linear notation, we may add to the basic alphabet two brackets (,) and postulate
10
that a(b) means ab . Then 1010 will be linearly written as 10(10(10)) using only
10 signs, still much less than 1010 + 1 decimal digits (of course, 1010 of them will
be just zeroes).
Then, perhaps, all integers can be produced by notation/programs that are much
shorter than logarithm of their size?
No! It turns out that absolute majority of numbers (or texts) cannot be signifi-
cantly compressed, although an infinity of integers can be written in a much shorter
way than it can be done in any chosen system of positional notation.
If we leave the domain of integers and leap, to, say, such a number as π =
3, 1415926..., it looks as if it had infinite complexity. However, this is not so. There
exists a program that can take as input the (variable) place of a decimal digit (an
integer) and give as output the respective digit. Such a program is itself a text
in a chosen algorithmic language, and as such, it also has a complexity: its own
Kolmogorov complexity. One agrees that this is the complexity of π.
A reader should be aware that I have left many subtle points of the definition
of Kolmogorov complexity in shadow, in particular, the fact that its dependence
of the chosen system of encoding and computation model can change it only by
a bounded quantity etc. A reader who would like to see some more mathematics
about this matter is referred to the brief Appendix 1 and the relevant references.
Here I will mention two other remarkable facts related to the Kolmogorov com-
plexity of numbers: one regarding its unexpected relation to the idea of randomness,
8

and another one showing that some psychological data make explicit the role of this
complexity in the cognitive activity of our mind.
Complexity and randomness. Consider arbitrarily long finite sequences of
zeroes and ones, say, starting with one so that each such sequence could be inter-
preted as a binary notation of an integer.
There is an intuitive notion of “randomness ” of such a sequence. In the con-
temporary technology “random” sequences of digits and similar random objects are
used for encoding information, in order to make it inaccessible for third parties. In
fact, a small distribured industry producing such random sequences (and, say, ran-
dom big primes) has been created. A standard way to produce random objects is
to leave mathematics and to recur to physics: from throwing a piece to registering
white noise.
One remarkable property of Kolmogorov complexity is this: those sequences
of digits whose Kolmogorov complexity is approximately the same as their length,
are random in any meaningful sense of the word. In particular, they cannot be
generated by a program essentialy shorter than the sequence itself.
Complexity and human mind. In the history of humanity, discovery of laws
of classical and quantum physics that represent incredible compression of com-
plex information, stresses the role of Kolmogorov complexity, at least as a relevant
metaphor for understanding the laws of cognition.
In his very informative book [De], Stanislas Dehaene considers certain exper-
imental results about the statistics of appearance numerals and other names of
numbers. cf. especially pp. 110 – 115, subsection “Why are some numerals more
frequent than others?”.
As mathematicians, let us consider the following abstract question: can one
say anything non-obvious about possible probabilities distributions on the set of
all natural numbers? More precisely, one such distribution
P is a sequence of non–
negative real numbers pn , n = 1, 2, . . . such that n pn = 1. Of course, from the
last formula it follows that pn must tend to zero, when n tends to infinity; moreover
pn cannot tend to zero too slowly: for example, pn = n−1 will not do. But two
different distributions can be widely incomparable.
Remarkably, it turns out that if we restrict our class of distributions only to
computable from below ones, that is, those in which pn can be computed as a function
of n (in a certain precise sense), then it turns out that there is a distinguished and
 9

small subclass C of such distributions, that are in a sense maximal ones. Any
member (pn ) of this class has the following unexpected property (see [Lev]):
the probability pn of the number n, up to a bounded (from above and below)
factor, equals the inverse of the exponentiated Kolmogorov complexity of n.
This statement needs additional qualifications: the most important one is that
we need here not the original Kolmogorov complexity but the so called prefix–free
version of it. We omit technical details, because they are not essential here. But
the following properties of any distribution (pn ) ∈ C are worth stressing in our
context:
(i) Most of the numbers n, those that are Kolmogorov ”maximally complex”,appear
with probability comparable with n−1 (log n)−1−ε , with a small ε: “most large num-
bers appear with frequency inverse to their size” (in fact, somewhat smaller one).
(ii) However, frequencies of those numbers that are Kolmogorov very simple,
such as 103 (thousand), 106 (million), 109 (billion), produce sharp local peaks in
the graph of (pn ).
The reader may compare these properties of the discussed class of distributons,
which can be called a priori distributions, with the observed frequencies of numerals
(number words) in printed and oral texts in various languages: cf. Dehaene, loc.
cit., p. 111, Figure 4.4. To me, their qualitative agreement looks very convincing:
brains and their societies do reproduce a priori probabilities.
Notice that those parts of the Dehaene and Mehler graphs in loc. cit. that refer
to large numbers, are somewhat misleading: they might create an impression that
frequencies of the numerals, say, between 106 and 109 smoothly interpolate between
those of 106 and 109 themselves, whereas in fact they abruptly drop down.
Finally, I want to stress that the class of a priori probability distributions that
we are considering here is qualitatively distinct from those that form now a common
stock of sociological and sometimes scientific analysis: cf. a beautiful synopsis by
Terence Tao in [Ta]. The appeal to the uncomputable degree of maximal compres-
sion is exactly what can make such a distribution an eye–opener. As I have written
at the end of [Ma2]:
“One can argue that all cognitive activity of our civilization, based upon symbolic
(in particular, mathematical) representations of reality, deals actually with the
initial Kolmogorov segments of potentially infinite linguistic constructions, always
replacing vast volumes of data by their compressed descriptions. This is especially
visible in the outputs of the modern genome projects.
10

In this sense, such linguistic cognitive activity can be metaphorically compared

to a gigantic precomputation process, shellsorting infinite worlds of expressions in
their Kolmogorov order.”

3. New cognitive toolkits: WWW and databases

“The End of Theory”. In summer 2008, an issue of the “Wired Magazine”

appeared. It’s cover story ran: “The End of Theory: The Data Deluge Makes the
Scientific Method Obsolete”.

The message of this essay, written by the Editor–in–Chief Chris Anderson, was
summarized in the following words:
“The new availablility of huge amounts of data, along with statistical tools to
crunch these numbers, offers a whole new way of understanding the world. Corre-
lation supersedes causation, and science can advance even without coherent models,
unified theories, or really any mechanical explanation at all. There’s no reason to
cling to our old ways. It’s time to ask: What can science learn from Google?”

I will return to this rhetoric question at the end of this talk. Right now I want
only to stress that, as well as in the scientific models of the “bygone days”, basic
theory is unavoidable in this brave new Petabyte World: encoding and decoding
data, search algorithms, and of course, computers themselves are just engineering
embodiment of some very basic and very abstract notions of mathematics. The
mathematical idea underlying the structure of modern computers is the Turing
machine (or one of several other equivalent formulations of the concepts of com-
putability). We know that the universal Turing machine has a very small Kol-
mogorov complexity, and therefore, using the basic metaphor of this talk, we can
say that the bipartite structure of the classical scientific theories is reproduced at
this historical stage.
Moreover, what Chris Anderson calls “the new availability of huge amounts of
data” by itself is not very new: after spreading of printing, astronomic observa-
tories, scientific laboratories, and statistical studies, the amount of data available
to any visitor of a big public library was always huge, and studies of correlations
proliferated for at least the last two centuries.
Charles Darwin himself collected the database of his observations, and the result
of his pondering over it was the theory of evolution.
 11

A representative recent example is the book [FlFoHaSCH], sensibly reviewed in

[Gr].
Even if the sheer volume of data has by now grown by several orders of magni-
tude, this is not the gist of Anderson’s rhetoric.
What Anderson actually wants to say is that human beings are now – happily!
– free from thinking over these data. Allegedly, computers will take this burden
upon themselves, and will provide us with correlations – replacing the old–fashioned
“causations” (that I prefer to call scientific laws) – and expert guidance.
Leaving aside such questions as how “correlations” might possibly help us un-
derstand the structure of Universe or predict the Higgs boson, I would like to quote
the precautionary tale from [Gr]:
“[...] in 2000 Peter C. Austin, a medical statistician at the University of Toronto,
and his colleagues conducted a study of all 10,674,945 residents of Ontario aged be-
tween eighteen and one hundred. Residents were randomly assigned to different
groups, in which they were classified according to their astrological signs. The re-
search team then searched through more than two hundred of the most common
diagnoses of hospitalization until they identified two where patients under one as-
trological sign had a significantly higher probability of hospitalization compared to
those born under the remaining signs combined: Leos had a higher probability of
gastrointestinal hemorrage while Sagittarians had a higher probability of fracture of
the upper arm compared to all other signs combined.
It is thus relatively easy to generate statistically significant but spurious correla-
tions when examining a very large data set and a similarly large number of potential
variables. Of course, there is no biological mechanism whereby Leos might be pre-
disposed to intestinal bleeding or Sagittarians to bone fracture, but Austin notes, ‘It
is tempting to construct biologically plausible reasons for observed subgroup effects
after having observed them.’ Such an exercise is termed ‘data mining’, and Austin
warns, ‘Our study therefore serves as a cautionary note regarding the interpretation
of findings generated by data mining’ [...]”

Coda
What can science learn from Google:
“Think! Otherwise no Google will help you.”
12

References
[An] Ch. Anderson. The End of Theory. in: Wired, 17.06, 2008.
[ChCoMa] A. H. Chamseddine, A. Connes, M. Marcolli. Gravity and the stan-
dard model with neutrino mixing. Adv.Theor.Math.Phys. 11 (2007), 991-1089.
arXiv:hep-th/0610241
[De] S. Dehaene. The Number Sense. How the Mind creates Mathematics. Ox-
ford UP, 1997.
[FlFoHaSCH] R. Floud, R. W. Fogel, B. Harris, Sok Chul Hong. The Changing
Body: Health, Nutrition and Human Development in the Western World Since
1700. Cambridge UP, 431 pp.
[Gr] J. Groopman. The Body and the Human Progress. In: NYRB, Oct. 27,
2011
[Lev] L. A. Levin, Various measures of complexity for finite objects (axiomatic
description), Soviet Math. Dokl. Vol.17 (1976) N. 2, 522–526.
[Ma1] Yu. Manin. A Course of Mathematical Logic for Mathematicians. 2nd
Edition, with new Chapters written by Yu. Manin and B. Zilber. Springer, 2010.
[Ma2] Yu. Manin. Renormalization and Computation II: Time Cut-off and the
Halting Problem. In: Math. Struct. in Comp. Science, pp. 1–23, 2012, Cambridge
UP. Preprint math.QA/0908.3430
[Pa] D. Park. The How and the Why. An Essay on the Origins and Development
of Physical Theory. Princeton UP, 1988.
[Ta] T. Tao. E pluribus unum: From Complexity, Universality. Daedalus, Journ.
of the AAAS, Summer 2012, 23–34.
[Zi] A. Zichichi. Subnuclear Physics. The first 50 years: Highlights from Erice
to ELN. World Scientific, 1999.
 13

APPENDIX 1. A brief guide to computability

This appendix contains a sketch of the mathematical computability theory, or
theory of algorithmic computations, as it was born in the first half the XXth cen-
tury in the work of such thinkers as Alonso Church, Alan Turing and Andrei Kol-
mogorov. We are not concerned here with its applied aspects studied under the
general heading of “Computer Science”.
This theory taught us two striking lessons.
First, that there is a unique universal notion of computability in the sense that
all seemingly very different versions of it turned out to be equivalent. We will sketch
here the form that is called the theory of (partial) recursive functions.
Second, that this theory sets its own limits and unavoidably leads to confronta-
tion with uncomputable problems.
Both discoveries led to very interesting research aiming to the extension of this
territory of classical computability such as basics of theory of quantum computing
etc. But we are not concerned with this development here.
Three descriptions of partial recursive functions. The subject of the
theory of recursive functions is a set of functions whose domain and values are
vectors of natural numbers of arbitrary fixed lengths: f : Zm n
+ → Z+ .
An important qualification: a “function”, say, f : X → Y , below always means
a pair (f, D(f )), where D(f ) ⊂ X and f is a map of sets D(f ) → Y . The definition
domain D(f ) is not always mentioned explicitly. If D(f ) = X, the function might
be called “total”; generally it may be called “partial” one.
(i) Intuitive description. A function f : Zm n
+ → Z+ is called (partial) recursive
iff it is “semi–computable” in the following sense:
there exists an algorithm F accepting as inputs vectors x = (x1 , . . . , xm ) ∈ Zm
+.
with the following properties:
– if x ∈ D(f ), F produces as output f (x).
– if x ∈
/ D(f ), F either produces answer “NO”, or works indefinitely long without
producing any output.
(ii) Formal description (sketch). It starts with two lists:
– An explicit list of “obviously” semi–computable basic functions such as con-
stant functions, projections onto i–th coordinate etc.
14

– An explicit list of elementary operations, such as an inductive definition, that

can be applied to several semi–computable functions and “obviously” produces from
them a new semi–computable function.
The key elementary operation involves finding the least root of equation f (x) = y
(if it exists) where f is already defined function. It is this operation that involves
search and makes introduction of partial functions inevitable.
– After that, the set of partial recursive functions is defined as the minimal set
of functions containing all basic functions and closed wrt all elementary operations.
(iii) Diophantine description (A DIFFICULT THEOREM). A function f :
Zm
+ → Zn+ is partial recursive iff there is a polynomial

P (x1 , . . . , xm ; y1 , . . . , yn ; t1 , . . . , tq ) ∈ Z[x, y, t]

such that the graph

Γf := {(x, f (x))} ⊂ Zm n
+ × Z+
q
is the projection of the subset P = 0 in Zm n
+ × Z+ × Z+ .

Constructive worlds. An (infinite) constructive world is a countable set X

(usually of some finite Bourbaki structures) given together with a class of structural
numberings: intuitively computable bijections ν : Z+ → X which form a principal
homogeneous space over the group of recursive permutations of Z+ . An element
x ∈ X is called a constructive object.
Example: X = all finite words in a fixed finite alphabet A.

Church’s thesis: Let X, Y be two constructive worlds, νX : Z+ → X, νY :

Z+ → Y their structural numberings, and F an (intuitive) algorithm that takes as
input an object x ∈ X and produces an object F (x) ∈ Y whenever x lies in the
domain of definition of F .
Then f := νY−1 ◦ F ◦ νX : Z+ → Z+ is a partial recursive function.
The status of Church’s thesis in mathematics is very unusual. It is not a theorem,
since it involves an undefined notion of “intuitive computability”. It expresses the
fact that several developed mathematical constructions whose explicit goal was to
formalize this notion, led to provably equivalent results. But moreover, it expresses
the belief that any new such attempt will inevitably produce again an equivalent
notion. Briefly, Church’s thesis is “an experimental fact in the mental world”.
 15

Exponential Kolmogorov complexity of constructive objects. Let X

be a constructive world. For any (semi)–computable function u : Z+ → X, the
(exponential) complexity of an object x ∈ X relative to u is

Ku (x) := min {m ∈ Z+ | u(m) = x}.

If such m does not exist, we put Ku (x) = ∞.

Claim: there exists such u (“an optimal Kolmogorov numbering”, or “decom-
pressor”) that for each other v, some constant cu,v > 0, and all x ∈ X,

Ku (x) ≤ cu,v Kv (x).

This Ku (x) is called exponential Kolmogorov complexity of x.

A Kolmogorov order on a constructive world X is a bijection K = Ku : X → Z+
arranging elements of X in the increasing order of their complexities Ku .
The reader must keep in mind two warnings related to these notions:
– Any optimal numbering is only partial function, and its definition domain is
not decidable.
– Kolmogorov complexity Ku itself is not computable. It is the lower bound of a
sequence of computable functions. Kolmogorov order is not computable as well.
– Kolmogorov order of Z+ cardinally differs from the natural order in the follow-
ing sense: it puts in the initial segments very large numbers that are at the same
time Kolmogorov simple.
.n
..
Example: let an := nn (n times).
Then Ku (an ) ≤ cn for some c > 0 and all n > 0.
Kolmogorov complexity of recursive functions. When we spoke about
“complexity of π”, we had in mind a program that, given an input n ∈ Z+ , calcu-
lates the n–th decimal digit of π. Such a program calculates therefore a recursive
function. However, the set of all recursive functions f : Zm n
+ → Z+ do not form a
constructive world, if m > 0!
Nevertheless, one can speak about a Kolmogorov optimal enumeration of pro-
grams, computing functions of this set, and thus about Kolmogorov complexity
16

of such functions themselves. This is critically important for applicability of our

“complexity metaphor” in the domain of scientific knowledge. In fact, both ”laws”
and descriptions of “phase spaces” that make the scene for these laws belong rather
to domains of intuitively computable functions than to the domain of constructive
objects.
Mathematical details of constructions, underlying brief explanations collected in
this Appendix can be found in [Ma1], Chapter II.
 17

APPENDIX 2. Lagrangian of the Standard Model

Source: [ChCoMa]
“In flat space and in Lorentzian signature the Lagrangian of the standard model
with neutrino mixing and Majorana mass terms, written using the Feynman gauge
fixing, is of the form

LSM =
1 1
− ∂ν gµa ∂ν gµa −gs f abc ∂µ gνa gµb gνc − gs2 f abc f ade gµb gνc gµd gνe −∂ν Wµ+ ∂ν Wµ− −M 2 Wµ+ Wµ− −
2 4
1 1 1
∂ν Zµ0 ∂ν Zµ0 − 2 M 2 Zµ0 Zµ0 − ∂µ Aν ∂µ Aν −igcw (∂ν Zµ0 (Wµ+ Wν− −−Wν+ Wµ− )−Zν0 (Wµ+ ∂ν Wµ− −
2 2cw 2
Wµ− ∂ν Wµ+ )+Zµ0 (Wν+ ∂ν Wµ− −Wν− ∂ν Wµ+ ))−igsw (∂ν Aµ (Wµ+ Wν− −Wν+ Wµ− )−Aν (Wµ+ ∂ν Wµ− −
1 1
Wµ− ∂ν Wµ+ )+Aµ (Wν+ ∂ν Wµ− −Wν− ∂ν Wµ+ ))− g 2 Wµ+ Wµ− Wν+ Wν− + g 2 Wµ+ Wν− Wµ+ Wν− +
2 2
g 2 c2w (Zµ0 Wµ+ Zν0 Wν− −Zµ0 Zµ0 Wν+ Wν− )+g 2 s2w (Aµ Wµ+ Aν Wν− −Aµ Aµ Wν+ Wν− )+g 2 sw cw (Aµ Zν0 (Wµ+ Wν−
1 1
Wν+ Wµ− ) − 2Aµ Zµ0 Wν+ Wν− ) − ∂µ H∂µ H − 2M 2 αh H 2 − ∂µ φ+ ∂µ φ− − ∂µ φ0 ∂µ φ0 −
2 2
2M 2 2M 4
 
2M 1 2 0 0 + − 3 0 0 + −


βh + H + (H + φ φ + 2φ φ ) + α h −gα h M H + Hφ φ + 2Hφ φ −
g2 g 2 g2
1 2
g αh H 4 + (φ0 )4 + 4(φ+ φ− )2 + 4(φ0 )2 φ+ φ− + 4H 2 φ+ φ− + 2(φ0 )2 H 2 −gM Wµ+ Wµ− H−


8
1 M 0 0 1
g 2 Zµ Zµ H − ig Wµ+ (φ0 ∂µ φ− − φ− ∂µ φ0 ) − Wµ− (φ0 ∂µ φ+ − φ+ ∂µ φ0 ) +


2 cw 2
1
1 1
g Wµ+ (H∂µ φ− − φ− ∂µ H) + Wµ− (H∂µ φ+ − φ+ ∂µ H) + g (Zµ0 (H∂µ φ0 −φ0 ∂µ H)+
2 2 cw
1 0 s2
M( Zµ ∂µ φ0 +Wµ+ ∂µ φ− +Wµ− ∂µ φ+ )−ig w M Zµ0 (Wµ+ φ− −Wµ− φ+ )+igsw M Aµ (Wµ+ φ− −Wµ− φ+ )−
cw cw
1 − 2c2w 0 + 1
ig Zµ (φ ∂µ φ− −φ− ∂µ φ+ )+igsw Aµ (φ+ ∂µ φ− −φ− ∂µ φ+ )− g 2 Wµ+ Wµ− H 2 + (φ0 )2 + 2φ+ φ−
2cw 4
18

1 2 1 0 0
1 s2
g 2 Zµ Zµ H 2 + (φ0 )2 + 2(2s2w − 1)2 φ+ φ− − g 2 w Zµ0 φ0 (Wµ+ φ− + Wµ− φ+ )
8 cw 2 cw
1 s2 1 1
− ig 2 w Zµ0 H(Wµ+ φ− −Wµ− φ+ )+ g 2 sw Aµ φ0 (Wµ+ φ− +Wµ− φ+ )+ ig 2 sw Aµ H(Wµ+ φ− −Wµ− φ+ )−
2 cw 2 2
sw 1
g2 (2c2w −1)Zµ0 Aµ φ+ φ− −g 2 s2w Aµ Aµ φ+ φ− + igs λaij (q̄iσ γ µ qjσ )gµa −ēλ (γ∂+mλe )eλ −ν̄ λ (γ∂+
cw 2
 
λ λ λ λ λ ¯λ λ λ λ µ λ 2 λ µ λ 1 ¯λ µ λ
mν )ν −ūj (γ∂+mu )uj −dj (γ∂+md )dj +igsw Aµ −(ē γ e ) + (ūj γ uj ) − (dj γ dj ) +
3 3
ig 0 4 8
Zµ {(ν̄ λ γ µ (1+γ 5 )ν λ )+(ēλ γ µ (4s2w −1−γ 5 )eλ )+(d¯λj γ µ ( s2w −1−γ 5 )dλj )+(ūλj γ µ (1− s2w +γ 5 )uλj )}
4cw 3 3
ig 
lep κ

+ √ Wµ+ (ν̄ λ γ µ (1 + γ 5 )Uλκ e ) + (ūλj γ µ (1 + γ 5 )Cλκ dκj )
2 2
ig  
+ √ Wµ− (ēκ Uκλ γ (1 + γ 5 )ν λ ) + (d¯κj Cκλ
lep† µ †
γ µ (1 + γ 5 )uλj ) +
2 2
ig 
lep lep

+ √ φ+ −mκe (ν̄ λ Uλκ (1 − γ 5 )eκ ) + mλν (ν̄ λ Uλκ (1 + γ 5 )eκ +
2M 2
ig   g mλ g mλe
lep† lep† ν
+ √ φ− mλe (ēλ Uλκ (1 + γ 5 )ν κ ) − mκν (ēλ Uλκ (1 − γ 5 )ν κ − H(ν̄ λ ν λ )− H(ēλ eλ )+
2M 2 2 M 2 M
ig mλν 0 λ 5 λ ig mλe 0 λ 5 λ 1 R 1 R
φ (ν̄ γ ν )− φ (ē γ e )− ν̄λ Mλκ (1−γ5 )ν̂κ − ν̄λ Mλκ (1 − γ5 )ν̂κ +
2 M 2 M 4 4
ig
√ φ+ −mκd (ūλj Cλκ (1 − γ 5 )dκj ) + mλu (ūλj Cλκ (1 + γ 5 )dκj +


2M 2
ig   g mλ g mλd
λ ¯λ † κ ¯λ †
− 5 κ
√ φ md (dj Cλκ (1 + γ )uj ) − mu (dj Cλκ (1 − γ )uj − 5 κ u
H(ūλj uλj )− H(d¯λj dλj )+
2M 2 2 M 2 M
ig mλu 0 λ 5 λ ig mλd 0 ¯λ 5 λ
φ (ūj γ uj ) − φ ( dj γ dj )
2 M 2 M

Here the notation is as follows:

• Gauge bosons: Aµ , Wµ± , Zµ0 , gµa
 19

• Quarks: uκj , dκj , collective : qjσ

• Leptons: eλ , ν λ
• Higgs fields: H, φ0 , φ+ , φ−
• Ghosts: Ga , X 0 , X +, X − , Y ,
• Masses: mλd , mλu , mλe , mh , M (the latter is the mass of the W )
√ m2h
• Coupling constants g = 4πα (fine structure), gs = strong, αh = 4M 2
• Tadpole Constant βh
• Cosine and sine of the weak mixing angle cw , sw
• Cabibbo–Kobayashi–Maskawa mixing matrix: Cλκ
• Cabibbo-Kobayashi-Maskawa matrix
• Structure constants of SU (3): f abc
• The Gauge is the Feynman gauge.”