Turing as a Biologist

G J Chaitin, Federal University of Rio de Janeiro

Mexico City, 26 June 2012
Berlin, 13 September 2012
Urbino, 27 September 2012

Paradigm Shifts

• Newton
• Darwin
• Maxwell
• Turing!

• Computer Technology, Hardware/Software, Universal Machines
• Most things in math are uncomputable!
• Physics: Is the world a computer?
• Artificial Intelligence: Is thinking a computation?
• DNA = Software [John von Neumann (1948)]

Conceptual Complexity

Turing (1936)   +   Shannon (1948)
computation         information

→

algorithmic information
[Solomonoff, Kolmogorov, Chaitin (1960's)]

This gives us a handle on the deep notion of conceptual
complexity which is fundamental in epistemology!
[In contrast, time complexity = engineering!]

This Notion of Conceptual Complexity is Vital
in Software Models of Physics, Math, Biology

• Complexity of physical theory [Leibniz (1686)]
  (Calculates experimental data using equations and initial conditions)
  Best theory = Simplest theory
  [Practical applications in machine intelligence, Bayesian statistics, data mining (Solomonoff)]

• Complexity of formal axiomatic theory
  (Calculates the theorems from the axioms using symbolic logic [David Hilbert / Emil Post])
  You can't prove you have the best theory → new version of Gödel incompleteness

• Complexity of algorithmic mutation
  (Calculates new organism from old organism)
  [Organisms are also software, but we are not concerned
  with their conceptual complexity]
  Used to model Darwinian evolution mathematically

What is a Mutation?

$A' = M(A)$

$M$ = algorithmic mutation
$A$ = original organism
$A'$ = mutated organism

If $M$ is a $K$-bit program, then probability of $M = 2^{-K}$.
If the conceptual complexity of $M$ is $K$ bits, then the probability of $M = 2^{-K}$.

Example:
The global change that consists of inverting each bit of a program
is a very simple and therefore a highly probable mutation!

Evolution = Hill-Climbing Random Walk in Software Space

• Single Software Organism!

• Life = Evolving Software

• Evolution of Mutating Software

• Programming without a Programmer!

• Increasing Fitness

• Fitness = Size of Number Calculated by Organism

• Bigger Number → Fitter Organism

Mutation Distance

• Mutation distance = $H(A' | A)$

• = relative information content of $A'$ given $A$

• = number of bits of algorithmic information needed to transform $A$ into $A'$

• = conceptual complexity of the mapping from $A$ to $A'$

• = $-\log_2$ of the probability that a random mutation carries $A$ into $A'$

Proving Darwin: Making Biology Mathematical

• Published in hardcover by Pantheon, May 2012

• To be published in softcover by Vintage, February 2013

• Forthcoming in Spanish, Italian and Japanese

  

Imagining a Brain!

• Deep remark in von Neumann, The Computer and the Brain, 1958, that in computers
  the technology used for memory and for logic is always different, so maybe the same is true in the brain.

• Is the Brain a Two-Level System?
  • Conscious, Rational, Serial, Sensual Front-End Mind: Slow Neurons
  • Unconscious, Intuitive, Parallel, Combinatorial Back-End Mind: Molecular Biology
    (much greater compute and memory capacity, e.g. photographic memory)
  After all, the immune system does information processing at the molecular level.

• How often does one work fruitlessly on a problem for hours then wake up the next morning with lots of new ideas:
  the intuitive mind has much, much greater information processing capacity than the rational mind.
  Indeed, it seems capable of exponential search.

• [Can connect the two levels postulated here by having a unique molecular "name" correspond to each neuron,
  for example to the proverbial "grandmother" cell.]

The Mystery of Consciousness

• I once fell asleep at the wheel while driving, then woke up and wondered
  where I was and "who" had continued driving while my conscious mind was asleep.
  Fortunately someone had continued driving!

• According to Christof Koch's book Consciousness, the level of my brain that continued driving was also conscious.
  Similarly, Koch believes the immune system must also be conscious; this is called panpsychism.

• According to Giulio Tononi's book PHI, consciousness can be measured in terms of the integrated information $\Phi$.
  [Tononi's $\Phi$ is also discussed in Koch's book.] The greater a system's $\Phi$ is, the more integrated and conscious it is.
  A binary switch has one bit of consciousness.

• I suspect $\Phi$ has something to do with what in algorithmic information theory is called mutual information
  $\;\;\;\;\;\;\;\;H(X : Y) = H(X) + H(Y) - H(X, Y)$
  which is the extent to which $X$ and $Y$ are simpler when seen together than when seen separately.

• [In a 1979 paper "Toward a Mathematical Definition of 'Life'" I discuss using the mutual information
  of the parts of a system to define the degree to which the parts are integrated into a whole.]

Summary

• We have used the program size $H(T)$ to measure the conceptual complexity of
  a physical or a mathematical theory $T$. The fact that you can never prove that you have
  the simplest physical theory yields a new version of Gödel's theorem on the limitations of
  formal axiomatic mathematical theories.

• In modeling Darwinian evolution, we have used relative program size $H(A' | A)$ to measure
  the conceptual complexity of an $A \rightarrow A'$ mutation. We can prove that our model evolves.
  We have a Pythagorean world in which life provably evolves.

• What about the brain and consciousness?! Following von Neumann, maybe
  a computer engineering approach is relevant. And following Tononi and Koch, maybe
  mutual program size complexity $H(X : Y)$ is related to integrated information as measured by $\Phi$.