This work is licensed under a
Creative Commons License.
|
Friday, May 16, 2003
Turing Machines and Godel's TheoremsA little recursion theory can make Gödel's Theorems intuitively easy.
Let A be the set of <M> such that M does not accept the input <M>. By diagonalization techniques we can show A is not recursively enumerable.
Now let us fix a logical theory like ZFC set theory. The actual theory does not matter much. Let B be the set of <M> such that there is a proof in ZFC of the statement "M does not accept input <M>." B is recursively enumerable since we can just try all possible proofs.
Now B is clearly a subset of A so there must be an input <M> in A-B. For this <M>, we have that M does not accept input <M> but there is no proof of this fact. We now have a true mathematical statement with no proof. This is Gödel's first theorem.
We can be more constructive. Since B is recursively enumerable there is some Turing machine N that computes B. Suppose that N accepts <N>. This means <N> is in B which implies there is a proof that <N> does not accept N, a contradiction.
So <N> cannot accept N which means <N> is not in B. So we have now constructed an N such that the statement "N does not accept <N>" is true but not provable.
But wait a minute, didn't I just give a proof that N does not accept <N>? Actually I had to make the assumption that ZFC is consistent. If ZFC is inconsistent then every statement (true or false) is provable so B would not be a subset of A and my whole argument falls apart.
If ZFC could prove that ZFC is consistent then I would not have to make any assumption and would have a contradiction. Thus ZFC cannot prove its own consistency. This is Gödel's second theorem.
Logicians tell me I'm cheating: I had to assume something technically stronger than consistency for this argument to work. Still these proofs illustrate the amazing power of Turing machines to make Gödel's theorems easier to understand.
3:57 PM # Comments []
Wednesday, May 14, 2003
Foundations of Complexity
Lesson 18: Savitch's TheoremPrevious Lesson | Next Lesson
Unlike what we believe for time, there is a polynomial relation between deterministic and nondeterministic space.
Savitch's Theorem (1970): NSPACE(s(n)) is contained in DSPACE(s2(n))
Proof: Recall the definition of tableau (as described in Lesson 12). Let N be a nondeterministic machine that uses s(n) space. We can represent the computation of an input x of length n by a tableau where each configuration has size O(s(n)) and there are at most m = cs(n) configurations for some constant c.
We will create a deterministic machine M(x) to determine whether the tableau is proper and thus N(x) accepts. First we need a subroutine CHECK to determine whether one configuration can reach another in 2t steps. We do not have enough space to write the entire tableau but instead we do a divide and conquer approach: Try all possible middle configurations and recurse on each half.
CHECK(CONF1,CONF2,t) \* Output TRUE if CONF1 can get to CONF2 in at most 2t steps *\ If t=0 then {if (CONF1 = CONF2 or CONF1 goes to CONF2 in one step on machine N) then output TRUE else output FALSE} For each CONF {If CHECK(CONF1,CONF,t-1) and CHECK(CONF,CONF2,t-1) then output TRUE} Output FALSEWe can implement CHECK by only having to store a constant number of configurations at each level of the recursion with a recursive depth of t for a total space of O(ts(n)).
Let CONF0 be the initial configuration encoding x. We can now give our main routine.
MAIN Let r be the smallest integer at least log2(cs(n)) For each CONF in an accepting state {If CHECK(CONF0,CONF,r) then output TRUE} Output FALSETotal space used: O(log2(cs(n))s(n)) = O(s2(n)).
3:30 PM # Comments []
Monday, May 12, 2003
The Nerd ShotMany years ago I was commuting home on the train with my wife and one of her colleagues. I showed them the group picture from a Dagstuhl I had attended that they recently sent me. My wife and her friend spent much of the train ride laughing at the collection of nerdly looking people in the photo. Ever since then we have jokingly called a conference group picture the nerd shot.
Computer scientists, especially in Europe, love to take pictures of other computer scientists. Problem is computer scientists are not particularly photogenic nor, for the most part, are they good photographers. The worst is the group photo, where we are herded like cattle to some enclosed place where we stand until all the strays are rounded up and finally the photo is taken, sometimes several times by several people.
Some things have changed over time. Most photos are now taken digitally and get posted quickly, sometimes before the conference is over. My kids enjoy playing "Where's Daddy?" especially if I am out of town. But still the group photo experience remains the same.
I was talking to my wife on the phone at the last Dagstuhl and told her it was time for the nerd shot. She said I should fix my hair and I replied "What? You want me to stand out?"
Without further adieu here is that nerd shot.
11:23 AM # Comments []