% file "JLRch242up.tex"
% LEGEND---search on the following strings for impt comments by KSN.
% {E,e}ditor     questions and special comments for the CRC editors.
% {A,a}uthor[s]  queries for the authors; answers requested.
% {O,o}ops       mistake fixed by KSN -- please check.
% !! or check    mental note by KSN of something that may still need checking.
% KSN            comment on changes by KSN worth noting.
%% Author's responses usually start with Answer:

% Note: To print /without/ the .ps figures, one line with \psfig
% must be commented out.  --KSN

% chapter24 

\documentclass[12pt]{article}
\usepackage{amssymb}
\usepackage{epsf}
\special{landscape}\special{! /landplus90 true store}
\textwidth = 6in
\textheight=8.75in
\topmargin= -0.35in     %-0.25in
\oddsidemargin= 0.25in    % 0.25in
\evensidemargin= -0.25in   %-0.5in
\input{2up.tex}
\twouparticle

% \documentstyle[11pt,epsf]{article}
\input{psfig}

% \renewcommand{\baselinestretch}{1.5}
% \setlength{\topmargin}{-0.2in}
% \setlength{\textwidth}{6.5in}
% \setlength{\oddsidemargin}{-0.2in}
% \setlength{\evensidemargin}{-0.2in}
% \setlength{\textheight}{8.5in}
% \setlength{\footskip}{0.5in}
% \setlength{\parskip}{3pt plus 1pt minus 1pt}

%old format replace by above Tao's format.
%\renewcommand{\baselinestretch}{1.15}
%\setlength{\topmargin}{-0.2in}
%\setlength{\textwidth}{6.5in}
%\setlength{\oddsidemargin}{-0.2in}
%\setlength{\evensidemargin}{-0.2in}
%\setlength{\textheight}{8.5in}
%\setlength{\footskip}{0.5in}
%\setlength{\parskip}{3pt plus 1pt minus 1pt}

%% \makeindex

