### Saturday, January 04, 2003

**Logic in the 21st Century**

The June 2000 Association of Symbolic Logic Annual Meeting included a panel discussion on "The Prospects of Mathematical Logic in the Twenty-First Century". From that workshop came this paper, an interesting view of the future of logic. Richard Shore, Sam Buss, Anand Pillay and Alexander Kechris each wrote a section giving their views in the areas of recursion theory, proof theory, model theory and set theory respectively.
Mathematical Logic forms the foundation of computer science and the logic community often looks to the computer science community for directions and applications. The sections on recursion and proof theory really bring out this connection.

1:55 PM
#
Comments
[]

### Friday, January 03, 2003

**Foundations of Complexity **

Lesson 12: Turing Machine Redux

Previous Lesson |
Next Lesson

Turing Machine (from
Lee Manovich)

Back in
Lesson
1 we gave an informal description of a Turing machine as any
computer program. That was fine for computability, but for complexity
we need to give a more specific, but still informal, definition.
A *one-tape Turing machine* consists of an infinitely long "tape"
consisting of tape cells that each can carry one of a finite set
Γ of tape symbols. Typically we have Γ={0,1,B}. The Turing
machine has a finite memory, where Q represents the set of all
possible states of that memory. The Turing machine also has a tape
head that points a specific location on the tape.

Initially the input is put somewhere on the tape with the rest of the
tape having the special "B" blank symbol. The tape pointer
points to the beginning of the input. The Turing machine starts out in
some initial state q_{0}.

In each iteration the Turing machine looks at the tape character under
the head and the current state. It writes a new character under the
head and then moves the head one step left or right and then enters a
new state depending on its instructions.

If the Turing machine enters the accept state q_{a} then it
halts and accepts. If the Turing machine enters the reject state
q_{r} then it halts and rejects. Otherwise the process
repeats.

This simple model captures all of the computational power of much more
general Turing machine. It also does this with at most a polynomial
slow-down, i.e., if a problem of size n was solved in t(n) steps on
a more complex machine it can be solved in time (t(n))^{k} on
a one-tape Turing machine for some fixed k.

A deterministic Turing machine's choice of next state, character to
write and direction to move the tape is a function of the previous
state and current character under the tape. A nondeterministic machine
may allow several options and if one series of options leads to
acceptance we say the nondeterministic machine accepts.

A *configuration* of a Turing machine is a snapshot in time of
the machine and consists of the tape contents, the current state and
the location of the head pointer.

A *tableau* is a list of configurations

conf_{0}#conf_{1}#...#conf_{m}.
A *proper tableau* for a machine M and input x is a tableau where
- conf
_{0} is the initial configuration for M with input x.
- conf
_{m} is a configuration in the accept state.
- For all i, 0 ≤ i < m, conf
_{i+1} follows from
conf_{i} in one step.

A machine M accepts input x if and only if there is a proper tableau
for M and x.
8:28 AM
#
Comments
[]

### Wednesday, January 01, 2003

**2003: A Year-Long Celebration of Geniuses**

What do Alonzo Church, Andrey Kolmogorov and John von Neumann have in
common?
- They are all brilliant mathematicians.
- Their research has helped establish the fundamentals of much of
computer science.
- They were all born in 1903.
- All of the above.

Of course the answer is "All of the above." Throughout the
year (in addition to the usual posts) we will honor these men and their research in the 100th
anniversary of their births.
I almost added Frank Ramsey, also born in 1903, to the
list. Certainly Ramsey Theory has played a major role in theoretical
computer science. But the popularity of Ramsey Theory is due more to
Paul Erdös than to Ramsey who was mostly a philosopher.

6:28 AM
#
Comments
[]

### Monday, December 30, 2002

**Reflections on 2002**

We have seen many exciting theorems during the past year but once
again we have failed to prove that P≠NP or anything even close to
it. There is always next year.
The most promising sign of the past year is the increased submissions
and attendance at conferences pretty much across the board in
theoretical computer science. The large
number of students studying theory make of much of this increase. In
the late 1990's during the dot-com boom, very few students, in
particular Americans, went to graduate school in computer science. But
with the days of easy money over and the need for computer science
faculty still great, we have seen a large increase in the number of
students. These students have and will continue to bring in new ideas
and directions to our field. Let us hope there are enough jobs for all
of them.

I also started this web log during this past year. Initially, I
started this blog just to try out a new technology but I have had a
blast writing these posts and sharing my knowledge and experiences. I
hope you have enjoyed reading them. I don't understand how I rank so
high on a Google search on
"web log". Perhaps because "weblog" is
supposed to be one word.

In remembrance: Edsger
Dijkstra and Steve
Seiden.

Have a good New Years everyone!

8:17 AM
#
Comments
[]