Computational Complexity

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₀.

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₀#conf₁#...#conf_m. A proper tableau for a machine M and input x is a tableau where

1. conf₀ is the initial configuration for M with input x.
2. conf_m is a configuration in the accept state.
3. 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?

1. They are all brilliant mathematicians.
2. Their research has helped establish the fundamentals of much of computer science.
3. They were all born in 1903.
4. 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 []   

Archives