This work is licensed under a
Creative Commons License.
|
Friday, October 04, 2002
Chaitin's Omega - The Halting ProbabilityChaitin'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) halts2-|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
lims→∞ Ω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 LU be the set of pairs (<M>,x) such that machine M accepts input x. LU 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 LD be the set of <M> such that machine M does not accept <M>. Suppose LD is computably enumerable. There must be some machine N such that N(<M>) accepts if and only if <M> is in LD. We have two cases
This kind of argument is called diagonalization. It is the main technique to show that problems cannot be computed.
- N(<N>) accepts: <N> is in LD so by definition of LD, N does not accept <N>, a contradiction.
- N(<N>) does not accept: <N> is not in LD so by definition of LD, N accepts <N>, a contradiction.
Step back for a second. We have shown that the language LD cannot be computed by a computer. Any computer. Ever.
4:10 PM # Comments []
Tuesday, October 01, 2002
SIGACT NewsLane 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 ComplexityMy 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
ict(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, icq(x:A)≤ c. To prove P ≠ NP one only needs to that icq(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 []