### Friday, May 16, 2003

**Turing Machines and Godel's Theorems**

A 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 Theorem

Previous 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(s^{2}(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 =
c^{s(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
2^{t} 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(CONF_{1},CONF_{2},t)
\* Output TRUE if CONF_{1} can get to CONF_{2} in at most 2^{t} steps *\
If t=0 then
{if (CONF_{1} = CONF_{2}
or CONF_{1} goes to CONF_{2} in one step on machine N)
then output TRUE else output FALSE}
For each CONF
{If CHECK(CONF_{1},CONF,t-1) and CHECK(CONF,CONF_{2},t-1) then output TRUE}
Output FALSE

We 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 CONF_{0} be the initial configuration encoding x. We can
now give our main routine.

MAIN
Let r be the smallest integer at least log_{2}(c^{s(n)})
For each CONF in an accepting state
{If CHECK(CONF_{0},CONF,r) then output TRUE}
Output FALSE

Total space used: O(log_{2}(c^{s(n)})s(n)) =
O(s^{2}(n)).

3:30 PM
#
Comments
[]

### Monday, May 12, 2003

**The Nerd Shot**

Many 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
[]