### Friday, October 04, 2002

**Chaitin's Omega - The Halting Probability**

Chaitin's Omega is the most compact way possible to encode the halting
problem. Fix a prefix-free universal Turing machine U, that is if U(p)
and U(q) both halt then p is not a prefix of q and vice versa. We
define Chaitin's Omega by
Ω = Σ_{p:U(p) halts}2^{-|p|}.
By Kraft's
Inequality, Ω ≤ 1. Since U halts on some p but not others
we have 0 < Ω < 1. Sometimes Ω is called the
*halting probability* because it is the probability of halting if
we run U at the start of an infinitely long randomly chosen string.
One can determine whether U(p) halts from only the first |p| bits of
Ω. Let n=|p| and Ω_{n} be Ω truncated to the
first n bits. We have Ω_{n} < Ω <
Ω_{n}+2^{-n}. Define Ω^{s} as the
same as the definition of Ω as above except then we only sum
over the p of length at most s such that U(p) halts in s steps. Note
we have

lim_{s→∞ }Ω^{s} = Ω.
and Ω^{s} is computable from s. So we find the smallest
s ≥ n such that Ω^{s} > Ω_{n}. Note
that U(p) halts if and only if it halts in s steps, otherwise Ω
≥ Ω^{s}+2^{-n} >
Ω_{n}+2^{-n} a contradiction.
Consider Ω^{A}, which has the same definition as Ω
but U now has access to an oracle for A. Rod Downey asks whether this
is well defined in terms of being machine independent? Is it degree
invariant, that is if A and B have the same Turing degree does
Ω^{A} have the same degree as Ω^{B}?

If the answer is yes, then, according to Rod, it is a solution to a
very long standing question of Martin. Note you cannot necessarily
compute even A from Ω^{A}.

9:24 AM
#
Comments
[]

### Wednesday, October 02, 2002

**Foundations of Complexity**

Lesson 3: Universal Turing Machines and Diagonalization

Previous Lesson
| Next Lesson
A *Universal Turing Machine* is a machine so powerful that it can
simulate any other Turing machine. Initially it seems amazing that
such a machine can exist. But think about the microprocessor that sits
on the computer you are now using. Every program that you use, your
word processor, the spreadsheet, the browser, the mp3 player all use
code that runs on this processor. This processor acts like a universal
Turing machine. Another example, is an interpreter for a language like
Java. Suppose we had a program written in C++. The Java interpreter
can run code that lets it interprets C++ and thus run any C++
program. This works for any other language and thus a Java interpreter
is also a universal Turing machine.

What we have done is to consider programs as data themselves. Fix a
programming language. For a
machine M let <M> be the binary encoding of the program describing M.
Let L_{U} be the set of pairs (<M>,x)
such that machine M accepts input x. L_{U} is a computably
enumerable set as we can create a machine U that simulates M on input
x. The machine U is a universal Turing machine.

We now show that there is a language that is not computably
enumerable. Let L_{D} be the set of <M> such that
machine M
does not accept <M>. Suppose L_{D} is computably
enumerable. There must be some machine N such that N(<M>)
accepts if and only if <M> is in L_{D}. We have two
cases

- N(<N>) accepts: <N> is in L
_{D} so by
definition of L_{D}, N does not accept <N>, a contradiction.
- N(<N>) does not accept: <N> is not in L
_{D} so by
definition of L_{D}, N accepts <N>, a contradiction.

This kind of argument is called *diagonalization*. It is the main
technique to show that problems cannot be computed.
Step back for a second. We have shown that the language L_{D}
cannot be computed by a computer. Any computer. Ever.

4:10 PM
#
Comments
[]

### Tuesday, October 01, 2002

**SIGACT News**

Lane Hemaspaandra's Complexity Column in the September SIGACT News has an interesting article by Marcus Schaefer and Chris Umans on problems complete in higher levels of the polynomial-time hierarchy. Also of interest for complexity theorists, Bill Gasarch's Book Review Column has a joint review of Computability and Complexity Theory by Homer and Selman and The Complexity Theory Companion by Hemaspaandra and Ogihara.
4:41 PM
#
Comments
[]

### Monday, September 30, 2002

**A Reader's Question about Kolmogorov Complexity**

My first question from a reader:
I'm interested in Kolmogorov complexity and its
relationship to traditional computational complexity
theory. It seems that
NP-complete problems all have a pretty low
Kolmogorov complexity, so in
this sense it seems KC will not serve as a good
measure for problem
instance hardness. I would like to know what you
would say on this topic
sometime in the future.

Andrei Nikolaevich Kolmogorov was born on April 25, 1903 and in 2003
there will be several events to mark the 100th anniversary of his
birth. I plan to devote several posts next year to mark these events
and discuss Kolmogorov complexity. If you cannot wait, I recommend the
great textbook on the topic,
An
Introduction to Kolmogorov Complexity and Its Applications by Ming
Li and Paul Vitányi.
As to the reader's question, initial segments of any computable set,
including the NP-complete sets, have low Kolmogorov complexity and are
not much use to measure the computational complexity of that
set. However, one can use time-bounded Kolmogorov complexity to capture
computational complexity.

Let p be a t-good program for a set A if for all inputs x, p(x) uses t(|x|) time and
says "Yes", "No" or "I don't know". If p(x) says Yes then x is in A
and if p(x) says "No" then x is not in A.

We define the t-time-bounded instance complexity of an instance x of a set A as

ic^{t}(x:A) = min{|p| : p is a t-good program for A and p(x)
≠ "I don't know"}
We have that A is in P if and only if there is a constant c and a
polynomial q such that for all x, ic^{q}(x:A)≤ c. To prove
P ≠ NP one only *needs* to that ic^{q}(x:SAT) is
unbounded for all polynomials q.

For more information about instance complexity see Section 7.4 of Li
and Vitányi.

4:49 PM
#
Comments
[]

The New York Times has finally taken notice that there has been a surprisingly number of plays, movies and now an opera about science.
2:21 PM
#
Comments
[]