%% superstring macros
\newcommand{\dplus}{\ifmmode {D^{+}} \else ${D^{+}}$ \fi}
\newcommand{\dminus}{\ifmmode {D^{-}} \else ${D^{-}}$ \fi}
\newcommand{\mrg}{\rightarrow}
\newcommand{\lar}{\leftarrow}
\newcommand{\pref}[2]{{\it pref}(#1,#2)}
\newcommand{\ovlp}[2]{{\it ov}(#1,#2)} 
\newcommand{\merge}[2]{{\it m}(#1,#2)} 
\newcommand{\dist}[2]{{\it d}(#1,#2)}
\newcommand{\cost}[2]{{\it c}(#1,#2)}
\newcommand{\length}[1]{{\it l}(#1)}
\newcommand{\weight}[1]{{\it w}(#1)}
\newcommand{\card}[1]{{\it card}(#1)}
\newcommand{\qed}{\ \ \ \rule{7pt}{8pt}\medskip}
\newcommand{\partialqed}{\ \ \ \raisebox{2pt}{\framebox[7pt]{\ }}\medskip}
\newtheorem{defin}{Definition}
\newcommand{\bracket}[1]{\langle #1 \rangle}
\newcommand{\barr}{\overline}
\newcommand{\Gee}{G_S}
\newcommand{\Geep}{G_{P,N}}
\newcommand{\cyc}[1]{{\it CYC}(#1)}
\newcommand{\CYC}{{\it CYC}(G_S)}
\newcommand{\cycn}[1]{{\it CYC1}(#1)}
\newcommand{\tsp}[1]{{\it TSP}(#1)}
\newcommand{\TSP}{{\it TSP}(G_S)}
\newcommand{\opt}[1]{{\it OPT}(#1)}
\newcommand{\optn}[1]{{\it OPT1}(#1)}
\newcommand{\OPT}{{\it OPT}(P,N)}
%\newcommand{\SS}{{\cal S}}
\newcommand{\floor}[1]{\lfloor #1 \rfloor}
% \newcommand{\copt}{C_{\rm opt}}
\newcommand{\spi}{S_{\pi}}
\newcommand{\first}[1]{{\it first}(#1)}
\newcommand{\last}[1]{{\it last}(#1)}
\newcommand{\shift}[1]{{\it rotate}(#1)}
\newcommand{\str}[1]{{\it strings}(#1)}
\newcommand{\period}[1]{{\it period}(#1)}
\newcommand{\factor}[1]{{\it factor}(#1)}
\newcommand{\stri}[2]{{\it strings}(#1,#2)}
\newcommand{\weako}{o_w}
\newcommand{\culpo}{o_c}
%end of superstring special macros

%General Forms
% \newcommand{\proof}{\noindent {\bf Proof:}\space}
\newcommand{\proof}{{\bf Proof. \enspace}}
\newcommand{\comment}[1]{}
\newcommand{\hs}{\enspace}
\newcommand{\hhs}{\thinspace}
\newcommand{\diverges}{\uparrow}
\newcommand{\converges}{\downarrow}
\newcommand{\inter}{\bigcap}
\newcommand{\real}{\ifmmode {\rm R} \else ${\rm R}$ \fi}
\newcommand{\nat}{\ifmmode {\rm N} \else ${\rm N}$  \fi}
\newcommand{\tot}{\ifmmode {\cal T} \else ${\cal T}$ \fi}
\newcommand{\sigstar}{\ifmmode \Sigma^{\ast} \else $\Sigma^{\ast}$ \fi}

\newtheorem{theorem}{\sc Theorem}[section]
% \newtheorem{lemma}{Lemma}
\newtheorem{lemma}[theorem]{\sc Lemma}
% \newtheorem{corollary}{Corollary}
\newtheorem{corollary}[theorem]{\sc Corollary}
% \newtheorem{definition}{Definition}
\newtheorem{definition}{\sc Definition}[section]
% \newtheorem{fact}{Fact}
% \newtheorem{claim}{Claim}
\newtheorem{claim}[theorem]{\sc Claim}
% \newtheorem{conjecture}{Conjecture}
\newtheorem{conjecture}[theorem]{\sc Conjecture}
\newlength{\thislabel}
\newcommand{\labsize}[1]{\settowidth{\thislabel}{#1}}
\newtheorem{example}{\sc Example}[section]
%\newenvironment{example}{\begin{example}}
%{\hspace*{\fill}$\Diamond$\end{example }}
\def\lablimer2stlabel#1{\rm #1\hfil}

\newcommand{\emptystring}{\epsilon}
\newcommand{\Vars}{V}   %% can switch to "N" for "nonterminals".

\pagestyle{plain}
\sloppy

\begin{document}
\baselineskip 15pt
%% \sloppy
%% \setcounter{chapter}{12}
%% \chapter{}
\title{Basic Notions in Computational Complexity
\footnote{Preliminary version of a chapter in the forthcoming
{\it CRC Handbook of Algorithms and Theory of Computation}.}}

\author{
Tao Jiang\\
Department of Computer Science\\
McMaster University\\
Hamilton, Ontario L8S 4K1, Canada
\and
Ming Li\\
Department of Computer Science\\
University of Waterloo\\
Waterloo, Ontario N2L 3G1, Canada
\and
Bala Ravikumar\\
Department of Computer Science\\
University of Rhode Island\\
Kingston, RI 02881, USA}

\date{}

\maketitle

\section{Introduction} \label{intro}
Computational complexity is aimed at measuring how complex a computational
solution is. There are many ways to measure the complexity of a solution: how
hard it is to understand it, how hard to express it,
how long the solution process 
will take, and more.  The last criterion---time---is
most widely taken as the definition of complexity. This is because the agent
that implements an algorithm is usually a computer---and from
a user's point of view,
the most important issue is how long one should wait to see the solution. 
However,
there are other important measures of complexity,
such as the amount of memory, 
hardware, information, communication, knowledge,
or energy needed for the solution. 
Complexity theory is aimed at quantifying these resources
precisely and studying
the amounts of them required to accomplish computational tasks.

This technical sense of the word ``complexity'' did not take root
until the mid-1960s.
Today, complexity theory is not only a vibrant subfield of 
computer science, but also has direct or metaphoric
impact on other fields such as dynamical systems and chaos theory.
%
% NB: This assertion does hold up---cf. Gell-Mann, /The Quark and the Jaguar/,
% pp28-29, "Different Kinds of Complexity".  --KSN  
%
The seed of computational complexity is the formalization
of the concept of an {\bf algorithm}.
%
% Chapter 32 deals with different equivalent ways of defining algorithms.
% KSN: wrong order, misdirecting the reader.
%
Algorithms in turn must be planted in some {\em computational model\/},
ideally one that abstracts important features of real computing machines
and processes.  
In this chapter we consider the {\bf Turing machine},
a computer model created and studied by the
British mathematician Alan Turing in the 1930s \cite{Turing}.  % !!!
Chapter~32 will discuss different (and equivalent) ways of formalizing algorithms.

With the advent of commercial computers in the 1950s and 1960s, when
processor speed was much lower and memory cost unimaginably higher than today,
it became critical to design {\em efficient\/} algorithms for solving
large classes of problems.  Just knowing that a problem was solvable, which
had been the main concern of computability theory since the 1930s, was
no longer enough.   
Turing machines provided a basis for Hartmanis
%
% Editor: The usage of "Alan Turing", "Hartmanis", and "N. Chomsky" on this
% page was inconsistent.  The least change was to use last-name-only
% everywhere, but I left "Alan Turing" in above because of the context of the
% sentence.  BTW, it is AOK to leave Babbage etc. out here.   --KSN
%
and Stearns \cite{HS} to formally define the measures
of {\bf time complexity} and {\bf space complexity} for computations.
The latter refers to the amount of memory needed to execute the computation.
They defined measures for other resources as well, and Blum ~\cite{blum}
found a precise definition of {\em complexity measure\/} that was not
tied to any particular resource or machine model. 
Together with earlier work by Rabin~\cite{Rabin}, these papers
marked the beginning of {\em computational complexity theory\/}
as an important new discipline. A closely related development was
drawn together by
Knuth, whose work on algorithms and data structures \cite{Knuth}
created the field of
%
% {\em Design and Analysis of Algorithms}.
% KSN: this was inconsistent capitalization.
%
{\em algorithm design and analysis\/}.
All of this work has been recognized in annual
Turing Awards given by the Association for Computing Machinery.
%
% Editor: italicize Turing Award? Say "Each of the above-named people
% has received a Turing Award for thjis work."?  --KSN
%
Hartmanis' Turing Award lecture~\cite{hartmanis} recounts the origins of
computational complexity theory and speculates on its future development. 

The power of a computing machine depends on
its internal structure as well as on the amount of time, space, or
other resources it is allowed to consume.
Restricting our model of choice,
the Turing machine, in various internal ways yields progressively
simpler and weaker computing 
machines.  These machines correspond to a natural hierarchy of grammars
defined and advanced by 
Chomsky~\cite{Chomsky1}, which we describe in Chapter~31.
In this chapter we present the most basic
computational models, and use these models to classify problems
first by solvability and then by complexity.
%
% The longer text was unnecessary.

Central issues studied by researchers in computational complexity include
the following.
% 
% (i) For a given amount of resource (or for a given type of resource),
% what problems can and cannot be solved? 
% (ii) Understanding the relationship between problems
% requiring the same amount of resource...
%
% KSN: A sentence fragment with non-parallel structure, and then the whole pgh
% became cryptic about "disguises".  I did my best to fix it,
% starting with the {enumerate} block really called for here.
%
\begin{itemize}
\item
For a given amount of resources, or for a given type of resource, what problems 
can and cannot be solved?
\item
What is the relationship between problems requiring essentially the same amount
of the resource or resources?  May they be equivalent in some intrinsic sense?
\item
What connections are there between different kinds of resources?
Given more time, can we reduce the demand on memory storage, or vice-versa?
\item
What general limits can be set on the kind of problems that can be solved
when resources are limited?
%
% I allowed the dual use of "limit" to stand.  --KSN
%
\end{itemize}
The end thrust of Turing's famous paper \cite{Turing}
was to demonstrate rigorously that several fundamental problems in logic
cannot be solved by algorithms at all.  Complexity theory aims to show
similar results for many more problems in the presence of resource limits.
Such an unsolvability result, although ``bad news'' in most
contexts (cryptographic security is an exception),
can have practical benefits:\ it may lead to alternative models, goals,
or solution strategies.  As will come out in Chapters 33--34,
complexity theory has so far been much more successful at drawing 
relative conclusions and relationships between problems than in proving
absolute statements about (un)solvability.

\section{Computational Models} \label{models}  
Throughout this chapter, $\Sigma$ denotes a finite alphabet of symbols;
unless otherwise specified, $\Sigma = \{ 0,1 \}$.
Then $\Sigma^*$ denotes the set of all finite strings,
including the empty string $\emptystring$, over $\Sigma$.
%
% Here $*$ is the so-called Kleene operator which concatenates
% any finite number of elements in $\Sigma$.
% KSN: See how I solved the out-of-order defn of regular expns problem
% by inserting a pgh to take this sentence just a little bit further.
% Authors, editor: I hope my use of "pattern" isn't felt to clash...
%%
%% Answer: Fine with me since pattern languages are not discussed here.
A {\bf language} over $\Sigma$ is simply a subset of $\Sigma^*$.

We use {\bf regular expressions} in specifying some languages.
In advance of the formal definition to come in Chapter 31, we 
define them as one kind of ``patterns'' for strings to ``match.''
The basic patterns are $\epsilon$ and the characters in $\Sigma$, which
match only themselves.  
The null pattern $\emptyset$ matches no strings.
Two patterns joined by ``$+$'' match any string
that matches either of them.  
Two or more patterns written in sequence match any 
string composed of substrings that match the respective patterns.
%
% Editor, authors: "...in the same sequence" should be clear from
% "respective", but if you think it's not, do add those four words.--KSN
%
%% Answer: Fine with me.
A pattern followed by a ``$*$'' matches
any string that can be divided into zero or more successive substrings,
each of which matches the pattern---here the ``zero'' case applies to
$\emptystring$, which matches any starred pattern.  
For example, the pattern $0(0+1)^*1$ matches any 
string that begins with a 0 and ends with a 1, with zero or more
binary characters in between.  The pattern can be used as a {\em name\/} for
the language of strings that match it.  In like manner, the
pattern $(0^* 10^*1)^* 0^*$ stands for the language of binary strings
that have an even number of 1s.  This pattern {\em says\/} that trailing
0s are immaterial to any such string, and the rest of the string can be
broken into zero or more substrings, each of which ends in a 1 and has
exactly one previous 1.

\subsection{Finite Automata}\label{sub.fin}
The finite automaton (in its deterministic version) was introduced
by McCulloch and Pitts in 1943 as a logical model for the 
behavior of neural systems~\cite{pitts}. Rabin and Scott
introduced the nondeterministic finite automaton (NFA)
in~\cite{rabin}, and showed that NFAs are equivalent to 
deterministic finite automata, in the sense that they recognize
the same class of languages.
%
% Hisss!  "rabin" a different cite from "Rabin", and no Scott??
%
This class of languages, called the {\bf regular languages\/}, had already
been characterized by
Kleene \cite{Kleene} and
Chomsky and Miller~\cite{miller}
in terms of
regular expressions and regular grammars, which will be described
formally in Chapter~31. 

In addition to their original role in the study of neural nets,
finite automata have enjoyed great success in many fields such as
the design and analysis of sequential circuits \cite{kohavi},
asynchronous circuits~\cite{brzozo1},
text-processing systems \cite{lesk}, and compilers. 
They also led to the design of more efficient algorithms. One excellent 
example is the development of linear-time string-matching algorithms, 
as described in~\cite{knuth}. Other applications of finite automata can be 
found in computational biology~\cite{searls}, natural language processing, 
and distributed computing~\cite{lynch}.

A {\bf finite automaton}, pictured in Figure~\ref{fa},
%
\begin{figure}
\begin{center}
\input{fa.pstex_t}
\end{center}
\caption{A finite automaton.}
\label{fa}
\end{figure}
%
A {\bf finite automaton}
consists of an {\em input tape\/} and a 
{\em finite control\/}.
%
% The text had "finite state control", inconsistent with the figure.
%
The input tape contains a finite string of input symbols,
and is read one symbol at a time from left to right.
The finite control is connected to an {\em input head\/} that reads
each symbol, and can be in one of a finite number of {\em states\/}.
The input head is {\em one-way\/},
meaning that it cannot ``backspace'' to the left,
and {\em read-only\/}, meaning that it cannot alter the tape.
At each {\em step\/}, the finite control may change its state
according to its current state and the symbol read, and the head advances
to the next tape cell.  In an NFA there may be more than one
choice of next state in a step.  Figure~\ref{fa}
also shows the second step of
a computation on an input string beginning $aabab\dots$
When the input head 
reaches the right end of the input tape, if the machine
is in a state designated ``final'' (or ``accepting''),
we say that the input string is {\em accepted\/};
else we say it is {\em rejected\/}.
The following is the formal definition.

\begin{definition}\label{def.ming1}
\rm
A {\bf nondeterministic finite automaton} (NFA) is a quintuple 
$(Q,\Sigma ,\delta , q_0 , F)$, where
\begin{itemize}
\item
$Q$ is a finite set of {\em states\/};
\item
$\Sigma$ is a finite set of {\em input symbols\/};
\item
$\delta$, the {\em state transition function\/}, is a mapping from 
$Q \times \Sigma$ to subsets of $Q$; 
\item
$q_0 \in Q$ is the {\em start state\/} of the NFA;
\item
$F \subseteq Q$ is the set of {\em final states\/}.
\end{itemize}
If $\delta$ maps $|Q| \times \Sigma$ to singleton subsets of
$Q$, then we call such a machine a {\bf deterministic finite
automaton} (DFA).

\end{definition}

\noindent
Note that a DFA is treatable as a special case of an NFA, where the next
state is always uniquely determined by the current state and
the symbol read.  On any input string $x \in \Sigma^*$, a DFA follows a
unique {\em computation path\/}, starting in state $q_0$.
If the final state in the path is in $F$, then $x$ is {\em accepted\/},
and the path is an {\em accepting path\/}.
An NFA, however, may have multiple
computation paths on the same input $x$.  It is useful to imagine that
when an NFA has more than one next state, all options are taken in
parallel, so that the ``super-computation'' is a tree of
branching computation paths.  Then the NFA is said to {\em accept\/}
$x$ if at least {\em one\/} of those paths is an accepting path.

\medskip
{\noindent \sc Remarks:} The concept of a nondeterministic automaton,
and especially the notion of acceptance, can be nonintuitive and
confusing at first.  We can, however, explain them in terms that
should be familiar, namely those of a {\em solitaire\/} game such
as ``Klondike.''
The game starts with a certain arrangement of cards, which we
can regard as the input, and has a desired ``final'' position---in
Klondike, when all the cards have been built up by suit from ace to king.
At each step, the rules of the game dictate how a new arrangement
of cards can be reached from the current one---and the element of
nondeterminism is that there is often
more than one choice of move (otherwise the game would be little fun!).
Some positions have no possible move, and lose the game.
Most crucially, some positions have moves that unavoidably lead to
a loss, and other moves that keep open the possibility of winning.
Now for a given position, the important analytical question is, 
``Is there a way to win?''  The answer is yes so long as there is
at least one sequence of moves that ends in a (or the) desired final position.
For the starting position, this condition 
is much the same as for an input to be accepted by an NFA.
(Practically speaking, some winnable starting positions may give so many
chances to go wrong along the way that a player may have little chance to
find a winning sequence of moves.  That, however, is beside the point
in defining which positions are {\em winnable\/}.  If one can always
(efficiently!) answer the yes/no question of whether a given position
is winnable,
then one can always avoid losing moves---and win---so long as the
start position is winnable to begin with.)
% 
% KSN: could add even more here...

In any event, the set of strings accepted by a (deterministic or
nondeterministic) finite automaton $M$ is denoted by $L(M)$.
When we say that $M$ {\em accepts a language $L$\/}, we mean
that $M$ accepts all strings in $L$ {\em and nothing else\/},
i.e.\ $L = L(M)$.
Two machines are {\bf equivalent} if they accept the same language. 

Nondeterminism is capable of modeling many important situations other
than solitaire games.  Concurrent computing offers some examples.
Suppose a device or resource (such as a printer or a network interface) is
controllable by more than one process.  Each process could change the
state of the device in a different way.  Since there may be no
way to predict the order in which processes may be given control
in any step, the evolution of the device
may best be regarded as nondeterministic.

Sometimes a state change can occur without input stimulus.
This can be modeled by allowing an NFA to make 
{\em $\emptystring$-transitions\/}, which change state without advancing the
read head.  Then the second argument of $\delta$ can be $\emptystring$
instead of a character in $\Sigma$, and these transitions can even
be nondeterministic, for instance if $\delta(q_0,\emptystring) = \{q_1,q_2\}$.
It is not hard to see that by suitable ``lookahead'' on
states reachable by {\em $\emptystring$-transitions\/}, one can always
convert such a machine into an equivalent NFA that does not use them.
  

%\begin{definition}
%A {\em configuration} of 
%\end{definition}
% KSN: Yeah, I was tempted to define configurations above, but better without.

\begin{example}\label{example.ming1}
\rm
We design 
%
% a DFA
% KSN: Oops, it's not a DFA.
%
an NFA to accept the language $0(0+1)^*1$.
Recall that this regular expression defines those
strings in $\{0,1\}^*$ that
begin with a $0$ and end 
with a $1$. 
A standard way to draw finite automata is
exemplified by
Figure~\ref{auto1}.
\begin{figure}
\begin{center}
\input{auto1.pstex_t}
\end{center}
\caption{An NFA accepting $0(0+1)^*1$.}
\label{auto1}
\end{figure}
As a convention, each circle represents a state,
and an unlabeled arrow points to the start state (here, state ``a'').
Final states such as ``c'' have darker (or double) circles. 
The transition function $\delta$ is represented by the labeled edges.
For example, $\delta({\rm a},0)=\{{\rm b} \}$, and
$\delta({\rm b},1) = \{{\rm b},{\rm c}\}$.
When a transition is missing, such as
on input $1$ from state ``a'' and on both inputs from 
state ``c'', the transition is assumed
to lead to an implicit non-accepting ``dead'' state, which has
transitions to itself on all inputs.
In a DFA such a dead state must be included when counting the number of
states, while in an NFA it can be left out.
%
% The text had ``trap state'' here, but ``dead state'' on the next page!

The machine in Figure~\ref{auto1} is nondeterministic since from 
``b'' on input $1$ the machine has two choices: stay at ``b''
or go to ``c''.
Figure~\ref{auto2} gives a DFA that accepts the same language.
The DFA has four, not three, states, since a dead state reached by
an initial `1' is not shown.
% 
% The scrambled order in which concepts were defined vs. used, compounded
% by the long proof on pages 9--10, set me a terrible task.  --KSN
%
\begin{figure}
\begin{center}
\input{auto2.pstex_t}
\end{center}
\caption{A DFA accepting $0(0+1)^*1$.}
\label{auto2}
\end{figure}
\end{example}

\begin{example}\label{example.ming2}
\rm
The DFA in Figure~\ref{auto3} accepts the language
of all strings in $\{0,1\}^*$
with an even number of $1$'s, which has the 
regular expression $(0^* 10^*1)^* 0^*$.
\begin{figure}
\begin{center}
\input{auto3.pstex_t}
\end{center}
\caption{A DFA accepting $(0^* 10^*1)^* 0^*$.}
\label{auto3}
\end{figure}
\end{example}

\begin{example}\label{example.ming3}
\rm
For a final example of a regular
language, we introduce a general ``tiling problem''
to be discussed further in Chapter 32,
and then strip it down to a simpler problem.
%
% This is an {\it unsolvable} problem in the sense that
% no algorithm can solve all its instances.
% Not needed here---better organization to delete it.  --KSN
% 
A {\em tile\/} is a unit-sized
square divided into four quarters 
%
% (see Figure 1(a), Chapter 32)
% SEE LAST COMMENT
%
by
joining two diagonals. Each quarter has a color chosen from a finite
set $C$ of colors.
Suppose you
are given 
%
% different kinds of such unit square tiles forming set $T$.
%
a set $T$ of different types of tiles, 
and have an unlimited supply of each type.  A $k \times n$ rectangle is said 
to be {\em tiled\/} using the tiles in $T$ if the rectangle can be filled with
exactly $kn$ unit tiles (with no overlaps)
%
% such that the tiles sharing a common side or edge have the same colors.
% KSN: /Oops/, the /tiles/ don't have the same colors, the /quarters/ do.
%
such that at every edge between two tiles, the quarters of the two
tiles sharing that edge have the same color.
The tile set $T$ is said to {\em tile\/} an entire plane
if the plane can be covered with tiles subject to the color compatibility stated
above.  As a standard application of K{\"o}nig's infinity lemma
%
% ~\cite{Knuth}
% Authors: I which of Knuth's volumes, and which chapter, can we find it?--KSN
%%
%% Answer: It's in chapter 2 of volume 1.
(for which see \cite{Knuth}, Chapter 2, p. 381), it
can be shown that the entire plane can be tiled with a
tile set $T$ if and only if all finite integer sided rectangles
can be tiled with $T$.
We will see in Chapter 32 that the problem of whether a given tile set $T$
can tile the entire plane is {\em unsolvable\/}.
Chapter 32 will also say more about the meaning and implications of
this tiling problem. 

Here we will consider a simpler problem:
Let $k$ be a fixed positive integer. Given a set $T$ of unit
tiles, we want to know whether
$T$ can tile an infinite {\it strip} of width $k$.  The answer is yes
if $T$ can tile any $k \times n$ rectangle for all
$n$. It turns out that this problem is solvable
by an efficient algorithm. One way to design such an
algorithm is based on finite automata. 
We present the solution for $k$ = 1 and leave the generalization for other
values of $k$ as an exercise.
Number the quarters of each tile as in Figure~\ref{fig.tile2}. Given a tile set
$T$, we want to know whether for all $n$,
the $1 \times n$ rectangle can be tiled using $T$.

\begin{figure}
\centerline{\psfig{figure=ravifig2.ps,height=0.5truein,width=0.5truein,silen=}}
\par
\smallskip
\caption{Numbering the quarters of a tile.}
\label{fig.tile2}
\end{figure}

To use finite automata, we define a language  that corresponds to valid
tilings.  Define $\Sigma$, the input alphabet, to be $T$, the tile set. Each
tile in $T$ can be described by a 4-tuple $[A,B,P,Q]$ where $A$, $B$,
$P$, and $Q$ are (possibly equal) members of the color set $C$.
Next we define a language $L$ over $\Sigma$ to be the set of strings
$T_1 T_2 ... T_n$ such that
(i) each $T_i$ is in $\Sigma$, and (ii) for each $i$,
$1 \leq i \leq n-1$, $T_i$'s third-quadrant color is the same as
$T_{i+1}$'s first-quadrant color.  These two conditions say that
$T_1 T_2 ... T_n$ is a valid $1 \times n$ tiling.

We will now informally describe a DFA $M_L$ that recognizes the 
language $L$. Basically, $M_L$ ``remembers'' (using the 
current state as the memory) the relevant information---for this problem, it 
need only remember the third-quadrant color $Q$ of the {\it most recently
seen\/} tile.
%
% Basic LaTeXnique: don't use ", use "---" for a sentence-level dash, 
% use \em not \it for emphasis, and follow with a \/ before a word.
%  
Suppose the DFA's current state is $Q$. If the next (input) tile is $[X,Y,W,Z]$,
it is consistent with the last tile if and only if $Q$ = $X$. In this case, the
next state will be $W$. Otherwise, the tile sequence is inconsistent, so $M_L$
enters a ``dead state'' from which it can never leave and rejects.
All other states of $M_L$ are accepting states.
Then the infinite strip of width 1 can be tiled if and only if 
the language $L$
accepted by $M_L$ contains strings of all lengths. There are standard
algorithms to determine this property for a given DFA.
\end{example}

The next three theorems show the satisfying result that
all the following language classes are identical: 
\begin{itemize}
\item
the class of languages accepted by DFAs;
\item
the class of languages accepted by NFAs;
\item
the class of languages generated by regular expressions.
%
% ,to be defined in Chapter 31.
% Definition~\ref{tao.def8}; 
% KSN: No longer needed.
%
\item
the class of languages generated by the right-linear, or Type-$3$, grammars,
which are formally defined in Chapter 31 and informally used here.
%ition~\ref{tao.def16}.
\end{itemize}
This class of languages is called the {\bf regular languages}.
%We first show
%${\rm NFA} \Leftrightarrow {\rm DFA}$, then 
%${\rm NFA} \Leftrightarrow$ right-linear grammars, and finally
%${\rm NFA} \Leftrightarrow {\rm regular~expressions}$.
%%% Ming: what are these \Leftarrow notations?

\begin{theorem}\label{theorem.ming1}
For every NFA, there is an equivalent DFA.
\end{theorem}
\begin{proof}
An NFA might look more powerful since it can
carry out its computation in parallel with its nondeterministic
branches. But since we are working with a {\it finite number} of
states, we can simulate an NFA $M=(Q,\Sigma , \delta , q_0, F )$
by a DFA $M'=(Q',\Sigma , \delta ' , q_0', F' )$, where
\begin{itemize}
\item
$Q'= \{ [S] ~ : ~ S \subseteq Q \}$;
\item
$q_0' = [\{q_0\}]$;
%
% KSN: OK as is, but not if "NFA" includes epsilon-transitions.
%
\item
$\delta ' ([S],a)=[S'] = [\cup_{q_l \in S} \delta (q_l ,a) ]$;
\item
$F'$ is the set of all subsets of $Q$ containing a 
state in $F$.
\end{itemize}
%
% My addition will really help the poor reader.  --KSN
%
Here square brackets have been placed around sets of states
to help one view these sets as being states of the DFA $M'$.
The idea is that whenever $M'$ has read some initial segment $y$ of
its input $x$, its current state equals the set of states $q$ such
that $M$ has a computation path
reading $y$ that leads to state $q$.  When all of $x$ is read,
this means that $M'$ is in an accepting state if and only if
$M$ has an accepting computation path.  Hence $L(M)=L(M')$. $\Box$
\end{proof}

\begin{example}\label{example.ming13}
\rm
Example~\ref{example.ming1} contains an NFA and an equivalent DFA
accepting the same language. 
In fact the above proof provides an effective procedure for converting
an NFA to a DFA. Although each NFA can be converted to an equivalent
DFA, the resulting DFA may require exponentially many more states,
since the above procedure may assign a state for every eligible subset
of the states of the NFA.
%
% This turns out the be the best thing one can
% do in the worst case.
% Unnecessary --KSN
% 
For any $k > 0$, 
consider the language $L_k = \{ x ~|~ x\in \{0,1\}^*$ and
the $k$th letter from the right of $x$ is a $1\}$. An NFA 
of $k+1$ states (for $k = 3$) accepting $L_k$ is given in Figure~\ref{auto4}.
Now we claim that any DFA $M$ accepting $L_k$ needs a separate state for
every possible value $y \in \{0,1\}^k$ of the last $k$ bits read.
Take any distinct $y_1,y_2 \in \{0,1\}^k$ and let $i$ be a position in which
they differ.  Let $z = 0^{k-i}$.
Then $M$ must accept one of the strings
$y_1 z$, $y_2 z$ and
reject the other.  This is possible only if the state $M$ is in 
after processing $y_1$ (with $z$ to come) is different from that after
$y_2$, and thus $M$ needs a different state for each string in $\{0,1\}^k$. 
The $2^k$ required states are also sufficient, as the reader may verify.

\begin{figure}
\begin{center}
\input{auto4.pstex_t}
\end{center}
\caption{An NFA accepting $L_3$.}
\label{auto4}
\end{figure}
%See Figure~\ref{auto4a} for a tighter relation.
%%% Ming: maybe you want to elaborate a little here.
%
%\begin{figure}
%\begin{center}
%\input{auto4a.pstex_t}
%\end{center}
%\caption{An NFA accepting the complement of $(0+1)^*1(0+1)^{k-1}$,
%for $k=3$. An equivalent DFA needs $2^k$ states.}
%\label{auto4a}
%\end{figure}
\end{example}

The remaining results of this section point forward to the
formal-language models defined in Chapter 31.
The point of including them here is to show the power of the
finite automaton model.
Regular expressions have been defined above, while a
{\em regular grammar\/} over $\Sigma$ consists of a set $\Vars$ of
variable symbols, a starting variable $S \in \Vars$, and a set $P$ of
substring-rewrite rules of the forms $A \rightarrow cB$,
$A \rightarrow \epsilon$, or $A \rightarrow c$, where $A,B \in \Vars$
and $c \in \Sigma$.
%
% The original text didn't even have a forward reference to Chapter 31 here,
% and I felt a one-sentence definition was justified.
% In the terminology I know, "right-linear" grammars include a
% fourth kind of rule A --> yB where y is any string of terminals.  I let
% the authors' usage in Ch. 31 stand, but put in a qualifying note.--KSN   


\begin{theorem}\label{theorem.ming2}
A language $L$ is generated by a regular grammar if and only if
$L$ is accepted by an 
% {\rm NFA}.
% KSN: Why Roman?  It's an ordinary acronym, not a mathematical object (like a
% complexity class).
NFA.
\end{theorem}

\begin{proof}
Let $L$ be accepted by an NFA $M=(Q,\Sigma ,\delta ,q_0,F)$.
We define an equivalent regular grammar $G=(\Sigma ,\Vars,S,P)$ by taking
$\Vars=Q$ with $S=q_0$, adding a rule $q_i \rightarrow c q_j$ 
whenever $q_j \in \delta (q_i,c)$, and adding rules
$q_j \rightarrow \emptystring$ for all
$q_j \in F$. Then the grammar simulates computations by the
NFA in a direct manner, giving $L(G)=L(M)$.  

Conversely,
suppose $L$ is the language of a regular grammar $G=(\Sigma ,\Vars,S,P)$.
We design an NFA $M=(Q,\Sigma ,\delta ,q_0,F)$ by taking
$Q=\Vars \cup \{f\}$, $q_0 = S$, and $F=\{f\}$. To define the $\delta$
function, we have $B \in \delta (A,c)$ iff $A \rightarrow cB$.
For rules $A \rightarrow c$, $\delta (A,c)=\{f\}$.
Then $L(M)=L(G)$---if this is not clear already, the treatment of grammars
in Chapter 31 will make it so. $\Box$ 
\end{proof}

\begin{theorem}\label{theorem.ming3}
A language $L$ is specified by a regular expression if and only if
$L$ is accepted by an NFA.
\end{theorem}

{\sc Proof Sketch.}
{\em Part 1.} We inductively convert a regular expression to an NFA that
accepts the same language as follows.
\begin{itemize}
\item
The pattern $\emptystring$ converts to the NFA
$M_{\epsilon} = (\{q\},\Sigma , \emptyset ,q, \{q\})$,
which accepts only the empty string.
\item
The pattern $\emptyset$ converts to the NFA
$M_{\emptyset} = (\{q\},\Sigma ,\emptyset ,q, \emptyset)$,
which accepts no strings at all.
\item
For each $c \in \Sigma$, the pattern $c$ converts to the
NFA $M_c = (\{q,f\},\Sigma ,\delta (q,c)=\{f\} ,q, \{ f \} )$,
which accepts only the string $c$.
\item
A pattern of the form $\alpha + \beta$, where $\alpha$ and $\beta$ are 
regular expressions that (by induction hypothesis) have corresponding
NFAs $M_\alpha$ and $M_\beta$, converts to an
NFA $M$ that connects $M_\alpha$ and $M_\beta$ in parallel:
$M$ includes all the states and transitions of $M_\alpha$ and $M_\beta$
and has an extra start state $q_0$, which is connected by
$\emptystring$-transitions to the start
states of $M_\alpha$ and $M_\beta$.
\item
A pattern of the form $\alpha \cdot \beta$, where $\alpha$ and $\beta$ 
have the corresponding
NFAs $M_\alpha$ and $M_\beta$, converts to an
NFA $M$ that connects $M_\alpha$ and $M_\beta$ in series:
$M$ includes all the states and transitions of $M_\alpha$ and $M_\beta$
and has extra $\emptystring$-transitions from the final states of
$M_\alpha$ to the start state of $M_\beta$.
The start state of $M$ is that of $M_\alpha$, while the final states
of $M$ are those of $M_\beta$.
\item
A pattern of the form $\alpha^*$, where $\alpha$ has the corresponding
NFA $M_\alpha$, converts to an NFA $M$ that figuratively feeds $M_\alpha$
back into itself.  $M$ includes the states and transitions of 
$M_\alpha$, plus $\emptystring$-transitions from the final states of
$M_\alpha$ back to its start state.  This state is not only the start state
of $M$ but the only final state of $M$ as well.
\end{itemize}

% Editor and authors: A figure showing the "parallel", "series", and "feedback"
% cases, perhaps with some chat about the electric-circuit analogy,
% would be nice here, but not needed.  --KSN
%% Author: Okay

{\em Part 2.} We now show how to convert an NFA to an equivalent
regular expression. The idea used here is based on~\cite{brzozo};
see also \cite{brzozo1} and \cite{wood}.
%Let's generalize 
%an NFA by allowing the transition function to map the current
%state and an arbitrary regular expression over $\Sigma$ to a set of states.
% KSN: It is OK with me to skip this and slip it on by the reader.

Given an NFA $M$, add a new final state $t$, and add
$\emptystring$-transitions from each old final state of $M$ to $t$.
Also add a new start state $s$ with an $\emptystring$-transition to the old
start state of $M$.
The idea is to eliminate all states $p$ other than $s$ and $t$
as follows.  To eliminate a state $p$, we eliminate each arc coming in to $p$
from some other state $q$ as follows:
For each triple of 
states $q,p,q'$ as shown in Figure~\ref{auto5}(a), add the transition(s)
shown in Figure~\ref{auto5}(b).
\begin{figure}
\begin{center}
\input{auto5.pstex_t}
\end{center}
\caption{Converting an NFA to a regular expression.}
\label{auto5}
\end{figure}
(Note that if $p$ does not have a transition leading back to $p$, then
$\beta = \beta^* = \emptystring$.)
After we have considered all such triples, we can
delete state $p$ and transitions related to $p$.
Finally, we obtain Figure~\ref{auto6}, and the final
$\alpha$ is a regular expression for $L(M)$.  $\Box$
\begin{figure}
\begin{center}
\input{auto6.pstex_t}
\end{center}
\caption{The reduced NFA.}
\label{auto6}
\end{figure}
%
% KSN: If you use ``t'', please use ``s'' not ``i''---the figures
% will need changing too.

\bigskip
The
last three theorems underline the importance of the class of regular languages,
since it connects to notions of automata, grammars, patterns, and much else.
However, regular languages and finite automata are not powerful enough to
serve as our model for a modern computer.
Many extremely simple languages cannot be accepted
by DFAs.  For example, $L=\{ xx ~|~ x\in \{0,1\}^* \}$ cannot
be accepted by a DFA.
% 
% One can prove this by counting, or use the
% so-called pumping lemmas, one can also prove this by
% 
%
To show this, we can argue similarly to the ``$L_k$''
languages in Example~\ref{example.ming13} that for any two strings
$y_1 = 0^m 1$ and $y_2 = 0^n 1$ with $n \neq m$, a hypothetical DFA
$M$ would need to be in a different state after processing $y_1$ from
that after $y_2$, because with $z = 0^m 1$ it would need to
accept $y_1 z$ and reject $y_2 z$.  However, in this case we would
conclude that $M$ needs {\em infinitely\/} many states, contradicting
the definition of a {\em finite\/} automaton.
Hence the language $L$ is not regular.
Other ways to prove assertions of this kind include so-called
``pumping lemmas'' or a direct argument that some strings $y$  
contain more information than a {\it finite}
state machine can {\it remember}~\cite{LV}. We refer the interested 
readers to Chapter 31 and textbooks such as~\cite{HU79}, \cite{gurari}, 
\cite{wood}, and \cite{floyd}.

One can also try to generalize the DFA to allow the input head to 
move backwards as well as forwards, in order to review earlier parts of the
input string, while keeping it read-only.
However, such ``two-way DFAs'' are not
more powerful---they can be simulated by normal DFAs.
The point of departure for a more-powerful model is to allow
the machine to {\em write\/} on its tape and later review what
it has written.  Then the tape becomes a {\em storage\/} medium,
not just a sequence of events to react to.
This ability to write down intermediate
results for future reference makes DFAs into full-blown general-purpose
computers.

\subsection{Turing Machines}\label{sub.tur}

A {\bf Turing machine} (TM),
pictured in Figure~\ref{turing.machine.picture},
consists of a {\it finite control\/},
an infinite {\it tape\/} divided into cells,
and a read/write {\it head\/} on
the tape.  The finite control can be in any one of a finite set 
$Q$ of states.   
Each cell can contain one symbol from the {\em tape alphabet\/}
$\Gamma$, which contains the {\em input alphabet\/} $\Sigma$ and
a special character $B$ called the {\em blank\/}.
$\Gamma$ may contain other characters besides $B$ and
those in $\Sigma$, but most often $\Sigma = \{0,1\}$ and
$\Gamma = \{0,1,B\}$.
We refer to the two directions on the tape as {\it left\/} and 
{\it right\/}, and abbreviate them by $L$ and $R$.
At any time, the head is positioned over a particular cell
that it is said to {\it scan\/}.
Initially, the head scans a distinguished cell
on the tape called the {\it start cell}, 
the finite control is in the start state $q_0$, and 
all cells contain $B$
except for a contiguous finite sequence of cells, extending
from the start cell to the right, that contain characters in $\Sigma$.
These cells hold the {\em input string\/} $x$; in case $x = \emptystring$
the whole tape is blank.
The machine is said to begin its computation on input $x$
at time $0$, and computation unfolds in discrete time steps
numbered $1,2,\dots$
\begin{figure}[b]
    \epsfxsize=3in
    %\epsfysize=5in
%%%    \centerline{\epsfbox{tm.ps}}
    \caption{A Turing machine.}
\label{turing.machine.picture}
\end{figure}


In any step, contingent on its current state and the character
being scanned, the device is allowed to
perform one the following two basic operations:
\begin{enumerate}
\item
write a symbol from the tape alphabet
$\Gamma$ into the scanned cell, or
\item
shift the head one cell left or right.
%\item
%it can change its current state.
\end{enumerate}
Then it may change its internal state in the same step.  The allowed
actions of a particular machine are specified by a finite set
$\delta$ of {\em instructions\/}.
%
% KSN: I think the analogy to ``rules'' of a grammar is much less
% helpful than the analogy to instructions in a program, which
% supports your "GOTO" language anyway!  And $\delta$ is consistent
% with the above DFA nomenclature and with most people's usage.
%
Each instruction has the form $(q,c,d,r)$ with
$q,r \in Q$, $c \in \Gamma$, and either $d \in \Gamma$ or
$d \in \{L,R\}$.  This means that if the machine is in state
$q$ scanning character $c$ on the tape, it may either
change $c$ to $d$ (if $d \in \Gamma$) or move its head
(if $d \in \{L,R\}$), and it enters state $r$.  Either $c = d$
or $q = r$ is allowed.
(Many texts use an alternate formalism in which {\em both\/} basic
operations may be performed in the same step, so that instructions
have the form $(q,c,d,D,r)$ with $q,r \in Q$, $c,d \in \Gamma$, and
$D \in \{L,R\}$, sometimes adding the option $D = S$ of keeping
the head stationary.  The differences do not matter for our purposes.)

If for every combination of $q$ and $c$ there is at most
one instruction $(q,c,d,r)$ that the machine can execute,
then the machine is {\em deterministic\/}.
Otherwise, the machine is {\em nondeterministic}.
In order for computations to possibly halt, there must be some
combinations $q,c$ for which $\delta$ has {\em no\/}
instruction $(q,c,d,r)$.
If a computation reaches such a state $q$ while scanning $c$,
the device is said to {\em halt\/}.
Then if $q$ is designated as a final state, we say the
machine {\em accepts\/} its input string $x$; if $q$ is not 
a final state, we say that the machine {\it rejects\/} the input.
We adopt the convention that there is only one
final state labeled $q_f$, and that $q_f$ is also a halting state,
meaning that there is no instruction $(q,c,d,r)$ with
source state $q = q_f$ at all.


\begin{definition}\label{def.ming3}
\rm
A {\bf Turing machine} is a 7-tuple $M=(Q,\Sigma,\Gamma,\delta,B,q_0,q_f)$,
where each of the components has been described above.
\end{definition}

Given an input
$x$, a deterministic Turing machine $M$ carries out a uniquely
determined succession of operations, 
which may or may not terminate in a finite number of steps.
If it terminates, then the {\em output\/} $M(x)$ is determined
to be the longest string of characters over $\Sigma$ beginning
in the cell in which the head halted and extending to the right.
(If the scanned cell holds $B$ or some other character in
$\Gamma \setminus \Sigma$, then the output is $\emptystring$.)
A function $f: \Sigma^* \rightarrow \Sigma^*$ is {\bf computable}
if there is a Turing machine $M$ such that for all inputs
$x \in \Sigma^*$, $M(x) = f(x)$.
%
% The original text had: "If it terminates, then the
% non-blank symbols left on the tape
% are the output. Given an input, a nondeterministic Turing machine..."
% Even with the simplifying assumption of alphabet 0,1,B, this
% still had the problem of multiple islands of non-blank cells.
% A paragraph break was also needed at "Given".  --KSN
%% The change is fine.

A nondeterministic Turing machine
is analogous to an NFA. One may imagine that it carries
out its computation in parallel. The computation may be viewed as
a (possibly infinite) tree, each of whose nodes is labeled by a
configuration of the machine.  A {\em configuration\/} specifies the
current state $q$, the position of the tape head, and the
contents of the tape, including the character $c$ currently
being scanned.
Each node has as many children as there are different instructions
$(q,c,\cdot,\cdot)$ to execute, and each child is the
configuration that results from executing the corresponding
instruction.  
The root of the tree is the starting
configuration of the machine.
If any of the branches
terminates in the final state $q_f$, we say the machine accepts
the input.
Note that this is the same ``benefit of all doubt'' criterion for
acceptance that we discussed above for NFAs.
Note also that a deterministic Turing machine always defines a
``tree'' with a single branch that forms a simple (possibly
infinite) path. 

% A Turing machine {\em accepts} a language $L$
% if $L=\{ w ~:~ \mbox{$M$ accepts $w$}\}$. Furthermore, if $M$
% halts on all inputs, then we say that $L$ is {\it Turing decidable},
% or {\it recursive}. The connection between a recursive language and a
% decidable problem (function) should be clear. 
% Here we refer to {\em a language recognized} by a Turing machine.
% These are two seemingly different ideas, but they are essentially the same. The reason
% is that a function $f$ which maps the set of strings over a
% finite alphabet to $\{0,1\}$ corresponds in a natural
% way to a language $L_f$ over $\Sigma$ defined as: $L_f$ = $\{ x| f(x) =
% 1\}$. Instead of saying that a Turing machine computes a function $f$,
% we say equivalently that it recognizes $L_f$.
% It is that a function $f$ is decidable if and only if $L_f$ is recursive. 
%
% This paragraph did not "sequitur" inside itself or
% with the following theorem.  --KSN

A language $L$ is said to be {\bf recursively enumerable}
({\bf r.e.}) if there is a Turing machine $M$ such that
$L = \{x: M \mbox{\rm ~accepts~} x\}$.
Furthermore, if $M$ is {\em total\/}; i.e., if every computation of $M$
on every input $x$ halts, then $L(M)$ is {\bf recursive}.
These terms reflect an important correspondence between languages
and functions.  For any language $L \subseteq \Sigma^*$, define
the {\em characteristic function\/} $f_L$ by $f_L(x) = 1$ of
$x \in L$, $f(x) = 0$ otherwise.  Then a language $L$ is recursive
if and only if $f_L$ is computable---and computable functions were
originally defined with regard to formalisms that used {\em recursion\/}.
Note that having $L$ be acceptable
by a Turing machine $M$ is {\em not\/} enough for $f_L$ to be computable,
because there may be inputs $x \notin L$ for which the computation
of $M$ on $x$ never halts.

Conversely, given a function $f : \Sigma^* \rightarrow \Sigma^*$,
and letting $\#$ be a new input symbol not in $\Sigma$,
one can define the language
$L_f = \{x\#y : y \mbox{~is an initial segment of~} f(x)\}$.
Recognizing $L_f$ allows one to find successive bits of the 
value $f(x)$.  Hence it is common in the field to identify
function problems with language problems and concentrate on the latter.
A language can also be identified with a property of strings and
with the associated {\bf decision problem} ``given a string $x$,
does $x$ have the property?''  For instance, the problem of
deciding whether a given number is prime is identifiable with the
language of (binary string encodings of) prime numbers.
The problem is {\bf decidable} if the associated language is
recursive, and a total Turing machine accepting the language is said
to {\em decide\/} the problem.
The term ``decidable language'' is a synonym for 
``recursive language,'' and ``recursive function'' is a synonym
for ``computable function.''  A Turing machine $M$ that does not
halt on all inputs computes a {\bf partial recursive} function
(whose domain is a proper subset of $\Sigma^*$), and $L(M)$ is
a {\bf partially decidable} language (or problem, or property).
%
% The wording of this last sentence is vague on whether "partial
% recursive" includes "recursive", but I think that vagueness also
% applies in practice.  I tried to keep this pgh short.  The definition
% of "r.e." originally misplaced at the end of this section was
% simply wrong on exactly this point.  --KSN
%
Any problem or language that is not decidable by a Turing machine
is called {\bf undecidable}, and any (partial or total) function
that is not computable by a Turing machine is called {\bf uncomputable}.
  
Now when we say that a Turing machine $M'$ {\em simulates\/} another
Turing machine $M$, we usually mean more than saying they accept
the same language or compute the same (partial) function.
Usually there is some overt correspondence between computations
of $M$ and those of $M'$.  This is so in the simulations claimed
by the following theorem, which says that many variations in the
basic machine model do not alter the notion of computability.

\begin{theorem}\label{theorem.ming5}
All the following generalizations of Turing machines can be simulated
by the one-tape deterministic Turing machine model defined in
Definition~\ref{def.ming3}, with tape alphabet $\{0,1,B\}$.
\begin{itemize}
\item
enlarging the tape alphabet $\Gamma$;
\item
adding more tapes;
% adding more work tapes;  KSN: "work tape" wasn't previously defined.
\item
adding more read/write heads or other access points on each tape;
\item
having two- or higher-dimensional grids in place of tapes,
where the head may move to any adjacent grid cell;
\item
allowing nondeterminism.
\end{itemize}
\end{theorem}

Extra tapes after the input tape are called {\em worktapes\/}
provided they allow read-write access.
A two-tape Turing machine, or alternately a one-tape machine with two
heads, has instructions
with six components:\ current state, two characters read by 
the heads, two head actions, next state.
Although these generalizations do not make a Turing machine 
compute more, they do make Turing machines more efficient
and easier to program.  Many more variants of Turing machines
have been studied and used in the literature.

Of all the simulations in Theorem~\ref{theorem.ming5}, the last one
needs special comment. A nondeterministic computation
branches like a tree. The easiest way for a deterministic
Turing machine to simulate it is by traversing the tree in a
breadth-first manner, which is the same as trying all possibilities
at any step with nondeterministic choices.  However, even if there are
at most two choices at any step, simulating $n$ steps of the
NTM could take on the order of $2^n$ steps by the DTM.
Whether a more-efficient simulation is possible is bound up with the
famous ``P vs.\ NP'' problem, to be discussed below and in Chapter~33.

\begin{example}\label{ex.ming5}
\rm
A DFA can be regarded as the special case of a Turing machine in which
every instruction moves the head right.
Turing machines
naturally accept more languages than DFAs can. For example,
a Turing machine can accept the non-regular language
$L=\{ xx ~|~ x\in \{0,1\}^* \}$ as follows.  Given an input string
$w \in \{0,1\}^*$:
\begin{itemize}
\item
First find the middle point.
A TM with two tape heads can do this efficiently by
moving one head twice for every move of the other, until the
further-advanced head sees the blank that marks the end of $w$.
This stage can also tell whether $w$ has even or odd length and
immediately {\em reject\/} in the latter case.
\item
Then check whether the scanned characters match while moving both
heads one cell left until the leftmost head sees the blank
to the left of the beginning of $w$.
If all pairs match, {\em accept\/}, else {\em reject\/}.
\end{itemize}
\end{example}

\noindent
For a TM with only one head the strategy is more cumbersome.
One way is to use ``alias'' characters $a$ for $0$ and $b$ for $1$,
aliasing first the leftmost 0/1 character on the tape, then the
%% aliasing first the leftmost 0-1 character on the tape, then the
rightmost, then the next-leftmost,\dots until finding the character
just left of middle (if $w$ has even length).  Then ``un-alias'' it and
check that the rightmost aliased character matches it, un-aliasing
the latter as well.  By looking for cases of an $a$ or $b$ immediately
to the left of an un-aliased $0$ or $1$, the TM can repeat this check
until all of the left half is compared with the right half.
Whereas the two-head TM needs only $3n/2$ steps to decide whether
a string $w$ of length $n$ belongs to $L$, the one-head TM takes
about $n^2$ steps.  It is known that $n^2$ steps 
%% are sufficient for our
%% basic one-head, one-tape model to simulate TMs with any number of
%% heads and tapes, and this many steps 
are necessary (asymptotically) for any one-head TM to accept the 
language $L$ (see, for instance, \cite{HU79} or \cite{LV}).
%
% Authors: Maybe my last two sentences can be deleted here,
% since the point is revisited in the next section.  --KSN   (!!check)
%%
%% Answer: I deleted the first sentence since it's not true. n^2 -> T(n)^2.

Three restrictions of the notion of a Turing machine tape merit
special mention.
\begin{itemize}
\item
A {\em pushdown store\/} 
(or {\em stack\/})
is a semi-infinite worktape with one head such
that each time the head moves to the left, it erases the symbol
scanned previously.  This is a last-in first-out storage.
\item
A {\em queue\/} is a semi-infinite work tape with two heads that
only move to the right, the leading head is write-only and the
trailing head is read-only.  This is a first-in first-out storage.
\item
A {\em counter\/} is a pushdown store with a single-letter alphabet,
except for a special bottom-of-stack marker that allows testing the counter
for zero.  Then a push increments the counter by one, and a pop
decrements it by one.
\end{itemize}

% A machine consisting of a single queue
% can simulate a standard Turing machine.  However, the
% other two types of machines are not powerful enough to simulate a 
% Turing machine.
% KSN: I put this later, not here. 

\begin{example}\label{ex.ming6}
\rm
A {\bf pushdown automaton\/} (PDA) has one read-only input tape and
one pushdown store.
A PDA can be identified with a two-tape Turing machine whose
tape-1 head can never move left and whose tape-2 head can move
left only while scanning a blank (combined with a previous step
that writes a blank, this simulates popping the stack).
\end{example}
  
Pushdown automata have been thoroughly studied because 
nondeterministic PDAs accept precisely
the class of context-free languages, to be defined in
Chapter 31.
% 
% More precisely, 
% it can be shown that if $L$ is a context-free
% language, then it is accepted by a PDA, and if $L$ is accepted 
% by a PDA, then there is a CFG generating $L$.
% KSN: Unnecessary, and the forward reference to "CFG" is cumbersome.
% (But if Ch. 31 came first, I could leave this text in.
%
Various types of PDAs have fundamental applications in compiler design.

The PDA has less power than a Turing machine. For example,
$L=\{ xx ~|~ x\in \{0,1\}^* \}$ cannot be accepted by a PDA, but 
it can be accepted by a Turing machine as in Example~\ref{ex.ming5}.
However, a PDA is more powerful than a DFA. For example, a PDA
can accept the non-regular language $L'=\{ 0^n 1^n ~|~n\geq 0 \}$ easily:
For each initial $0$ read, push a $0$ onto the stack; then pop a $0$
for each $1$ read, and accept if and only if a blank is read after
the block of $1$s exactly when the stack is empty.
Indeed, this PDA is a counter machine with a single counter.

Two pushdown stores can easily be used to simulate a tape---let one
stack represent the part of the tape currently to the left of the
input head, and let the other stack represent the rightward portion.
Much more subtle is the fact that two {\em counters\/} can simulate
a tape; unlike the two-pushdown case this takes exponentially more time.
Finally, a single queue can simulate a tape:\ send the lead head to 
the right end so that it can write the next-step update of the
configuration that the trailing head is reading.  This involves encoding
the current state of the TM being simulated onto the tape of the
queue machine that is simulating it.  Hence a single-queue machine,
with the input initially resting in the queue, is as powerful as a
Turing machine, although it may require the square of the running time.
For comparisons of powers of pushdown stores, queues, counters, and
tapes, see \cite{boas} and \cite{LV}.


%So far, our Turing machines do not really behave like general
%purpose computers since they are designed to do specific tasks
%and they do not take ``programs'' as input.
%
% The idea of the ``universal algorithm'' has already been introduced
% at the outset of this chapter.
% %in Section~\ref{sub.uni}. 
% KSN ^^^^^ which appears to have disappeared, so I took this sentence out.
%
Much more important is the fact that there are single Turing machines
that are capable of simulating {\em any\/} Turing machine. 
Formally, a {\bf universal Turing machine} $U$ takes an encoding 
$\langle M,w \rangle$ of a (deterministic)
Turing machine $M$ and a string $w$ as input, and 
simulates $M$ on input $w$.
$U$ accepts $\langle M,w \rangle$ if and only if $M$ accepts $w$.
Intuitively, $U$ models a general-purpose computer that takes a
``program'' $M$ and ``data'' $w$, and executes $M$ on input $w$.
Universal Turing machines have many applications.  For example, the
definition of Kolmogorov complexity (see ~\cite{LV}) fundamentally relies on
them.

\begin{example}\label{ex.ming8}
\rm
Let $L_u = \{ \langle M,w \rangle ~|~M~\mbox{accepts}~w\}$. Then
$L_u$ is {\em the\/} language
accepted by a universal Turing machine, so it is recursively
enumerable.  We shall see in Chapter~32, however, that $L_u$ is
not recursive.
The same properties hold for the language
$L_h = \{ \langle M,w \rangle : \mbox{$M$ on input $w$ halts}\}$,
which is the language of the so-called {\bf Halting Problem}.

% If a language is Turing acceptable but not Turing decidable, we
% call such a language {\it recursively enumerable}, or {\it r.e.}
% --/Oops/: "Partially decidable" is often taken to imply "not decidable",
% --but "r.e." never is.  See the note above where I took care of this.  
% --I also inserted L_h to improve something in the next section.  --KSN
% Thus $L_u$ is r.e., but not recursive. It is easily seen that if both a
% language and its complement are r.e., then both of them are recursive.
% So $\bar L_u$ is not r.e.
% --Check that I reflected this last sentence in Chapter 32.
\end{example}

\subsection{Oracle Turing Machines}\label{sub.oracle}

In order to study the comparative hardness of computational problems,
we often need to extend the power of Turing machines by
adding oracles to them.

% In formally, a Turing machine $T$ with an {\em oracle} $A$ is denoted
% as $T^A$.
% KSN: T^A is formal notation, and the denoting is not your main point.
%
Informally, a Turing machine $T$ with an {\em oracle\/}
$A$ operates similarly to a
normal Turing machine, with the exception that it can write down
a string $z$ and ask whether $z$ is in the language $A$.
The machine gets the correct yes/no answer from the oracle in one step,
and can branch its computation accordingly.
% 
% An oracle machine can use this feature one or more times during
% each computation.
%
This feature can be used as often as desired.
We now give the definition precisely.

\begin{definition}
\rm
% Let $A$ by a set over $\Sigma$.
% KSN: Better to lead off with the language-independent aspect.
%
An {\bf oracle Turing machine} is a normal
Turing machine $T$ with an extra {\em oracle query tape\/}, a special
state $q_?$, and two distinguished states
labeled $q_y$ and $q_n$.
Let $A$ be any language over an alphabet $\Sigma$.
Whenever $T$ enters state $q_?$ with some string $z \in \Sigma^*$
on the query tape,
control passes to state $q_y$ if $z \in A$, or to $q_n$ if $z \notin A$.
The computation continues
normally until the next time the machine enters $q_?$.
The machine $T$ with a given choice of oracle $A$ is denoted by $T^A$.
\end{definition}

\begin{example}\label{ex.ming.new1}
\rm
In Example~\ref{ex.ming8}, we know that the universal language
$L_u = \{ \langle M,w \rangle ~|~M~\mbox{accepts}~w\}$
is not Turing decidable. But if we can use $L_u$ as the oracle set,
there is a trivial oracle TM $T$ such that $T$ with oracle $L_u$
decides $L_u$.  $T$ simply copies its input $x$ onto the query tape and
enters $q_?$.  If control passes to $q_y$, $T$ accepts; otherwise
from $q_n$ it rejects.

For something less trivial, suppose we have
$L_h = \{ \langle M,w \rangle : \mbox{$M$ on input $w$ halts}\}$
as the oracle set.  Given a (non-oracle) Turing machine $M$,
there is a standard way to modify $M$ to the
code of an equivalent Turing machine $M'$ in which the accepting
state $q_f$ is the only place where $M'$ can halt.  This is done by
making every other combination $q,c$ where $M$ might halt send control
to an extra state that causes an infinite loop.  Thus $M'$ halts on $w$
if and only if $M$ accepts $w$.  Now design an oracle Turing machine $T'$
that on any input $x$ of the form $\langle M,w \rangle$
(rejecting if $x$ does not have the form) writes
$x' = \langle M',w \rangle$ on the query tape and enters $q_?$,
accepting if control goes to $q_y$ and rejecting from $q_n$.
Then $T'$ with oracle set $L_h$ decides whether $x \in L_u$,
since $x \in L_u \iff x' \in L_h$.  This is a
simple case where an oracle for
one problem helps one decide a different problem.
\end{example}

A language $A$ is {\bf Turing-reducible} to a
language $B$, written $A \leq_T B$,
if there is an oracle Turing machine that with oracle $B$ decides $A$.
For example, we have just shown that $L_u \leq_T L_h$.
%
% It is also not hard to see that $L_h \leq_T L_u$, so that
% $L_u$ and $L_h$ are {\em Turing equivalent\/}.
%
The important special case in which the oracle TM $T$ makes exactly
one query, accepting from $q_y$ and rejecting from $q_n$, gets
its own notation:\ $A \leq_m B$.  Equivalently, $A \leq_m B$ if
there is a computable function $f$ such that for all $x \in \Sigma^*$,
$x \in A \iff f(x) \in B$.  The function $f$ represents the computation
done by $T$ prior to making the sole query.  This case is called
a {\bf many-one reduction} (hence the subscript ``$m$'') for the
arcane historical reason that $f$ need not be a one-to-one function.
The term ``many-one reduction'' is standard now.
The above example actually shows that $L_u \leq_m L_h$.
It is not hard to show that also $L_h \leq_m L_u$, so that the
Halting Problem and the membership problem for a universal Turing machine
are {\em many-one equivalent\/}.


\subsection{Alternating Turing Machines}\label{alternating}

Turing machines can be naturally generalized to model
parallel computation. A nondeterministic Turing machine accepts an input if
there exists a move sequence leading to acceptance. We can call 
%
% such a state
% What state?  --KSN
%
any nondeterministic state entered along this sequence
an {\em existential state\/}. We can naturally add another type
of state, a {\em universal state\/}. When a machine enters
a universal state, the machine will accept if and only if 
{\em all\/} moves from this state lead to acceptance.
These machines are called {\bf alternating Turing machines}. 

Let us describe the computation of alternating Turing machines formally and precisely.
An alternating Turing machine is simply a nondeterministic Turing machine with the 
extra power that some states can be universal.
A {\em configuration\/} of an alternating Turing machine $A$
has the same form as was described for a deterministic Turing machine,
namely:
\begin{verbatim}
           (current state, tape contents, head positions).
\end{verbatim}
We write
\[
\alpha \vdash \beta
\]
if, in one step, $A$ 
%
% moves
% KSN: A can be nondeterministic.  Punctuation was wrong, too.
%
can move
from configuration $\alpha$ to configuration $\beta$.
A configuration with current state $q$ is {\em accepting\/} if
\begin{itemize}
\item
$q$ is an accepting state (i.e., $q = q_f$); or
\item
$q$ is existential, and
there exists
an accepting configuration $\beta$ such that $\alpha \vdash \beta$; or
\item
$q$ is universal, and
or each configuration
$\beta$ such that $\alpha \vdash \beta$, $\beta$ is an accepting configuration.
\end{itemize}
This definition may seem circular, but by working backwards from
configurations with $q_f$ in the current-state field, one may verify
that it inductively defines the set of accepting configurations
in a natural manner.  
Then $A$ accepts an input $x$ if its initial configuration
(with current state $q_0$, $x$ on the input tape, heads at 
initial positions) is accepting.

Alternating Turing machines were first proposed by
\cite{CKS81} for the purpose of
modeling parallel computation. In order to allow sub-linear computation
times, a random-access model is used to read the input. When in a
special ``read'' state, the alternating Turing machine
is allowed to write a number in binary which is then interpreted
as the address of a location on the input tape, whose symbol
is then read in unit time.
By using universal states to relate different branches of
the computation, one can effectively read the whole
input in as little as logarithmic time. 

Just as a nondeterministic Turing machine is a model
for solitaire games,
an alternating Turing machine is a model for general two-person games.
Alternating Turing machines have been successfully
used to provide a theoretical
foundation of parallel computation as well as to establish the
complexity of
various two person games.
For example, a chess position with White to move can be modeled from
White's point of view as a configuration $\alpha$ whose first
component is an existential state.  The position is winning if there
exists a move for White such that the resulting position $\beta$
is winning.  Here $\beta$ with Black to move has a universal
state $q$, and is a winning position (for White) if and only if 
either Black is checkmated (this is the base case $q = q_f$) or for all
moves by Black to a position $\gamma$, $\gamma$ is a winning
position for White\dots
Chapter~34, Sections 5--6, will demonstrate the significance
of games for time and space complexity, to which we now turn.      

\section{Time and Space Complexity}\label{subsub.tim}
With Turing machines, we can now formally define what we mean by time
and space complexity. The formal investigation by
%
% Hartmanis and Stearns~\cite{HS} and Blum~\cite{blum}
% KSN: The CRC style guidelines give a green light to referring to
% papers as though they were people.  Here at any rate it is even OK
% to say that the investigation was "by" the papers, so I changed it.
% Above with CKS, where the "named" bibstyle puts "Chandra et. al",
% I left all the names in front as you had it.  I'm sure the CRC editors
% will sort this out.
%
\cite{HS} and \cite{blum}
in the 1960's marked the beginning 
of the field of {\em computational complexity\/}. 
%We refer the readers to Hartmanis' Turing Award lecture~\cite{hartmanis}
%for an interesting account on the history and the future of this field. 

% To define the space complexity properly (in the sub-linear case), we
% need to slightly modify the Turing machine of
% Figure~\ref{turing.machine.picture}.  We will replace
% the tape containing the input by a read-only input tape
% and give the machine some extra work tapes.
%
% KSN: The use of future tense promised something more.  You also
% neglected to say /why/ you are doing this.  And this was wordy,
% with "sub-linear case" (of /what/?) rather cryptic.

An important point with space complexity is that a machine
should be charged only for those cells it uses for calculation,
and not for read-only input, which might be provided on 
cheaper non-writable media such as CD-ROM or 
accessed piecemeal over a network. 
Hence we modify the Turing machine of
Figure~\ref{turing.machine.picture} by making
the tape containing the input read-only,
and giving it one or more worktapes.



\begin{definition}\label{def.ming9}
\rm
Let $M$ be a Turing machine. If for all $n$, every sequence of
legal moves on an input $x$ of length $n$ halts within $t(n)$ steps, 
we say that $M$ is
of {\bf time complexity} $t(n)$.
Similarly, if every such sequence uses at most $s(n)$
{\em worktape\/} cells, then $M$ is of {\bf space complexity} $s(n)$.
\end{definition}
%
% KSN: space complexity wasn't italicized, the sentence was run-on, etc.
% My wording removes the need for special mention of nondeterminism.
% /Possibly/ the first sentence of the next result should be rewritten to
% rule out the chance of someone wondering if the first TM can be
% an NTM and the second a DTM, but I think it's OK.

\begin{theorem}\label{theorem.ming7}
Fix a number $c > 0$, a space bound $s(n)$, and a time bound $t(n)$.
\begin{itemize}
\item[(a)]
Any Turing machine of $s(n)$ space complexity,
using any number of tapes or grids of any dimension, 
can be simulated by a Turing
machine with a single (one-dimensional) worktape
%
% in $s(n)$ space.
% Oops, this wasn't true under the original TM definition given
% by the authors, since it fixed the tape alphabet to be {0,1,B}.
% Also originally one branch said "can be simulated by" and the
% other said "language...also accepted by", inconsistent.
% Note that I /defined/ "simulate" above.  --KSN 
%
%% Thanks for the correction.
that has space complexity $s(n)/c$.
\item[(b)]
Any Turing machine of $t(n)$ time complexity can be simulated by
a Turing machine, with the same number and kinds of worktapes,
that has time complexity $n + t(n)/c$.
\end{itemize}
\end{theorem}

The proof of these so-called {\em linear speed-up theorems\/}
involves enlarging the original TM's worktape alphabet $\Gamma$ to an
alphabet $\Gamma'$ large enough that one character in $\Gamma'$
can encode a block of $c$ consecutive 
characters on a tape of the original machine (see \cite{HU79}).  The extra
``$n+$'' in the time for part (b) is needed to read and translate
the input into the ``compressed'' alphabet $\Gamma'$.
If we think of memory in units of bits the idea that this saves space
and time is illusory, but if we regard the machine with $\Gamma'$ as
having a larger {\em word size\/}, the savings make sense.
Definition~\ref{def.ming9} is phrased in a way that applies also
to nondeterministic and alternating TMs, and the two statements in
Theorem~\ref{theorem.ming7} hold for them as well.
%
% KSN: Actually, for t(n)=O(n) one gets the stronger statement
% that they can run in real time, i.e. time n+1, but I don't think
% this result of Book-Greibach-Wegbreit needs to be cited.

In Theorem~\ref{theorem.ming7}, if $s(n) \geq n$, then we do not need to
separate the input tape from the worktape(s).  For any Turing machine $M$
of linear space complexity, part (a) implies that we can simulate $M$ by a
one-tape TM $M'$ that on any input $x$ uses only the cells
initially occupied by $x$ (except for one visit to the blank cell
to the right of $x$ to tell where $x$ ends).
Then $M'$ is called a {\em linear bounded automaton\/}.

The main import and convenience of Theorem~\ref{theorem.ming7}
is that one does not need to use ``$O()$-notation'' to define
complexity classes:\ space complexity $O(s(n))$ is no different from
space complexity $s(n)$, and similarly for time.
% 
% ---except in the linear
% case where time $O(n)$ equals time $(1+\epsilon)n$ for any
% $\epsilon > 0$, but is different from time $n+1$.
% People often refer to time $O(n)$ as ``time $n$'' anyway. 
% KSN: I took care of this neatly in Example 3.1.
%
As we shall see, it is not always possible to reduce the number
of tapes and run in the same time complexity, so researchers have
settled on Turing machines with any finite number of
tapes as the bench model for time complexity.  

\begin{definition}\label{def.ming10}
\rm
% \begin{description}
% \item[ ]
% KSN: CRC guidelines asked for bullets when items need not be labeled.
% Deleting "O(t(n))" etc. is consistent with the Allender chapters.
%
\begin{itemize}
\item
${\rm DTIME}[t(n)]$ is the class
of languages accepted by multi-tape
deterministic TMs in time $t(n)$;
\item
${\rm NTIME}[t(n)]$ is the class of languages accepted by 
multi-tape
nondeterministic TMs in time $t(n)$;
\item
${\rm DSPACE}[s(n)]$ is the class of languages accepted by 
deterministic TMs in space $s(n)$;
\item
${\rm NSPACE}[s(n)]$ is the class of languages accepted by multitape
nondeterministic TMs in space $O(s(n))$;
\item
P is the complexity class  $\bigcup_{c \in {\cal N}} {\rm DTIME}[n^c]$;
\item
NP is the complexity class  $\bigcup_{c \in {\cal N}} {\rm NTIME}[n^c]$;
\item
PSPACE is the complexity class $ \bigcup_{c \in {\cal N}} {\rm DSPACE}[n^c]$;
\item
${\rm ATIME}[s(n),t(n)]$ is the class of languages accepted by alternating
Turing machines operating simultaneously in time $t(n)$
and space $s(n)$.
% \end{description}
\end{itemize}
\end{definition}

\begin{example}\label{ex.ming10}
\rm
In Example~\ref{ex.ming5} we demonstrated how the language
$L=\{ xx ~|~ x\in \{0,1\}^* \}$ can be decided by a Turing machine.
We gave a two-head, one-tape TM running in time $3n/2$, and 
it is easy to design a two-tape, one-head-per-tape TM that
executes the same strategy in time $2n$.
Theorem~\ref{theorem.ming7} says that by using a larger tape alphabet,
one can push the time down to $(1+\epsilon)n$
for any fixed $\epsilon > 0$.
%
% KSN: I wonder if $L$ is known not to be real-time solvable on a
% multitape TM; I know the palindromes /are/.  (!!check)?
%
%% Answer: I don't know. It seems unlikely.
However, our basic one-tape, one-head Turing machine model can do
no better than time on the order of $n^2$.
\end{example}
 
% It should be clear that any language that can be accepted by a DFA or
% an NFA can be accepted by a Turing machine in $O(n)$ time,
% with no storage space needed at all.
%
% % The Type-1 grammar as defined in Chapter 31
% % %in Definition~\ref{tao.def16} 
% % can be accepted by a Turing machine in $O(n)$ space.
% % KSN: Oops, you seem to mean DSPACE[O(n)] here.  And it's
% % not the /grammar/ that's being accepted...
% %
% Languages in P, that is, languages acceptable by Turing machines
% in {\em polynomial} time, are considered as {\em feasibly} computable.
% It is important to point out that all generalizations of the Turing
% machine, except the nondeterministic version, can all be simulated
% by the basic one-tape deterministic Turing machine in with at most
% polynomial slow down. 
% These generalizations include for example 2-dimensional tapes,
% $k$-tapes, more than one head on each tape, and so on.
% For example, a two-tape deterministic Turing
% machine can be simulated a one-tape deterministic Turing machine
% with quadratic slow down.
%
% KSN: This disjointed paragraph breaks the flow of the examples, and
% most of it is covered by things I inserted above or below or by things
% in Allender-Loui-Regan's Chapter 33.  Plus it was hard to fix. 

\begin{example}\label{two_tapes_to_one}
\rm
{\em Any\/} multi-tape, multi-head Turing machine, not just the
one accepting $L$ in the last example, can be simulated
by our basic one-tape, one-head model in at most the square
of the original's running time.  For example, a two-tape machine $M$
with tape alphabet $\Gamma$ can be simulated by a one-tape machine $M'$
with a $\Gamma'$ large enough to encode
all pairs of characters over $\Gamma$.
Then $M'$ can regard its single tape as having two ``tracks,'' one for
each tape of $M$.  $M'$ also needs to mark the locations of the
two heads of $M$, one on each track---this can be facilitated by
adding more characters to $\Gamma'$.
Now to simulate one step of $M$, the one-tape machine $M'$ must
use its single head to update the computation at the two
locations with the two head markers.  If $M$ runs in time $t(n)$,
then the two head markers cannot be more than $t(n)$ cells apart.
Thus to simulate each step by $M$, $M'$ moves its head for at most
$t(n)$ distance.  Hence $M'$ runs in time at most $t(n)^2$.
%
% This pgh was easier to retype than to fix.
\end{example}

The simulation idea in Example~\ref{two_tapes_to_one} does not work
if $M$ uses two- or higher-dimensional tapes,
or a more-general ``random-access'' storage (see the next section).
However, a one-tape $M'$ can be built to simulate it whose
running time is still no worse than a polynomial in the time of $M$.
It is important to note that our basic one-tape deterministic 
Turing machine is known to simulate all of the extended models
we offer above and below---except
nondeterministic and alternating TMs---with at most polynomial slowdown.
This is a key point in taking the class P,
defined as above in terms of Turing machine time, as the benchmark for
which languages and functions are considered
{\em feasibly computable\/} for general computation.
(See Chapter~33 for more discussion of this point.)
Polynomial time for nondeterministic Turing machines defines the
class NP.
Interestingly, polynomial space for nondeterministic TMs does equal
polynomial space for deterministic TMs \cite{savitch}, and 
polynomial {\em time\/} for {\em alternating\/} TMs equals the
same class, namely PSPACE.


\begin{example}
\rm
All of the basic arithmetical operations---plus, minus, times,
and division---belong to P.
Given two $n$-digit integers $x$ and $y$,
we can easily add or subtract them
in $O(n)$
steps.  We can multiply or divide them in $O(n^2)$ 
steps using the standard algorithms learned in school.
Actually, by grouping blocks of digits
in $x$ and $y$ and using 
some clever tricks one can bring the time down to $O(n^{1+\epsilon})$
bit-operations
for any desired fixed $\epsilon > 0$, and the asymptotically fastest
method known takes time $O(n\log n \log\!\log n)$~\cite{schonhage1}.
%
% Editor, authors: This insertion by me needs a reference.
% Does the numerical-complexity chapter mention it?
% [Aho, Hopcroft, Ullman, 1974] has a nice treatment, but it's old.  --KSN
%
%% Answer: As far as we know the bound is still the best, and the reference is:
%%   Schoenhage, A., and V. Strassen [1971]. "Schnelle Multiplikation
%%   grosser Zahlen", Computing 7, pp. 281-292.
Computing $x^y$ is technically not in P because the
sheer length of the output may be exponential in $n$,
but if we measure time as a function of output length as
well as input length, it is in P.
However, the operation of {\em factoring\/} a number into primes,
which is a kind of inverse of multiplication, is commonly
believed {\em not\/} to belong to P.
The language associated to the factoring function
(refer to ``$L_f$'' before Theorem~\ref{theorem.ming5} above) 
does belong to NP.
\end{example}

\begin{example}
\rm
There are many 
other important problems in NP that are not known to be in P. 
For example, consider the following ``King Arthur'' problem,
which is equivalent to the problem called
{\sc Hamiltonian Circuit} in Chapter~34.  King Arthur
plans to have a round table meeting.
By one historical account he had 150 knights, so let $n = 150$.
It is known that some pairs of
knights hate each other, and some do not. King Arthur's problem
is to arrange the knights around the table so that no pair of
knights who sit side by side hate each other.
King Arthur can solve this problem by enumerating all possible
permutations of $n$ knights. But even at $n=150$, there are
$150!$ permutations. All the computers in the whole world,
even if they started a thousand years ago and worked non-stop,
would still be going on
today, having examined only a tiny fraction of the
$150!$ permutations.  However,
% 
% it is obvious that such a
% KSN: Ever since Galois' frequent use of "il est aise' de voir..."
% got himself shot, it has been good advice to avoid these words.
%
this problem is in NP because a nondeterministic Turing
machine can just guess an arrangement and verify the correctness
of the solution---by checking if any two neighboring
knights are enemies---in polynomial time. It is currently
unknown if every problem in NP is also in P. This problem has a special 
property---namely, if it is in P then every problem in NP is also in P.
\end{example}

The following relationships are true:
\[
{\rm P} \subseteq {\rm NP} \subseteq {\rm PSPACE}.
\]

Whether or not either of the above inclusions is proper
is one of the most fundamental open questions in
computer science and mathematics.
Research in computational complexity theory
centers around these questions. 
% 
% In order to solve these problems,
% KSN: this confuses the reader on "problem" vs. "question"...
%
The first step in working on these questions is to
identify the hardest problems in NP or PSPACE. 

\begin{definition}
\rm
Given two languages $A$ and $B$ over an alphabet $\Sigma$,
a function $f: \Sigma^* \rightarrow \Sigma^*$ is called
a {\bf polynomial-time many-one reduction} from $A$ to $B$ if
\begin{itemize}
\item[(a)]
$f$ is polynomial-time computable, and
\item[(b)]
for all $x \in \Sigma^*$, $x \in A$ if and only if $f(x) \in B$.
\end{itemize}
One also writes $A \leq_m^p B$.
\end{definition}

The only change from the definition of ``many-one reduction''
at the end of Section~\ref{sub.oracle} is that we have
inserted ``polynomial-time'' before ``computable.''
There is also a polynomial-time version of Turing reducibility
as defined there, which gets the notation $A \leq_T^p B$.

\begin{definition}
\rm
A language $B$ is called {\bf NP-complete} if
% and only if
% KSN: Standard style is that this is not necessary in a definition. 
\begin{enumerate}
\item
$B$ is in NP;
\item
for every language $A \in {\rm NP}$, $A \leq_m^p B$.
% 
% there is a polynomial many-one reduction from $L_2$ to $L_1$
% KSN: Might as well /use/ the "\leq_m" notation, which you 
% defined in the earlier section to begin with.  I want to lend weight to
% making the "\leq_m^p" notation standard, and the Allender chapters
% use it in this Handbook.  Your earlier section also used "A" and "B";
% why use a letter and a subscript here when one letter will do?   
\end{enumerate}
\end{definition}

In this definition, if only the second item holds, then we say
the language $B$ is {\em NP-hard\/}.
(Curiously, while ``NP-complete'' is always taken to refer by
default to polynomial-time many-one reductions, ``NP-hard'' is
usually extended to refer to polynomial-time Turing reductions.)
The upshot is that
if a language $B$ is NP-complete and $B$ is in P,
then ${\rm NP} = {\rm P}$.
An NP-complete language is in this sense a hardest language in
the class NP.
Working independently,
Cook \cite{cook1} and Levin \cite{levin}
introduced NP-completeness, and Karp \cite{karp1}
further demonstrated its importance.
%
% Editor: Here's a case where the CRC guideline about only having the
% name inside [...] looks wrong to me, although this does too...  --KSN
% 
PSPACE and other classes also have complete languages.

Chapters 33 and 34 of this {\em Handbook\/} develop the topics
of this section in much greater detail.  We also refer the
interested reader to the
textbooks~\cite{yap}, \cite{HU79}, \cite{wood}, \cite{lewis}
and \cite{floyd}.


\section{Other Computing Models}\label{subsub.oth}
Over the years, many alternative computing models have been proposed.
Under reasonable definitions of running time
for these models, they can all be simulated by
Turing machines 
with at most a polynomial slow-down. The reference \cite{boas}
provides a nice survey of various computing models other than
Turing machines. We will discuss a few such
alternatives very briefly and refer our readers to
Chapter 48 and \cite{boas} for more information.

\subsection{Random Access Machines}\label{sub.ram}
The {\em Random Access Machine}~\cite{cook} consists of a
finite control where a program is stored, several
arithmetic registers, and an infinite collection of memory registers
$R[1],R[2], \ldots $
All registers have an unbounded word length.
The basic instructions for the program are
LOAD, STORE, ADD, 
%
% MULT,
% "MUL" is a more-standard name for it. --KSN
% Oops, you also need to mention conditional-branch instructions.
%
MUL, GOTO, and conditional-branch instructions.
%
% STORE, GOTO, ACCEPT, REJECT, etc.
% Indirect addressing is also used.
%
The LOAD and STORE commands can use indirect addressing. 
Compared to Turing machines,
this appears to be a closer but more complicated approximation
of modern computers. 
There are two standard ways for measuring time complexity
of the model:
\begin{itemize}
\item
The {\it Unit-cost RAM}: Here
each instruction takes one unit of time, no matter how big
the operands are. This measure is convenient for analyzing
%
% some algorithms such as sorting. But it is unrealistic 
% or even meaningless for analyzing some other algorithms, such
% as integer multiplication.
% KSN: Just say,
%
many algorithms.
\item
The {\it Log-cost RAM}: Here each instruction is charged for the sum of
the lengths of all data manipulated
%
% implicitly or explicitly   %% KSN: why needed?
% 
by the instruction. 
Equivalently, each use of an integer $i$ is charged
$\log i$ time units, since $\log i$ is approximately the length of $i$.
This is a more realistic model, but sometimes
less convenient to use.
\end{itemize}

Log-cost RAMs and Turing machines can simulate each
other with polynomial overheads. The unit-cost assumption becomes
unrealistic when the MUL instruction is used repeatedly to
form exponentially large numbers.  Taking MUL out, however,
makes the unit-cost RAM polynomially equivalent to the Turing machine
as well.


\subsection{Pointer Machines}
Pointer machines were introduced by 
%
% Kolmogorov and Uspenskii
% KSN: three mentions of their names were too much; maybe you can
% restore one.  Note that Scho"nhage's model is a little different.
%
\cite{kolmogorov} in 1958
% 
% (also known as the Kolmogorov-Uspenskii machine)
% 
and in modified form
by Sch\"onhage
%
% in 1970
% KSN: how do you know the exact year without a reference?  Ten years
% to the journal paper makes me think he refined it along the way.
%
in the 1970s.
Sch\"onhage called his form the ``storage modification machine''
\cite{schonhage}, and both forms are sometimes named for their authors. 
We informally describe Sch{\"o}nhage's form here here.
%
% A pointer machine is similar to a RAM but
% differs in its memory structure.
% %The memory of a RAM consists of an (infinite) array of cells.
% A pointer machine operates on a storage structure called
% a $\Delta$-structure, where $\Delta$ is a finite alphabet
% of size greater than one.
%
A pointer machine is similar to a RAM, but instead of having an
unbounded array of registers for its memory structure, it has
modifiable pointer links that form a {\em $\Delta$-structure\/}.
A $\Delta$-structure $S$, for a finite alphabet $\Delta$ of size $k$,
is a finite directed graph in which each node has $k$ out-edges labeled
by the $k$ symbols in $\Delta$.
%
% (the Kolmogorov-Uspenskii version is an undirected graph)
% KSN: Cleaner to leave this out.
%
Every node also has a cell holding an integer, as with a RAM.
At every step of the computation, one node of $S$ is distinguished
as the {\it center\/}, which acts as a starting point for
addressing.
A word $w \in \Delta^*$ addresses the cell of the node formed by
following the path of pointer links selected by the 
successive characters in $w$.
Besides having all the RAM instructions,
the pointer machine has various instructions and rules for
moving its center and
redirecting pointer links, thus modifying the storage structure.
%
% KSN: I was tempted to make an allusion to Java VMs here.
%
Under the log-cost criterion, pointer machines are
polynomially equivalent to RAMs and Turing machines.
There are many interesting studies on the precise efficiency of the 
simulations among these models, and we refer to the reader
to the survey \cite{boas} as a center for further pointers on them.
%
% A subtler pun than "pointers on pointer machines".
 

\subsection{Circuits and Nonuniform Models}
A {\it Boolean circuit} is a finite, labeled, directed
acyclic graph. Input nodes are nodes without ancestors; they are
labeled with input variables $x_1, \ldots , x_n$.
The internal nodes are labeled with functions from a finite set
of Boolean operations
%
%, for example $\{{\rm and},{\rm or},{\rm not} \}$ or
% $\{ \oplus \}$.
% KSN: Something bothered me about the latter being an incomplete set.
% Reference to NAND mirrors Chapter 33, also.
%
such as $\{$AND, OR, NOT$\}$ or $\{$NAND$\}$.
The number of ancestors of an internal
node is precisely the number of arguments of the Boolean function
that the node is labeled with. A node without successors is
an output node. The circuit is naturally evaluated from input to
output: at each node the function labeling the node is evaluated
using the results of its ancestors as arguments.
Two cost measures for the circuit model are
\begin{itemize}
\item
{\em depth}: the length of a longest path from an input node to an
output node.
\item
{\em size}: the number of nodes in the circuit.
\end{itemize}
These measures are applied to a family
$\{ C_n ~|~ n\geq 1 \}$ of circuits for a particular problem,
where $C_n$ solves the problem of size $n$.
%
% If $C_n$ can be computed from $n$ (in polynomial time),
% then this is a {\it uniform measure}. Such circuit families
% are equivalent to Turing machines. If $C_n$ cannot
% be computed from $n$, then such measures are
% {\it nonuniform} measures, and such classes of circuits are
% more powerful than Turing machines since they simply can compute
% any function by encoding the solutions of all 
% inputs for each $n$.
% KSN: This is more likely to confuse readers here.
%
Subject to the {\em uniformity condition\/} that the layout of
$C_n$ be computable given $n$ (in time polynomial in $n$),
circuits are (polynomially) equivalent to Turing machines.
Chapters 33 and 48 give full presentations of circuit complexity, while
\cite{boas} and \cite{Karp} have more 
details and pointers to the literature.

\section{Defining Terms}\label{terms}

{\bf alternating Turing machine:} a generalization of a nondeterministic
Turing machine. In the latter, every state can be called
an existential state since the machine accepts if one of the possible moves
leads to acceptance.  In an alternating Turing machine there are also
universal states, from which the machine
accepts only if all possible moves out of that state lead to acceptance.

\noindent
{\bf algorithm}: a finite sequence of instructions that is supposed to
solve a particular problem.
%
% This identifies "algorithm" with "program", which some will decry.
% But it's OK with me to let it pass.  --KSN

\noindent
{\bf complexity class NP:} the class of languages that can be accepted
by a nondeterministic Turing machine in polynomial time.

\noindent
{\bf complexity class P:} the class of languages that can be accepted
by a deterministic Turing machine in polynomial time.
%
% I felt inserting "deterministic" was needed here, but not next.  --KSN

\noindent
{\bf complexity class PSPACE:} the class of languages that can be accepted
by a Turing machine in polynomial space.

\noindent
{\bf computable function}:
a function that can be computed by an algorithm---equivalently,
by a Turing machine.

% \noindent
% {\bf context-free grammar}: a grammar whose rules have the form
% $A \rightarrow \beta$, where $A$ is a nonterminal and $\beta$ is
% a string of nonterminals and terminals.
% KSN: These two are not mentioned in this chapter.
% \noindent
% {\bf context-free language}: a language that can be described by
% some context-free grammar.

%{\bf context-sensitive grammar}: a grammar whose rules have the form
%$\alpha \rightarrow \beta$, where $\alpha, \beta$ are strings of nonterminals
%and terminals and $|\alpha| \leq |\beta|$.
%
%{\bf context-sensitive language}: a language which can be described by
%some context-sensitive grammar.

\noindent
{\bf decidable problem/language}:
a problem that can be decided by an algorithm---equivalently,
whose associated language is accepted by a Turing machine
that halts for all inputs.

\noindent
{\bf deterministic}: permitting at most one next move at any step
in a computation.

\noindent
{\bf finite automaton or finite-state machine}:
a restricted Turing machine where the head
is read-only and shifts only from left to right.
% Nondeterministic finite automata correspond to nondeterministic
% Turing machines.

\noindent
{\bf (formal) language}: a set of strings over some fixed alphabet.

%{\bf (formal) grammar}: a description of some language
%typically consisting of a set of terminals, a set of nonterminals
%with a distinguished one called the start symbol, and a set of
%rules (or productions) of the form $\alpha \rightarrow \beta$,
%depicting what string $\alpha$ of terminals and nonterminals
%can be rewritten as another string $\beta$ of terminals and nonterminals.

\noindent
{\bf Halting Problem}: the problem of deciding whether a given program
(or Turing machine) halts on a given input.

\noindent
{\bf many-one reduction}: a reduction that maps an instance of one problem
into an equivalent instance of another problem.

\noindent
% {\bf nondeterministic Turing machine}: a Turing machine which
% can make any one of a prescribed set of moves
% on a given state and symbol read on the tape.
% KSN: Simpler here is:
%
{\bf nondeterministic}: permitting more than one choice of next
move at some step in a computation.

\noindent
{\bf NP-complete language:} a language in NP such that every language
in NP can be reduced to it in polynomial time. 

\noindent
{\bf oracle Turing machine:} a Turing machine with an extra oracle tape
and three extra states $q_?,q_y,q_n$. When the machine enters $q_?$,
control goes to state $q_y$ if the oracle tape content is in the oracle
set; otherwise control goes to state $q_n$. 

\noindent
{\bf partial recursive function}:
a partial function computed by a Turing machine that need
not halt for all inputs.

\noindent
{\bf partially decidable problem}: one whose associated language is
recursively enumerable.  Equivalently,
there exists a program that halts and outputs $1$ for every
instance having a yes answer, but is allowed not to halt
or to halt and output $0$ for every instance with a no answer.


\noindent
{\bf polynomial time reduction}: 
a reduction computable in polynomial time. 

\noindent
{\bf program}: a sequence of instructions
%
% that is not required to terminate on every input.
% KSN: Eh? Readers will be led to think that nontermination is the
% distinguishing mark of a program.
%
that can be executed, such as the code of a Turing machine or
a sequence of RAM instructions.

\noindent
{\bf pushdown automaton}: a restricted Turing machine where the tape
acts as a pushdown store (or a stack), with an extra one-way read-only
input tape. 
% Nondeterministic pushdown automata correspond to 
% nondeterministic Turing machines.

\noindent
{\bf recursive language}: a language accepted by a Turing machine
that halts for all inputs.

\noindent
{\bf recursively enumerable (r.e.) language}:
a language accepted by a Turing machine.

\noindent
{\bf reduction}: a computable transformation of one problem into another.

%{\bf regular expression}: a description of some language using
%operators union, concatenation, and Kleene closure.

\noindent
{\bf regular language}: a language which can be described by some
right-linear/regular grammar (or equivalently by some regular expression).

\noindent
{\bf time/space complexity}: a function describing the maximum time/space
required by the machine on any input of length $n$.

\noindent
{\bf Turing machine}: a simplest formal model of computation consisting
a finite-state control and a semi-infinite sequential tape with a
read-write head. Depending on the current state and symbol read on the tape,
the machine can 
change its state and move the head to the left or right.
Unless otherwise specified, a Turing machine is deterministic.

\noindent
{\bf Turing reduction}:
a reduction computed by an oracle Turing machine that halts for
all inputs with the oracle used in the reduction.

\noindent
{\bf uncomputable function}:
a function that cannot be computed by any algorithm---equivalently,
not by any Turing machine.

\noindent
{\bf undecidable problem/language}:
a problem that cannot be decided by any algorithm---equivalently,
whose associated language
cannot be recognized by a Turing machine that halts for all inputs).

\noindent
{\bf universal Turing machine}: a Turing machine that is capable of simulating
any other Turing machine if the latter is properly encoded.

\begin{thebibliography}{99}
\setlength{\baselineskip}{0.6\baselineskip}
%\bibitem[Angluin, 1980]{Angluin}
%        Angluin, D. 1980. 
%        Finding patterns common to a set of strings.
%        {\it Journal of Computer and System Sciences}. 21:46-62.
\bibitem[Blum, 1967]{blum}
        Blum, M. 1967.
        A machine independent theory of complexity of recursive functions.
        {\em J. Assoc. Comput. Mach.} 14:322-336, 1967.
\bibitem[Brzozowski and McCluskey, 1963]{brzozo}
        Brzozowski, J. and McCluskey Jr, E. 1963.
        Signal flow graph techniques for sequential circuit state diagram.
        {\it IEEE Trans. on Electronic Computers}, EC-12(2):67-76.
\bibitem[Brzozowski and Seger, 1994]{brzozo1}
        Brzozowski, J.A. and Seger, C-J. H. 1994.
        {\it Asynchronous Circuits}, Springer-Verlag, New York.
\bibitem[Chandra, {\it et al}, 1981]{CKS81}
        Chandra, A.K., Kozen, D.C., and Stockmeyer, L.J. 1981.
        Alternation, 
        {\em Journal of the Assoc. Comput. Mach.}, 28:114-133.
\bibitem[Chomsky, 1956]{Chomsky1}
        Chomsky, N. 1956. 
        Three models for the description of language.
        {\it IRE Trans. on Information Theory}. 2(2):113-124.
%\bibitem[Chomsky, 1963]{Chomsky2}
%        Chomsky, N. 1963. 
%        Formal properties of grammars. 
%        In {\it Handbook of Math. Psych.} Vol. 2, 323-418.
%        John Wiley and Sons, New York.
\bibitem[Chomsky and Miller, 1958]{miller} 
        Chomsky, N. and Miller, G. 1958.
        Finite-state languages.
        {\it Information and Control}. 1:91-112.
\bibitem[Cook, 1971]{cook1}
        Cook, S. 1971.
        The complexity of theorem-proving procedures.
        {\em Proc.\ 3r ACM Symp.\ Theory of Comput.}, pp. 151-158. 
\bibitem[Cook and Reckhow, 1973]{cook}
        Cook, S. and Reckhow, R. 1973.
        Time bounded random access machines.
        {\it J. Comput. Syst. Sci.} 7:354-375.
\bibitem[Davis, 1980]{Davis}
        Davis, M. 1980. 
        What is computation? 
        in {\it Mathematics Today--Twelve Informal Essays}. L. Steen
        (ed.) 241-259. 
\bibitem[Floyd and Beigel, 1994]{floyd}
        Floyd, R.W. and Beigel, R. 1994
        {\it The Language of Machines: an Introduction to
        Computability and Formal Languages}. Computer Science Press,
        New York.
\bibitem[Gurari, 1989]{gurari}
        Gurari, E. 1989.
        {\it An Introduction to the Theory of Computation}.
        Computer Science Press, Rockville, MD.
\bibitem[Harel, 1992]{Harel}
        Harel, D. 1992. 
        {\it Algorithmics: The spirit of Computing}.
        Addison-Wesley, Reading, MA.
\bibitem[Hartmanis, 1994]{hartmanis}
        Hartmanis, J. 1994.
        On computational complexity and the nature of computer science.
        {\it CACM}. 37(10):37-43.
\bibitem[Hartmanis and Stearns, 1965]{HS}
        Hartmanis, J. and Stearns, R. 1965. 
        On the computational complexity of algorithms.
        {\it Trans.\ Amer.\ Math.\ Soc.}. 117:285-306.
\bibitem[Hopcroft and Ullman, 1979]{HU79}
        Hopcroft, J. and Ullman, J. 1979.
        {\it Introduction to Automata Theory, Languages and Computation}.
        Addison-Wesley, Reading, MA.
\bibitem[Karp, 1972]{karp1}
        Karp, R.M. 1972.
        Reducibility among combinatorial problems.
        in {\em Complexity of Computer Computations}, 
        ed. R.E. Miller and J.W. Thatcher. Plenum Press, pp. 85-104.
\bibitem[Karp and Ramachandran, 1990]{Karp}
        Karp, R.M. and Ramachandran, V. 1990.
        Parallel algorithms for shared-memory machines.
        in {\it Handbook of Theoretical Computer Science},
        ed. J. van Leeuwen, 869-941. Elsevier/MIT Press.
\bibitem[Kleene, 1956]{Kleene}
        Kleene, S. 1956.
        Representation of events in nerve nets and finite automata.
        In {\it Automata Studies}, 3-41. Princeton University Press, NJ.
\bibitem[Knuth {\it et al}, 1977]{knuth}
        Knuth, D., Morris, J. and Pratt, V. 1977.
        Fast pattern matching in strings.
        {\it SIAM J. Comput.}. 6:323-350.
\bibitem[Kohavi, 1978]{kohavi}
        Kohavi, Z. 1978.
        {\it Switching and Finite Automata Theory}.
        McGraw-Hill.
\bibitem[Kolmogorov and Uspenskii, 1958]{kolmogorov}
        Kolmogorov, A. and Uspenskii, V. 1958.
        On the definition of an algorithm.
        {\it Uspekhi Mat.\ Nauk}. 13:3-28.   
\bibitem[Knuth, 1969]{Knuth}
	Knuth, D.E. 1969.
	{\it Fundamental Algorithms}, volume 1 of {\it The Art of Computer
	Programming}. Addison-Wesley, Reading, MA.

\bibitem[Lesk, 1975]{lesk}
        Lesk, M. 1975.
        LEX--a lexical analyzer generator.
        {\it Technical Report 39}. Bell Laboratories, Murray Hill, NJ.
\bibitem[Levin, 1973]{levin}
        Levin, L. 1973.
        Universal sorting problems.
        {\em Problemi Peredachi Informatsii} 9(3):265-266. (In Russian)
\bibitem[Lewis and Papadimitriou, 1981]{lewis}
        Lewis, H. and Papadimitriou, C.H. 1981.
        {\it Elements of the Theory of Computation.}
        Prentice-Hall.
\bibitem[Li and Vit\'{a}nyi, 1993]{LV}
        Li, M. and Vit\'{a}nyi, P. 1993.
        {\it An Introduction to Kolmogorov Complexity and Its Applications.}
        Springer-Verlag.
\bibitem[McCulloch and Pitts, 1943]{pitts}
        McCulloch, W. and Pitts, W. 1943.
        A logical calculus of ideas immanent in nervous activity.
        {\it Bull.\ Math.\ Biophysics}. 5:115-133.
\bibitem[Lynch, 1996]{lynch}
        Lynch, N. 1996.
        {\it Distributed Algorithms.}
        Morgan Kaufmann.
\bibitem[Post, 1943]{Post}
        Post, E. 1943. 
        Formal reductions of the general combinatorial decision problems. 
        {\it Amer. J. Math.} 65:197-215.
\bibitem[Rabin, 1963]{Rabin}
        Rabin, M.O. 1963.
        Real time computation.
        {\em Israel J.\ Math.} 1(4):203-211.
\bibitem[Rabin and Scott, 1959]{rabin} 
        Rabin, M.O. and Scott, D. 1959.
        Finite automata and their decision problems. 
        {\it IBM J.\ Res.\ Dev.}. 3:114-125.
\bibitem[Robinson, 1991]{Rob}
        Robinson, R. 1991. 
        Minsky's small universal Turing machine.
        {\it International Journal of Mathematics}. 2(5):551-562.
\bibitem[Ruzzo, 1981]{Ruzzo}
        Ruzzo, W.L. 1981.
        On uniform circuit complexity.
        {\it J. Comput. System Sci.} 22:365-383.
\bibitem[Savitch, 1970]{savitch}
        Savitch, J. 1970.
        Relationships between nondeterministic and deterministic tape
        complexities. 
        {\it J.\ Comput.\ Syst.\ Sci.}. 4(2)177-192.
\bibitem[Searls, 1993]{searls}
        Searls, D. 1993.
        The computational linguistics of biological sequences.
        In {\it Artificial Intelligence and Molecular Biology}.
        L. Hunter (ed.), MIT Press. 47-120.
\bibitem[Sch\"onhage, 1980]{schonhage}
        Sch\"onhage, A. 1980.
        Storage modification machines.
        {\it SIAM J. Comput.}. 9:490-508.
\bibitem[Sch\"onhage and Strassen, 1971]{schonhage1}
        Sch\"onhage, A., and Strassen, V. 1971.
        Schnelle Multiplikation grosser Zahlen,
        {\it Computing} 7, 281-292.
\bibitem[Sipser, 1997]{Sipser}
	 Sipser, M. 1997
	 {\it Introduction to the Theory of Computation}, First Edition.
	 PWS Publishing Company, Boston, MA.
\bibitem[Turing, 1936]{Turing}
        Turing, A. 1936.
        On computable numbers with an application to the
        Entscheidungsproblem.      
        {\it Proc.\ London Math.\ Soc., series 2}, 42:230-265. 
\bibitem[van Emde Boas, 1990]{boas}
        van Emde Boas, P. 1990. Machine models and simulations.
        in {\it Handbook of Theoretical Computer Science},
        ed. J. van Leeuwen, 1-66. Elsevier/MIT Press.
\bibitem[Wood, 1987]{wood}
        Wood, D. 1987.
        {\it Theory of Computation}. Harper and Row.
\bibitem[Yap, 1997]{yap}
        Yap, C. 1997.
        {\em Introduction to Complexity Classes}.
        Oxford University Press. To appear.
\end{thebibliography}

\bigskip
{\noindent \large \bf Further Information}\\
The fundamentals of the theory of computation, automata theory,
and formal languages can be found in Chapters 31--33
and in many text books including
\cite{floyd,gurari,Harel,HU79,lewis,wood,yap,Sipser}.
One central focus of research in this area is to understand the relationships
between different resource complexity classes. This work is motivated
in part by some major open questions about the relationships between resources
(such as time and space) and the role of control mechanisms 
(such as nondeterminism or randomness). 
At the same time, new computational models are being introduced
and studied. One recent model that has led to the resolution of a number
of interesting problems is the {\em interactive proofs\/} (IP) model.
IP is defined in terms of two Turing machines that
communicate with each other. One of them has unlimited power and the other
(called the {\em verifier\/})
is a probabilistic Turing machine whose time complexity is
bounded by a polynomial. The study of IP has led to
new ways to encrypt information as well as to the proof of some unexpected 
results about the difficulty of solving NP-hard problems (such as coloring,
clique etc.) even approximately. See Chapter~35, sections~3 and~5.
Another new model is the {\em quantum Turing machine\/},
which can solve in polynomial time
some problems such as factoring
that are believed to require exponential time on any hardware that
follows the laws of ``classical'' (pre-quantum) physics. 
There are also attempts to use molecular or cell-level
interactions as the basic operations of a computer. 
%Yet another research
%direction motivated in part by the advances in hardware technology is the 
%study of `neural networks' which model (albeit in a simplistic manner)
%the brain structure of mammals. 
%
% Later chapters in this {\em Handbook\/}
% will present the state of the art 
% information about many of these developments.
% KSN: seemingly not---Allender et al. mention only in passing.  Editor?

The following annual conferences present the leading research
work in computation theory: ACM Annual Symposium on Theory of Computing
(STOC), IEEE
Symposium on the Foundations of Computer Science (FOCS), IEEE Conference on
Computational Complexity
(CCC, formerly Structure in Complexity Theory), 
International Colloquium on Automata, Languages and Programming
(ICALP), Symposium on
Theoretical Aspects of Computer Science (STACS), Mathematical
Foundations of Computer Science (MFCS),
and Fundamentals of Computation Theory (FCT).
There are many related conferences
%
% such as several conferences on each of
%
in
the following areas:\ computational learning
theory, computational geometry, algorithms, principles of distributed 
computing, computational biology, and database theory. In each case,
specialized computational models and concrete
algorithms are studied for a specific application area.
There are also conferences in both pure and applied mathematics
that admit topics in computation theory and complexity.
We conclude with a partial list of major
journals whose primary focus is in theory of computation: 
{\em Journal of the ACM\/},
{\em SIAM Journal on Computing\/},
{\em Journal of Computer and System Sciences\/},
{\em Information and Computation\/},
{\em Theory of Computing Systems\/}
(formerly {\em Mathematical Systems Theory\/}),
{\em Theoretical Computer Science\/},
{\em Computational Complexity\/},
{\em Journal of Complexity\/},
{\em Information Processing Letters\/},
{\em International Journal of Foundations of Computer Science\/},
and {\em Acta Informatica\/}.

\end{document}








