% revised Friday, Feb 13 by Ravi
% file "JLRch26.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.

% Note: one line with psfig may need commenting out.

% Chapter26 

\documentclass[11pt]{article}
\special{landscape}\special{! /landplus90 true store}
\usepackage{epsf}
\usepackage{amssymb}
\input{psfig}
\input{2up.tex}
\twouparticle

\sloppy    %% KSN: Not as bad as its name suggests, fixes \overfull hbox'es

\setlength{\topmargin}{-0.2in}
\setlength{\textwidth}{6in} %6.5in
\setlength{\oddsidemargin}{.3in}
\setlength{\evensidemargin}{.3in}  %were -.2in
\setlength{\textheight}{8.5in}
\setlength{\footskip}{0.5in}
\setlength{\parskip}{3pt plus 1pt minus 1pt}


%% \makeindex

%% KSN macros
\newcommand{\emptystring}{\epsilon}
\newcommand{\code}{\mbox{\it code\/}}
\newcommand{\plus}{\mbox{\it plus\/}}
\newcommand{\ittimes}{\mbox{\it times\/}} 
\newcommand{\itexp}{\mbox{\it exp\/}}
\newcommand{\sub}{\mbox{\it sub\/}}
\newcommand{\seq}[2]{\mbox{${#1}_1,\ldots,{#1}_{#2}$}}
\newcommand{\seqn}[1]{\seq{#1}{n}}
% \newcommand{\tuple}[2]{(\seq{#1}{#2})}
% \newcommand{\ntuple}[1]{\tuple{#1}{n}}
% \newcommand{\Ctuple}[2]{({#1}_0,\ldots,{#1}_{#2-1})}
\newcommand{\stub}[1]{\typeout{*** Stub! ***}
        $\langle${\bf Stub:} {\em #1}$\rangle$}


%% 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}

\pagestyle{plain}

\begin{document}
%% \sloppy
%% \setcounter{chapter}{12}
%% \chapter{}
\title{Computability
%% \footnote{Preliminary version of a chapter
%% in the forthcoming {\it CRC Handbook of Computer Science and Engineering.}}
}

\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
\and
Kenneth W. Regan\\
Department of Computer Science\\
State University of New York at Buffalo\\
Buffalo, NY 14260, USA}

\date{}

\maketitle

% Authors, editor---general comments by KSN: Some ideas in this chapter
% were really good, such as the connections to programming languages
% and to paradoxes.  Those connections seemed to me to call for a
% clearer, fuller treatment, so I added to them.  However, some other
% ideas were not handled well.  For instance, the bare assertion about
% "undecidable ==> needs human assistance" flies in the face of
% Turing's main point that human beings "are" computers.  It can fly
% if properly supported...  Another lack was not completing the point
% of how the /success/ of /formalization/ is the key preamble to
% /undecidability/.  This was Go"del's main point---and he had a long
% "Part II" of his famous paper ready in case he needed to buttress it.
% I've handled this by some sentence tweaks and one inserted paragraph
% about "implementing" Zwicker's paradox.  Most of all, the writing here
% was especially unfocused and disorganized, well to the point of
% damaging comprehension (not to mention some mistakes), and in some
% places the only fix was wholesale rewriting.
% My edits also bring this chapter up to the prescribed 30--40 page range.



\section{Introduction} \label{intro}
%
% In the last two chapters, we have introduced important
% computational models, namely finite automata, pushdown automata,
% Turing machines, and Chomsky's hierarchy of formal grammars.
% In this chapter, we will explore the limits of mechanical computation
% as defined by these computational models.
%
% KSN: A little unfocused already---FAs and PDAs and Types 1-3 do not set
% the limits, and you don't explore /them/ further, and there are other
% models besides "these" that you discussed.  I opted just to simplify.
%
In the last two chapters, we have introduced several important
computational models, including
Turing machines and Chomsky's hierarchy of formal grammars.
In this chapter, we will explore the limits of mechanical computation
as defined by these models.
We begin with a list of fundamental
problems for which automatic computational solution
%
% will
% KSN: Counterfactual---use the subjunctive tense.
%
would be very useful.
%
%
\comment{   %% Text commented out by KSN.
>One of these problems is the
>%
>% {\it universal simulation problem\/} that involves the design...
>% KSN: Here, use a comma and "which".  The rule for "that" vs. "which"
>% is that when the preceding clause has uniquely specified its referent,
>% use "which"; when it has not yet done so, use "that" (no comma) to
>% introduce a /qualifying clause/.  The usual "mistake" (even great writers
>% do it) is to use "which" too often---this was the opposite.
>%
>{\it universal simulation problem\/}, which involves the design
>of an algorithm to simulate any computer.
>%
>% Well, in a sense this problem /has/ been solved, in the sense that every
>% computer user partakes of daily.  This writing is not focused well...
>% ..Now I see that you *did* intend to say that this problem is solvable...
>% 
>We will present a simple programming language to program a Turing machine and
>show how to design a program for universal simulation.
>This construction is known as a universal Turing machine.
>Next we present a class of functions called $\mu$-recursive functions that
>provides a concise, mathematical description of computable functions.
>Finally we will describe basic techniques for showing the unsolvability
>of most of the problems in our list.
>%
} %% end of \comment-outed text.  The point squiggled through, but the
% reader would have been confused about what "solvable" means and where
% it applies.  I fixed this and the "human assistance" point wholesale.--KSN
%
%
One of these is the {\em universal simulation problem\/}:\ can one
design a single algorithm that is capable of simulating {\em any\/}
algorithm?  Turing's demonstration that the answer is {\em yes\/}
\cite{Turing} supplied the proof for Babbage's dream of a
single machine that could be programmed to carry out any
computational task.  We introduce a simple Turing machine programming
language called ``GOTO'' in order to facilitate our own design
of a universal machine.  Next, we describe the schemes of 
{\em primitive recursion\/} and {\em $\mu$-recursion\/}, which enable
a concise, mathematical description of computable functions that is
independent of any machine model.  We show that the $\mu$-recursive
functions are the same as those computable on a Turing machine,
and describe some computable functions, including one that solves a
second problem on our list.

The success in solving ends there, however.
We show in the last section of this chapter that all of the remaining
problems on our list are {\em unsolvable\/} by Turing machines,
and subject to the {\em Church-Turing thesis\/}, have no mechanical or
human solver at all.  That is to say, there is no Turing machine or
physical device, no stand-alone product of human invention, 
that is capable of giving the correct answer to all---or even
most---instances of these problems.  The implication we draw is that in order
to solve {\em some\/} important instances of these problems, human
ingenuity is needed 
to guide powerful computers down the paths felt
most likely to yield the answers.  To cite Raymond Smullyan quoting
P.~Rosenbloom, the results on unsolvability imply that ``man can
never eliminate the necessity of using his own cleverness, no
matter how cleverly he tries.''

Almost the first consequence of formalizing computation was that we can
formally establish its limits.  Kurt G{\"o}del showed that the process
of proof in any formal axiomatic system of logic can be simulated by the basic
arithmetical functions that computation is made of.  Then he proved that
any sound formal system that is capable of stating the grade-school
rules of arithmetic can make statements that are neither provable nor
disprovable in the system.  Put another way, every sound formal
system is {\em incomplete\/} in the sense that there are mathematical
truths that cannot be proved in the system.  Turing realized that
G{\"o}del's basic method could be applied to computational models themselves,
and thus proved the first computational unsolvability results.    
Since then
problems from many areas, including
group theory, number theory, combinatorics, 
set theory, logic, cellular automata, dynamical systems, topology, 
and knot theory, have been shown to be unsolvable.
In fact, proving unsolvability is
now an accepted ``solution'' to a problem.
%
% I've added the most famous example---Hilbert's Tenth---below.  --KSN
%
It is just a way of saying that the
problem is too general for a computer to handle---that
supplementary information is needed to enable
a mechanical solution.

Since Turing machines capture the power of mechanical computability,
our study will be based on Turing's model.
%
% We will show the existence of problems which 
% are not solvable on a Turing machine.
% Hence such problems cannot be solved on any 
% computer, regardless of time and storage requirements.
% On the way to the proof of such a negative result is a very useful
% positive result which asserts
% the existence of a universal Turing machine.
% This universal simulation result is
% of central importance in general purpose computers.
% The fact that different
% problems can be solved on the same computer by only changing the
% software but not the hardware is what makes computers such a
% versatile tool in contrast to other
% gadgets such as automobiles or microwave ovens.
% KSN: Repetitive, unnecessary---except perhaps the last sentence, but I 
% hit that point by citing "Babbage's dream" anyway---and I would have had
% to change "automobile" to something else---they are all Turing-complete now.
% E.g. IACOCCA stands for "I Am Crazy Over Computer-Controlled Automobiles."
%
In the next section, we describe a Turing machine as a computer that can
run programs written in a very simple language we call the
``GOTO Language.''  This formalism
is equivalent to Chapter 24's description of Turing machines 
using the standard 7-tuple notation.
%
% KSN: Please note that I changed Ch. 24 from 5-tuple to 7-tuple notation.
% The repetition of "GOTO..." is probably OK.
%
Our language provides an alternate way to write programs
and makes proofs about Turing machines more intuitive.


% \section{Computability and a Universal Algorithm}\label{universal}
% KSN: See section note below.
%
\section{Computability and a Universal Program}\label{universal}
Turing's notion of mechanical computation was based on identifying 
the {\em basic steps\/} in any mechanical computation. 
He reasoned that an operation such as numerical multiplication is not
primitive, because it can be divided into simpler steps such as
using the times-table on individual pairs of digits, shifting, and adding.
Addition itself can be broken down
into simpler steps such as
adding the lowest digits, computing the carry, and moving to the next
digit.
% 
% etc.   <-- KSN: a good habit to break.
%
Turing concluded that the most basic 
features of mechanical computation are the ability to read and
write on a storage medium, the ability to move about on that medium,
and the ability to make simple logical decisions.
%
% KSN: this change to the last sentence suits your GOTO language better.
% Actually, in place of "move about" Turing said something like
% "shift the focus of attention", and he argued that this focus need
% only be in one place at any one time.  I've left that out, but
% now I bring in a couple more things from Turing's paper.
%
Turing chose the storage medium to be a single linear {\em tape\/}
divided into cells.  He showed that such a tape could model
spatial memory in three (or any number of) dimensions through the use
of indexed co-ordinates.  With much care he argued that human
sensory input could be encoded by strings over a finite alphabet
of cell symbols called the {\em tape alphabet\/}.
(This bold discretization of sensory experience now seems a harbinger
of the digital revolution that was to follow.)         
A decision step enables the computer to exert local control over
the sequence of actions.  Turing restricted the next action
performed to be in a
cell neighboring the one on which the current action occurred,
and showed how non-local actions can be simulated by successions
of steps of this kind.  He also
introduced an instruction to tell the computer to stop.

In summary, Turing proposed a model to characterize mechanical computation 
as being carried out as a sequence of instructions.
Our ``GOTO'' formalism provides the following five
kinds of instructions.  Here $i$ stands for a tape symbol 
and $j$ stands for a line number.


%\begin{table}
\begin{center}
\begin{tabular}{l} 
PRINT $i$ \\
 
MOVE RIGHT \\

MOVE LEFT \\

IF $i$ IS SCANNED GOTO LINE $j$  \\
% Better style, and consistent with "IF (...) THEN j" in BASIC.  --KSN

STOP \\
% KSN: Why not "HALT"?  I left your word in.
\end{tabular} 
\end{center}
%\end{table}

\noindent
When we speak about programs recognizing languages rather than
computing functions, we replace STOP by statements ACCEPT and
REJECT, each of which need occur only once in a program.

A program in this language is a sequence of instructions or ``lines''
numbered $1$ to $k$.  The input to the program is a string over a
designated {\em input alphabet\/} $\Sigma$, which we take to be $\{0,1\}$
throughout this chapter.  The tape alphabet includes $\Sigma$ and a
special {\em blank\/} character $B$ representing an empty cell, and
may (but need not) contain other symbols.
The input is stored on the tape,
with the read head scanning the first symbol
(or $B$ if the input is empty), before the computation begins.
 
How much memory should we allow the computer to use?
Rather than postulate that the tape is actually infinite---an
unrealistic assumption---we prefer here to say that the tape
has expandable boundaries.  Initially the input defines the 
two boundaries of the tape.  Whenever the machine moves
left of the left boundary or right of the right boundary, a new
memory cell containing the blank is attached.  This convention 
clarifies what we mean by saying that if and when the machine halts
by reaching the STOP instruction, the ``result'' of the computation
is the entire content of the tape.
%
% KSN: I don't strongly see the need for these sentences, but at least I
% rewrote the last sentence to supply a motivation.

We present an example program written in the GOTO language.
This program accomplishes
the simple task of doubling the number of 
initial $1$s in the input string.
%
% More precisely, on the input containing $k$ $1$'s, 
% the program produces $2k$ $1$'s.
% KSN: This wasn't "more precisely", it was the definition.
% Oops, it doesn't work in the k = 0 case.  Rather than rewrite the code,
% I chose to call this "bug" a "feature".
%
Informally, the program achieves its goal as follows:
When it reads a $1$, it changes the $1$ to a $0$,
moves left looking for a new cell, and writes a $1$ in that cell.
Then it returns rightward to the $0$ that marks where it had been,
rewrites it as a $1$, and moves right to look for more $1$s.
If it immediately finds another $1$ it repeats the process from line~$1$,
while if it doesn't, it halts right there. 
%
% and repeats this step for each 1.
% KSN: It was neither a single /step/ nor a single /line/.
%
This program even has a ``bug''---it ``should'' leave strings that
do not begin with a~$1$ unchanged, but instead it alters them.

\begin{figure}\label{ravi.fig1}
\begin{center}
\begin{tabular}{|l|} \hline
1 PRINT 0 \\

2 MOVE LEFT \\

3 IF 1 IS SCANNED GOTO LINE 2  \\

4 PRINT 1 \\

5 MOVE RIGHT \\

6 IF 1 IS SCANNED GOTO LINE 5 \\

7 PRINT 1 \\

8 MOVE RIGHT \\

9 IF 1 IS SCANNED GOTO LINE 1 \\

10 STOP \\ \hline
\end{tabular}
\end{center}
\caption{The doubling program in the GOTO language.}
\end{figure}

The main change from the traditional Turing machine formalism of
Chapter~24 is that we have replaced ``states'' by line numbers.
A Turing machine of the former kind can always be simulated in
our GOTO language by making blocks of successive lines, themselves
divided into sub-blocks (for each character)
that are headed by ``IF'' statements,
carry out the instructions for each state.
Our formalism makes many programs more succinct and closer to
programmers' experience, and highlights the role of (conditional) GOTO
instructions in setting up loops and enabling statements to be repeated.
Despite the popular scorn of {\tt goto} statements,
this feature is ultimately
the most important aspect of programming and can be
found in every imperative-style programming language---at
least in the code produced by the compiler if the language has
no {\tt goto} instruction itself.
Indeed, the above example could be rendered into a
structured programming language such as C as follows,
%
\begin{tabbing}
\indent\=\indent\=\kill
\>{\bf do} \{ \\
\>\>{\bf do} \{ PRINT 0; MOVE LEFT; \} {\bf while} (1 is scanned);\\
\>\>PRINT 1;\\
\>\>{\bf do} MOVE RIGHT; {\bf while} (1 is scanned);\\
\>\>PRINT 1; MOVE RIGHT; \}\\
\>{\bf while} (1 is scanned);
\end{tabbing}
%
and a C compiler (using a character array {\tt tape[i]} and 
{\tt ++i}, {\tt --i} for the moves) might plausibly convert this
into something exactly like our GOTO program!
%
% The do...while construct is closest to what you wrote and nicer-looking
% than repeat...until in Pascal, plus the tape<-->array analogy holds
% since C arrays do not fix their bounds!  --KSN
 


The simplicity of the GOTO language is rather deceptive.
%
% There is strong
% reason to believe that it is powerful enough that any mechanical
% computation can be expressed by a suitable program in the GOTO language.
%
% KSN: The reader would be really confused as to the source of any doubt
% here, since the Church-Turing thesis comes much later.  You are really
% making two points here, and my addition above helps one of them.
%
As the above example hints, any program in
any known high-level programming language can be converted into an
equivalent GOTO program, under suitable conventions on 
how inputs and outputs are represented on the tape.
(If the program only reads from the standard input stream and writes to
the standard output stream, then no such conventions are necessary.) 
%
% KSN: Technically I've misplaced "only", but this sounds best.
%
There is strong reason to believe that any
mechanical computation of any future kind can be
expressed by a suitable GOTO program.
Note, however, that a program written in the GOTO language need not
always halt; i.e., on certain inputs the program may never reach
a STOP instruction.  On such inputs we say that the output of the
program is {\em undefined\/}.

Now we can give a precise definition of what we mean by an
{\em algorithm\/}, attempting to rule out this last situation.
An algorithm is {\em any program written in the {\rm GOTO}
language that has the additional property of halting on all inputs.\/} 
Such programs will be called {\em halting programs\/},
and correspond to ``total'' deterministic Turing machines in Chapter~24.
When we consider {\em decision problems\/},
which have yes/no answers, halting programs are required to end their
computation with either an ACCEPT or a REJECT statement, on any input.
%
% I put the first-mention of ACCEPT and REJECT back where it belonged,
% near the definition of GOTO programs.  --KSN
  


\subsection{Some Computational Problems}\label{sub.some}
We begin by listing a collection of computational problems for
which a mechanical solution can be very helpful.  By a mechanical
solution, we mean a step-by-step process that takes into account
all possible
inputs, and that can be executed without any human assistance
%
% KSN: Some readers may think that the process executes on all
% possible inputs simultaneously, but I fixed it by adding:
%
once a certain input is provided.
An algorithm is required to work correctly on all instances.
%
% The reader has a clear informal notion of an algorithm from the earlier
% chapters. (Later in this chapter we will formally define an algorithm.)
% Another requirement of an algorithm is that it should terminate
% in a finite number of steps.  A practically-oriented reader may
% object that this requirement is not reasonable since the problems
% in the real world have a clear upper limit on the instance size.
% But there are no good alternatives...
%
% KSN: This is meandering unfocused repetitive writing.  I deleted much
% of it, and moved the decision/solving criteria to AFTER the problems.

We now list some problems that are fundamental 
either because they are inherently important or because they played a
historical role in the development of computation theory.
For the first four, $P$ stands for a program in our GOTO language,
and $x$ is a string over the input alphabet, which we fix to be
$\{0,1\}$.
%
% Note the parallel structure and better organization of what follows.
% /However/, I did not know how to get my preferred "(1), (2),..." style
% of item labels to be picked up automatically in cross-references,
% so I had to fall back (inconsistently) on the default style.  --KSN

\begin{enumerate}
\item\label{problem-universal}
{\em Universal simulation.\/}
Given a program $P$ and an input $x$ to $P$, determine the 
output (if any) that $P$ would produce on input $x$. 
\item\label{problem-halting}
{\em Halting problem.\/}
Given $P$ and $x$, output 1 (for yes) if $P$ would halt when given
input $x$, and $0$ (for no) if $P$ would not halt.
\item\label{problem-type0}
{\em Type-0 grammar membership.\/}
Given a type-0 grammar $G$ and a string $x$, determine whether
$x$ can be derived from the start symbol of $G$.
% 
% ---and if so, find such a derivation.
%
% Without the last clause, it's the /membership problem/ as
% defined in the last chapter.  --KSN
%
\item\label{problem-compression}
{\em String compression.\/}
Given a string $x$, find the shortest program $P$ such that
when $P$ is started with empty tape, $P$ eventually halts 
with $x$ as its output.  Here ``shortest'' means that the total number
of symbols in the program's instructions is as small as possible.
%
% I won't bug you that "the shortest" isn't well-defined.  --KSN
%
\item\label{problem-tiling}
{\em Tiling.\/}
Given a finite set $T$ of tile types, where all tiles of a type are
unit squares with the same four colors on their four edges,
determine whether every finite rectangle can be {\em tiled\/} by $T$.
If $k$ and $n$ are the integer sides of the rectangle, being tiled
means that $kn$ tiles drawn from $T$ can be arranged so that
every two tiles that share an edge have the same color at that edge.
\item\label{problem-LP}
%
% Grrr...the original text made no mention of "objective function", and
% then the next subsection referred to one.  I chose to put the full
% form of linear programming in the remarks, but grrr...   --KSN
%
{\em Linear programming.\/}
Given some number $k$ of linear inequalities in $n$ unknowns,
determine whether there is an assignment of $n$ values to
the unknowns that satisfies all the inequalities.
\item\label{problem-Hilbert}
%
% {\em Hilbert's tenth problem.\/}
%
{\em Integer equations.\/}
Given $k$-many polynomial equations in $n$ unknowns, determine whether
there is an assignment of $n$ integers to the unknowns that
satisfies all the equations.
%
% KSN: Without adding this, I didn't see the particular point of having
% LP.  One could be more ambitious and add "Non-Linear Programming"
% and "Integer Linear Programming" as examples of () a decidable
% problem that has been proved intractable [if I recall the work
% on real closed fields correctly] and () a decidable problem that is
% NP-hard.  But I left it at this.  Omitting "integer coefficients" is OK.
\end{enumerate} 


{\noindent \sc Some remarks about the above problems:}
% Most of the problems in the above list are decision problems; they just
% have two outcomes- yes or no.  The problems in our list include nonnumerical 
% problems, and ``meta problems'', which are problems about other problems.
% KSN: Repetitive.  I clarified "meta-problem" in my remarks below on (7).
%
A solution to Problem~\ref{problem-universal}
realizes Babbage's objective of a
single program or machine capable of simulating all programs $P$.
For cases where $P$ run on $x$
would never halt and produce output, we have left open whether we require the
solution itself to halt and detect this fact---i.e., to be an algorithm.
For any such algorithm to exist, there must be an algorithm to solve
Problem~\ref{problem-halting}, which is a yes/no {\em decision problem\/}.
An algorithm for Problem~\ref{problem-halting} would be a boon to  
reliable software design, since it could be used to test whether
a given block of code can cause infinite loops.
Problem~\ref{problem-type0} is another decision problem; its solution
would be useful for natural-language processing and much more.
Problem~\ref{problem-compression} is a function-computation
problem of central importance in information theory.
For illustration, think of $x$ as a large amount of scientific data
for which we seek a concise theory $P$ that can generate and hence
explain it. 
A famous example is Kepler's laws,
which explained Tycho Brahe's voluminous and meticulous observational data.
Problem~\ref{problem-compression} thus asks whether the heart of science
(to paraphrase Occam's Razor,
``finding the simplest explanation that fits the facts'')
can be done automatically on a computer.
% 
% When we allow the inference rules to be sufficiently 
% strong, this problem becomes  undecidable. We will not discuss this
% problem further in this section but will refer the reader to some
% related formal systems discussed in~\cite{LV}.
% KSN (!!): put this later.

The tiles in Problem~\ref{problem-tiling}, which we introduced in
detail in Chapter~24, are sometimes named after Hao Wang,
who wrote the first research paper about them \cite{Wang}.
Figure~\ref{fig.tile1}(a) shows an example of a set $T$ of
tile types, and Figure~\ref{fig.tile1}(b) shows how
tiles drawn from $T$ can be used to tile
a $5 \times 5$ square area.
%
\begin{figure}
\centerline{\psfig{figure=ravifig1.ps,height=2.5truein,width=4.3truein,silen=}}
\par
\smallskip
\caption{An example of tiling.}
\label{fig.tile1}
\end{figure}
% 
The tiling problem is not merely an interesting puzzle.
It has been an art form
pursued by artists from many cultures for centuries.
Tiling problems have deep
significance in combinatorics, algebra, and formal languages.
Note that our decision problem does not ask simply whether a given
$k \times n$ rectangle can be tiled, but whether---given $T$---{\em all\/}
$k \times n$ rectangles can be tiled via $T$.
The full problem of linear programming adds to Problem~\ref{problem-LP} a
clause saying:\ if there exist {\em feasible solutions\/},
i.e.\ assignments that satisfy
all the so-called linear {\em constraints\/}, find one
that maximizes (or minimizes) a given {\em objective function\/}
(or {\em cost function\/}).
%
% It suits our purposes, however, to stick with the decision
% problem of whether any such assignment (called a {\em feasible solution\/})
% exists.  
% The case where one is given some number of linear {\em equations\/}
% can be regarded as a special case of Problem~\ref{problem-LP}.
%
This problem has central importance in economics, game theory, and 
operations research.
Problem~\ref{problem-Hilbert} is called
{\em Hilbert's tenth problem\/}, and was one of
twenty-four that David Hilbert posed as challenges for the new century
at the International Congress of Mathematicians in 1900.  It
goes back two thousand years to the mathematician Diophantus'
study of these so-called {\em Diophantine equations\/}.
Actually, Hilbert posed the ``meta-problem'' of finding
an algorithm that can solve any Diophantine equation,
or at least tell whether it has a solution.

Recall from Chapter~24 that a decision problem is {\em decidable\/}
if it has an algorithm, and {\em undecidable\/} otherwise.
If our program correctly evaluates all
instances for which the answer is ``yes,'' but may fail to halt on
some instances for which the answer is ``no,'' then the program is
a {\em partial decision procedure\/}, and the problem is
{\em partially decidable\/}.
A partially decidable problem, however, is undecidable---unless you
can find an algorithm that removes the word ``partially.''
Likewise, if our program
correctly outputs $f(x)$ whenever $f(x)$ is defined, but may fail
to halt when $f(x)$ is undefined, then the partial function $f$
is {\em partial computable\/}.

In the remainder of the subsection, we present some simple algorithm design 
techniques and sketch how they make progress on solving some
of these problems and special cases of them.
These techniques may seem too obvious to warrant explicit
description. However, we feel that such a description will help
new readers to appreciate 
the limits on information processing
that make certain problems undecidable.

\subsubsection{Table Look-up}\label{subsub.tab}
% The basic idea is to create a table for a function $f$ which
% needs to be computed by tabulating in
% one column an input $x$ and the corresponding $f(x)$ in a second
% column. Then the table itself can be
% used as an algorithm. This method cannot be used directly since
% the set of all inputs is infinite.
% It is therefore not very useful although it can be made to work
% in conjunction with the technique described below.
%
% KSN: Really weak writing.  I almost killed the whole thing until I
% found a way to save it.

For certain functions $g$ it can be advantageous to create a table
with one column for inputs $x$ and one for values $g(x)$,
looking up the value in the table whenever an evaluation $g(x)$ is
needed.  A function $f$ that is defined on an infinite set
such as $\Sigma^*$ cannot have its values enumerated in a finite
table in this manner, but sometimes the infinite table for $f$
can be described in a finite way that constitutes an algorithm for $f$.
Moreover, tables for other functions $g$ may help the task of
computing $f$, such as the digit-by-digit times-table
used in multiplying integers of arbitrary
size.  These ideas come into play next.

\subsubsection{Bounding the Search Domain}\label{subsub.bou}
Many solutions to decision problems involve finding a {\em witness\/}
that proves a ``yes'' or ``no'' answer for a given instance.
The term reflects an analogy to a criminal trial where a 
key witness may determine the guilt or innocence of the defendant.
Thus the first step in solving many decision problems is to identify the
right kind of witness to look for.
For example, consider the problem of determining whether a given number
$N$ is prime.  Here a (counter-) witness would be a factor of $N$
(other than $1$ and $N$ itself).  If $N$ is composite,
it is easy to prove by simple division that the witness' claim is
correct.

In cases where the given number is prime, a witness of
a different kind needs to be searched for.  This search may involve
integers larger than $N$, and trying to summon every
integer sequentially as a witness would violate the requirement
of an algorithm to terminate in finite number of steps. {\it This is
often the main challenge in establishing decidability\/.}
%
% A natural way to surmount this problem is to place an upper bound
% (based on the structure of the problem) on the size of the witness
% so that all potential witnesses can be examined in a finite number
% of steps.  KSN: Note the important re-working of your point.
%
The difficulty can be surmounted if, based on the structure of the
problem, we can establish ahead of time an upper bound such that
if any witness exists at all, one exists that meets the bound.
Then a sufficient body of potential witnesses can be examined 
in a finite number of steps.  In the case of composite $N$,
the bound is $N$ itself.  For prime $N$, there is a known
polynomial $p$ such that a witness exists in the numbers between
$1$ and $2^{p(n)}$, where $n$ is the number of digits in $N$,
according to a certain witnessing scheme whose test for correct
claims is easy to compute. 
This kind of ``polynomial size-bounded witnessing scheme''
characterizes the important complexity class NP, and is discussed
much further in Chapter~33.

For another example, let us consider the special case of
Problem~\ref{problem-type0} where the given $G$ is a Type-1 grammar,
and we wish to determine whether a given string $x$ can
be generated from the start symbol $S$ of $G$.
A witness in
this case can be a sequence of sentential forms starting
from $S$ and ending with $x$ that forms a valid derivation in $G$.
The length of $x$
imposes a limit on the size of such sentential forms because
$G$ has no length-decreasing productions, and this in turn
defines a (much larger) limit on the number of sequences
that need be considered before all possibilities are exhausted.
Readers may find the details in a standard text such as~\cite{HU79}.

For one more example, consider the
full version of the linear programming problem
where one wishes to maximize a linear objective function $f$
over the set of feasible solutions $s$.
This set may be infinite,
and so a table-lookup through all values $f(s)$ cannot be used.
However, it is possible to
reduce the search domain to a finite set as follows. The feasible
solutions form a collection in $n$-dimensional space
(where $n$ is the number of variables plus the number of
constraints) known as a {\em convex polytope\/}.
Unless the polytope is empty or unbounded---cases that can be
detected and resolved---the polytope has a finite number of
``corner'' points, which are similar to the vertices of a polygon,
and which are easily computed.
In this case, it is known that a linear objective function attains
its maximum value at one (or more) of these corner points.
Thus we know the problem is decidable via 
table-lookup of values at the corner points.
In practice, there are intelligent algorithms that find
a maximum-giving corner point after searching (usually) only a small part
of this table.


\subsubsection{Use of Subroutines}\label{subsub.use}
This is more a programming technique than an algorithm design tool.
% 
% A central concept of programming is repetitive (or iterative) computation.
% We already observed how GOTO statements can be used to perform a
% sequence of steps repetitively.
% The idea of a subroutine is another central concept of programming.
% KSN: The point is a digression here---I expounded on it later.
%
The idea is to use one program $P$
as a single step in another program $Q$. Building programs from
simpler programs is a natural way to deal with the complexity of the
programmer's task.
A simple example is using a lookup to the times table as a
subroutine in multiplying two integers $i$ and $j$.
Let us examine this in the context of designing Turing machines,
where $i$ and $j$ are represented on the tape by
the string $1^i 0 1^j$ (namely, $i$ $1$s followed by a $0$ and then
by $j$ $1$s).
The basic idea of our GOTO program is  
to duplicate the string of $i$ $1$s $j-1$ times,
meanwhile erasing the string $1^j$ bit-by-bit to count the iterations.
A little thought reveals that our earlier GOTO program in
Figure~\ref{ravi.fig1} can {\em almost\/} be used verbatim as a
subroutine to call $j-1$ times.  The only hitch is that the
first call would run $2i$-many $1$s together so that
further calls would duplicate too many $1$s.  To fix the
problem, we introduce a new tape symbol $2$, using two
initial steps to convert the tape to $2 1^i 0 1^j$, and
``patch'' the subroutine so that it will not overwrite this $2$.
The new subroutine can be called by a line
``$k$: IF $2$ IS SCANNED GOTO $m$,'' where $m$ is the number of the
first line in the subroutine, and can return control to the
point of call by replacing its STOP instruction by
``IF $0$ IS SCANNED GOTO $k+1$.''  Careful writing will ensure that
this latter $0$ is the one initially separating $1^i$ from $1^j$.
The remaining details are left to the interested reader,
while performing a similar patch without using a new symbol ``2'' is 
left to the obsessive reader.
This subroutine mechanism is in fact no different from the one
programmers in BASIC have used for decades.
%
% My rendition makes the role of "2" much more plain, etc.  
% The bit with "obsessive" helps the next section.  --KSN
      

%\subsection{A Universal Algorithm}\label{sub.uni}
%
% Oops, NOT an "algorithm" as you defined it!  Gee willikers. --KSN
%
\subsection{A Universal Program}\label{sub.uni}
We will now solve Problem~\ref{problem-universal} by arguing the
existence of a program $U$ written in the GOTO language
that takes as input a program $P$ (also written in the 
GOTO language) and data $x$ for $P$, and that
produces the same output as $P$ does on input $x$, {\em if\/}
$P(x)$ halts and produces output at all.  
The last caveat hints that we shall only achieve a partial solution,
formally showing only that the function $U(P,x) = P(x)$ is
partial computable.

For convenience, we assume that all
programs written in the GOTO language use the fixed alphabet
$\{0,1,B\}$.  Since we have thus far used the full English
alphabet for the notation of our GOTO programs, we must
first address the issue of
what the formal input to the program $U$ will look like. 
This problem can be circumvented by {\em encoding\/}
each instruction using only $0$ and $1$.
The idea of such an encoding should not be mysterious---we could
refer to the $0$-$1$ encoding defined by the ASCII standard, which
the terminal used to type this chapter has already carried out
for these example programs.
However, we prefer the more-succinct
encoding defined by Table~\ref{ravitab}.  

\begin{table}
\caption{Encoding GOTO instructions.}
\label{ravitab}
\begin{center}
\begin{tabular}{|r|l|}\hline
 Instruction & Code \\ \hline
 PRINT $i$ & 000$1^{i+1}$ \\
 MOVE LEFT & 001 \\
 MOVE RIGHT & 010 \\
 IF $i$ IS SCANNED GOTO $j$ & $0111^j 01^{i+1}$ \\
 STOP & 100 \\ \hline
\end{tabular}
\end{center}
\end{table}

To encode an entire program, we simply write down in order (without the
line numbers) the code for each instruction as given in the table. For
example, here is the code for the doubling program shown in
Figure~\ref{ravi.fig1}: 
\[
0001001011110110001101001111111011000110100111011100.
\]
Note that the encoded string preserves all the information about the
program, so that one can easily reverse
the process to decode the string into a GOTO program.  From now on, if
$P$ is a program in the GOTO language,
$\code(P)$ will denote its binary encoding.
When there is no confusion, we will identify $P$ and
$\code(P)$.  We may also assume that all programs $P$ have a
unique STOP instruction that comes last.
This convention ensures that a input string to $U$ of the form
$w = \code(P)x$ can be parsed into its $P$ and $x$ components.
(When we consider decision problems we will use the code 100 for a unique
final ACCEPT instruction, and assign some other code to REJECT.)
Before proceeding further, readers
may test their understanding of the encoding/decoding
process by decoding the following string: $0100111011001001$.
%
% KSN: I appended "1001".  Oops, the vital "STOP" convention was missing,
% even earlier in the chapter.  Plural "readers" eliminated "his/her".
 

The basic idea behind the construction of a universal program is
simple, although the details involved in actually constructing one are
%
% enormous.
% KSN: Hardly---I've assigned undergraduates to do it on a Mac; see below.
%
substantial.
Turing in his original paper \cite{Turing}
exhibited a universal program in glorious gory detail, while
simpler constructions may be found in more-recent sources
such as~\cite{Rob}.
Here we will content ourselves with a sketch that conveys the 
central ideas.

$U$ has as its input a string $w$ of the form
$\code(P)x$.  (If $U$ is given an input string not of this form,
it can detect the flaw and immediately stop.)
% 
% To simulate the computational steps of $P$ on input $x$, $U$ 
% divides its tape into three segments, one containing the program
% $P$, one modeling the contents of the tape of
% $P$ as it changes with successive moves,
% and one containing the line number in $P$ of the instruction being
% currently simulated.  The second segment is initially occupied by $x$, 
% while the third is similar to a {\em program counter\/} in a real
% computer.
% KSN: I decided to eliminate the program counter, since it seemed to me
% to relinquish a nice advantage of the GOTO formalism, and doing so
% makes the simulation MUCH cleaner.
%
To simulate the computational steps of $P$ on input $x$, $U$ 
divides its tape into two segments, one containing the program
$P$, and one modeling the contents of the tape of
$P$ as it changes with successive moves.
The computation by $U$ consists of a sequence of {\em cycles\/},
each of which simulates one step by $P$ and is analogous to
an {\em REW cycle\/} (for ``read-evaluate-write'') in 
many real computer systems.
%
% Better analogy than a "CPU cycle".  --KSN

To execute a cycle, $U$ first needs to know the cell that the
``virtual'' tape head of $P$ is currently scanning,
and the instruction $P$ is currently executing.
We can assist $U$ by extending its own work alphabet
to include new ``alias'' symbols
%
% $0'$ and $1'$
% KSN: Oops, what about a scanned blank?
%
$0',1',B'$ for the characters of $P$.
$U$ maintains the condition that there is exactly one aliased symbol
in the ``$P$'' segment of its tape that marks the
encoding of the current instruction, and exactly one in the other
segment that marks the
cell currently scanned by $P$. 
For example, suppose that after thirty-nine steps, $P$
is reading the fourth symbol from the left on its tape containing 
$01001001$. Then the second tape segment of $U$ after 
thirty-nine cycles consists of the string
$0100'1001$.  We can further assist $U$ by adding a
symbol $\wedge$ to divide the two segments,
although the unique STOP instruction itself
could serve as the divider.  The computation by $U$ on an input
$w = \code(P)x$ can begin with some steps that
prime the first symbol of $\code(P)$, insert a $\wedge$
before the first symbol of $x$ (caterpillaring $x$ one cell to the right),
and prime the first symbol of $x$.
We may suppose that each cycle by $U$ begins with its own head
scanning the $\wedge$.

At the beginning of a 
new cycle, $U$ moves its head left to find the
current instruction, and begins decoding it.
The only information $U$ needs to retain is which type
of instruction it is, and in the case of a PRINT~$i$ or
IF~$i$\dots\ instruction, which character $i$ is involved.
To execute a PRINT~$i$, MOVE RIGHT, or MOVE LEFT instruction,
$P$ unprimes the instruction, primes the next one, and marches
down its tape to find the primed cell on its copy of $P$'s tape
and execute the action.  It is possible that a MOVE LEFT
instruction may bump into the $\wedge$, in which case $U$
makes another call to its ``caterpillar'' subroutine to
move $P$'s tape over, and inserts a $B'$ for the blank $P$ would
scan after that move.  
The only case that requires cumbersome action by $U$ is an
instruction IF~$i$ IS SCANNED GOTO $j$, when $U$ finds that
$P$ really is scanning character $i$.  Then $U$ needs to find the
$j$th instruction in the ``$P$'' part of its tape.
Because we have used a unary encoding $1^j$
of the required line number $j$, it is not
too difficult to write a subroutine that counts off the $1$s in $1^j$
and advances an instruction marker each time beginning from line $1$,
knowing to stop when the $j$th instruction has been located.
Finally, if the current instruction is STOP,
$U$ gleefully {\em erases\/} $P$, erases the $\wedge$, and
unprimes the scanned symbol, leaving exactly the final
output $P(x)$.

% KSN: Oops, the next point is important but was left out. 
%
One last refinement is needed to answer the objection that $U$
is using extra tape symbols $0',1',B',\wedge$ that we have 
expressly forbidden to GOTO programs.  This use can be eliminated by
one more level of encoding.  Give each of the seven tape symbols
its own three-bit code, and make $U$ treat blocks of three cells as
single cells in the simulation that was described above.
$U$ itself can be programmed to convert its input $\code(P)x$
to this encoding before the first cycle, and to invert it
when restoring the final output $P(x)$.
Then $U$ is a bona-fide GOTO program that meets all our
requirements.  It is even possible to run $U$ on input
$\code(U)w$ where $w = \code(P)x$,
producing (more slowly) the same output $P(x)$.
It is important to note that the code of $U$ itself is completely
independent of any program $P$ that might be simulated.
The code of $U$ itself is not long---a reader with good programming skill
can make it shorter than the prose description we have just given.
%
% Hmm...CRC says that they want this to be like a textbook, so here's
% an exercise.  BTW, it does make me like the GOTO formalism.  --KSN

Besides solving what was asked for in Problem~\ref{problem-universal},
we have also shown that Problem~\ref{problem-halting} is
partially decidable.  Namely, for any ``yes''-instance $w = \code(P)x$ where
$P$ on input $x$ halts, $U$ on input $w$ will eventually
detect that fact---and the slight edit of changing $U$'s own
STOP instruction to ACCEPT will make $U$ halt and accept $w$.
However, on a ``no''-instance where $P(x)$ does not halt, our $U$ will
blindly follow $P$ and not halt either.
The question is whether we can improve $U$ so that it will
{\em detect\/} every case in which $P(x)$ does not halt, and signal
this by executing a REJECT instruction.  
We will see in Section~\ref{undecide}
that all the programming skill in the world cannot
produce such a $U$---the halting problem is {\em un\/}decidable.

Before presenting undecidability, however, we develop a
fundamentally different way 
to formalize the notion of mechanical computability in the next
section.

\section{Recursive Function Theory}
The main advantage of using the class of {\em $\mu$-recursive\/}
functions to define computation is their
mathematical elegance.  Proofs about this class can be
presented in a rigorous and concise way, without long prose
descriptions or
complicated programs that are hard to verify.
These functions need and make no reference to any computational machine
model, so it is remarkable that they characterize ``mechanical''
computability.

An analogy to the two broad families of programming languages is
in order.  We have already discussed how Turing machines and our
particular ``GOTO'' formalism abstract the essence of
{\em imperative\/} programming languages, in which a program is a sequence
of operational commands and the major program structures are
subroutines and loops and other forms of {\em iteration\/}.
By contrast, specifications in recursive function theory
are {\em declarative\/}, and the major structures are
forms of {\em recursion\/}.  ``Declarative'' means that
a function $f$ is specified by a direct description of the
value $f(x)$ on a general argument $x$, as opposed to giving
steps to compute $f(x)$ on input $x$.
Often this description is {\em recursive\/}, meaning that 
$f(x)$ is defined in terms of values $f(y)$ on other
(usually smaller) arguments $y$.  Programming languages built on
declarative principles include Lisp, ML, and Haskell, which are
known as {\em functional languages\/}.  These languages have recursion
syntax that is not greatly different from the recursion schemes
presented here.
%
% Actually, functional languages were based on lambda calculus,
% another closely related notation to describe computations.
%
They also draw upon Church's {\em lambda calculus\/},
which can be called the world's first general programming language.
%
% KSN2: I moved the footnote after your insert.
% KSN: I usually eschew footnotes, but these are a digression that might
% be deleted.  Whereas I agree with your usage that "declarative"
% includes "functional", MANY use it to cordon off Prolog etc. from the
% functional languages, so my footnote is a sop to that.  Also,
% it's a tough call whether the lambda-calculus should have such offhand
% treatment.  It is after all a big part of the Church-Turing story, and
% it CAN be presented in a short, simple, and beautiful way.
% The treatment I have in mind actually starts by defining 
% {\em formal systems\/} as analogous to grammars but doing local
% rewriting on /trees/ rather than /strings/ (and allowing more than
% one argument in a rewrite step).  This embraces formal systems of
% logic and the lambda calculus in one go, and brings out the link
% between proofs and computations.  Editor--perhaps the lambda calculus
% is discussed in another chapter?  It might be useful for some
% practicioners to know about, and I could volunteer such a section
% for a future edition.  Authors---does one of the texts you already
% cite treat it?  Then we could refer readers there (NOT to Barendregt!).
%
%%% The book by N.D. Jones treats lambda calculus.
%%% We have added a reference to it.
%%% Being a Computability book makes this an attractive choice (compared to
%%%  Barendregt.)
%
A formal proof of equivalence between lambda calculus and the
Turing machine model
(via a programming language called $I$)
can be found in \cite{Jones}, which 
presents computability theory from a programming perspective.\footnote{
%
Turing created an addendum to his seminal paper \cite{Turing}
showing that his definition of a (partial) computable function
was equivalent to the one proposed by Church.
The lambda calculus uses essentially a single execution scheme
called {\em reduction\/} to govern its computations, and by
suitable conditioning one can make this scheme carry out recursion.
Another declarative language, Prolog, also fixes
a single execution scheme that tries to limit the operational
decisions the programmer needs to make, and also relies upon recursion.
}  %% end of fottnote.

In this section, we will describe this functional approach to computation
and
code some simple functions using recursion. Owing to space limitation,
we will not present a complete proof that the class of
{\em $\mu$-recursive\/} functions is the same as the class of
(partial) computable functions on a Turing machine.
The full proof can be found in standard texts such as
\cite{sudkamp}.
%
% Before we present a formal definition, let us look at some examples
% of function definitions.
% All the functions we will consider map tuples of nonnegative
% integers to integers, i.e., the inputs are positive
% integers (including 0) and the output is a single positive integer.
% KSN: no comment needed.
%
All the functions we consider have one or more non-negative integers
as arguments, and produce a single non-negative integer value.

Before presenting formal definitions, we qualify the above ideas
with a few examples.  Consider first the simple definition of a
two-variable linear function by
%
\begin{equation}\label{explicit-example}
h(y,z) = z + 2*y + 1.
% KSN: I changed your example for a visual parallel to one I inserted.
\end{equation}
%
Here $h(y,z)$ is defined with the aid of other functions
(here, plus and times) and quantities (here, 2 and 1) that
presumably have already been defined or given.
This is an example of an {\em explicit definition\/} because all
entities on the right-hand side are known---in particular,
this definition does not involve recursion.  If we rewrite
the infix functions $+$ and $*$ in prefix-function style as
``$\plus$'' and ``$\ittimes$,'' the expression becomes
%
\begin{equation}\label{prefix-example}
h(y,z) = \plus(z,\plus(\ittimes(2,y),1)),
\end{equation}
%
and we can glimpse another hallmark of functional languages:\
function names can be regarded as parameters the same way that variable
names can.  
Now consider the somewhat-similar definition of a one-variable function by
%
\begin{equation}\label{recursive-example}
f(x) = f(x-1) + 2*(x-1) + 1,
\end{equation}
%
together with a base case such as $f(0) = 0$.  Here not every quantity
on the right-hand side is known---one must first
know $f(x-1)$ to compute $f(x)$.  However, this is still
``declarative'' insofar as $f(x)$ is defined in terms of
known quantities and values $f(y)$ for other (smaller) arguments $y$.
The reader may check that this is a
recursive definition of the squaring function.

Why use recursion?  One reason is that explicit definition by
itself is known not to be powerful enough to capture the essence of
mechanical computation.
%
% Hmmm...is every language definable by explicit definition
% with arithmetic as the basis a CSL? rudimentary?  OK as is.  --KSN
%
The next two sections define the two principal schemes of recursion
in recursive function theory.
%
% KSN: I moved the examples to later contexts.
 

\subsection{Primitive Recursive Functions}
%
% Now we will precisely define the terms introduced above.
% Our goal is to define a collection of functions
% that map $k$-tuples of positive integers to positive integers.
% Such functions will be called {\it
% number-theoretic total} functions.
% Total is a redundant phrase to emphasize the fact that the function is
% defined for all possible $n$ -tuples of positive integers.
% (Later we will relax this condition and allow
% partial functions that may be undefined for certain $n$-tuples.)
% First we define the class of {\it
% primitive recursive functions} as follows.
% KSN: redundant.
%
The class of {\em primitive recursive functions\/} is built up
from the following set of {\em basic functions\/}, which are the
only ones we need to pre-suppose are ``known'':
%
\begin{enumerate}
\item
The {\em successor function\/} $S$ is defined for
all $x$ by $S(x)\ =\ x+1$.
\item
The {\em zero function\/} $Z$ is defined for all $x$ by $Z(x)\ = \ 0$.
The constant $0$ is also provided here.
\item
For all fixed numbers $i$ and $n$ with $1 \le i \le n$, the
{\em projection function\/} $p_i^n$ is defined for all
$n$-tuples $(x_1, x_2,\dots,x_n)$ by
$p_i^n(x_1, x_2,\dots, x_n)\ =\ x_i$.
\end{enumerate}

The primitive recursive functions are constructed from the basic functions
by applications of the following two operations.
The case $n=0$ is allowed in them; a $0$-variable function is the
same as a constant, and a $0$-tuple is the empty list.
%
% KSN: The original wording of what follows used "primitive recursive"
% inconsistently.  My highlighting makes it look much better, too.
%
\begin{enumerate}
\item
{\em Functional composition:\/}
Given $k$-many functions $g_1,\dots,g_k$ that each take $n$ variables,
and a function $h$ that takes $k$ variables, one can define a 
function $f$ of $n$ variables by
%
\begin{equation}
f(\seqn{x} = h(g_1(\seqn{x}), g_2(\seqn{x}),\ldots, g_k(\seqn{x})).
\end{equation}
%
If $g_1,\dots,g_k$ and $h$ are primitive recursive, then $f$ is
defined to be primitive recursive.
\item
{\em Primitive recursion:\/}
Given a function $g$ that takes $n$ variables, and a function $h$
that takes $n+2$ variables, one can define
a function $f$ of $n+1$ variables by
%
\begin{eqnarray}
f(\seqn{x},0) &~=~& g(\seqn{x});\label{basis}\\
f(\seqn{x},S(y)) &~=~& h(\seqn{x}, y, f(\seqn{x}, y)).\label{recursion}
\end{eqnarray}
%
If $g$ and $h$ are primitive recursive, then $f$ is defined to be
primitive recursive.
\end{enumerate}

Here (\ref{basis}) is the {\em basis\/} and (\ref{recursion})
is the {\em recursion step\/}.
It is conventional to call $\seqn{x}$ the {\em parameters\/}
and $y$ the {\em recursion variable\/}.  From a computational viewpoint,
the scheme is easy to interpret.
Given integer values for variables $\seqn{x}$ and $z$,
how can we evaluate $f(\seqn{x},z)$?
We start building a table $T$ in which each row $y$ contains the
value of $f(\seqn{x}, y)$.
The basis step gives us the top row via
$T[0] = f(\seqn{x},0) = g(\seqn{x})$.
Whenever we have filled a row $y$, we can fill the 
next row via the recursion step, via
$T[y+1] = f(\seqn{x},S(y)) = h(\seqn{x}, y, T[y])$.
As soon as row $z$ is filled, using $y$ such that $z = S(y)$,
we are done.
The point is that provided $g$ and $h$ are computable,
the function $f$ is also computable.
Functional composition likewise preserves computability.
Moreover, since the basic functions are all total and
produce non-negative values,
every function that we can build up in this manner is
also total and produces non-negative values.

\begin{definition}
\rm
A function is said to be {\bf primitive recursive}
if it can be built up from the successor, zero and
projection functions by
a finite number of applications of composition and primitive recursion.
\end{definition}


\begin{example}
\rm
To show how the scheme of primitive recursion models
the informal recursion defining the function $f$ of one variable
(so we have $n = 0$) in equation (\ref{recursive-example}),
take ``$g()$'' to be the constant $0$, and take $h$ to be the
two-variable function $h(y,z) = z + 2y + 1$, which happens to be
our example of ``explicit definition'' in (\ref{explicit-example}).
Then we have $f(0) = 0$ and
\[
f(S(y)) = h(y,f(y)) = f(y) + 2*y + 1.
\]
With ``$x-1$'' in place of ``$y$'' and ``$x$'' in place of ``$S(y)$,''
this is the same as (\ref{recursive-example}).  We will return to
this notational difference later.
\end{example}

As the prefix form (\ref{prefix-example}) indicates, $h$ itself
can be built up via functional composition from the 
{\em plus\/} and {\em times\/} functions.
It is interesting to see how the usual functions of
arithmetic can themselves be constructed from the 
rather Spartan basis we have been given.
To begin with, the constants $1,2,\dots$ are formally
introduced by functional composition,
with ``$g_1()$'' as the constant $0$ and ``$h$'' as the 
successor function,
via $1 = S(0)$, $2 = S(1) = S(S(0))$, $3 = S(2)$, and so on.

\begin{example}\label{addition}
\rm
{\em Addition\/}.
Take $g(x) = x$ and $h(x,y,z) = S(z)$.
Formally, $g$ is the basis function $p_1^1$,
and $h$ is the functional composition of the
successor function with $p_3^3$.  
Then primitive recursion gives us $\plus(x,0) = g(x) = x$ and
\[
\plus(x,S(y)) = h(x,y,\plus(x,y)) = S(\plus(x,y)) = S(x+y) = x+y+1,
\]
as we would demand.  Hence this formal
definition of $\plus$ correctly computes addition, and
we may use the standard ``$+$'' notation in the formal
examples that follow.
\end{example}

\begin{example}\label{multiplication}
\rm
{\em Multiplication\/}.
Take $g(x) = 0$ and $h(x,y,z) = x+z$.
Formally, $g$ is the zero function (of one variable rather than
the constant zero), and $h$ is the functional composition of
$\plus$ with the two functions $p_1^3$ and $p_3^3$ (so $k=2$ here).
Then primitive recursion gives us
$\ittimes(x,0) = g(x) = 0$ and
\[
\ittimes(x,S(y)) = h(x,y,\ittimes(x,y)) = x + \ittimes(x,y) = x*(y+1),
\]
again as we would demand.  Hence this formal
definition of $\ittimes$ correctly computes multiplication.
Note that we had to go to some length (of making $h$ a function of 3 variables)
so that our definition
exactly agrees with the formal requirements in equation (\ref{recursion}).
\end{example}


\begin{example}\label{exponentiation}
\rm
{\em Exponentiation}.
Take $g(x) = 1$ and $h(x,y,z) = x*z$.  Formally, $g$ is the
one-variable function that always outputs $1$ and is defined
by composing $S$ and the zero function $Z$, while $h$ is the same
as in Example~\ref{multiplication} but with $\ittimes$ in place of $\plus$.
Then primitive recursion gives us $\itexp(x,0) = g(x) = 1$ (note
that even $0^0$ equals $1$) and
\[
\itexp(x,S(y)) = h(x,y,\itexp(x,y)) = x*\itexp(x,y) = x^{y+1}.
\]
Once again the correctness of this definition for all
values of $x$ and $y$ is easy to verify,
via a simple proof by induction that follows the recursion.
\end{example}

It is now straightforward to omit some of the formal apparatus
and write the definitions more succinctly.
For instance, the last example becomes
\begin{eqnarray*}
\itexp(x,0) &=& 1\\
\itexp(x,y+1) &=& x*\itexp(x,y).
\end{eqnarray*}
This resembles a program one would actually write,
especially in a language like C that does not provide
exponentiation as a built-in operator.
%
% Well, the library function "pow" is written via iteration
% rather than recursion, but fair enough.  
% The points I raise /now/ are *important* to include.  --KSN

At this point the alert reader, 
%
% having noted our restriction
% of arguments and values to be non-negative numbers, and
% observing the tendency of composition and primitive recursion
% to make things ``more positive,''   %% My own writing--KSN
%
noting the way our schemes all involve non-negative numbers,
will first wonder how on earth we
can ever define {\em subtraction\/} this way.
The key is that the syntax of primitive recursion allows
us to define a function $P(y)$ that computes
``proper subtraction by~1,'' and then use $P$ to define
{\em proper subtraction\/} itself.  The word ``proper'' here
means that any negative value is replaced by $0$,
in order to maintain our restriction to the non-negative numbers.
The definitions are
\begin{eqnarray*}
P(0) &=& 0\\
P(S(y)) &=& y\\
\sub(x,0) &=& x\\
\sub(x,S(y)) &=& P(\sub(x,y))
\end{eqnarray*}
For $P$ we took $h(y,z) = y$, i.e.\ $h = p_1^2$, and for
$\sub$ we took $h(y,z) = P(z)$.
To trace this out,
$\sub(3,2) = P(\sub(3,1)) = P(P(\sub(3,0)) = P(P(3)) = P(2) = 1$,
and $\sub(2,3) = P(P(P(2))) = P(0) = 0$, which is the ``proper'' value.
%
% KSN: I read somewhere (but forget where) that the discovery of
% how to compute Predecessor in the lambda calculus (by Kleene?)
% took a long time and was regarded as *the* key step that
% told Church and company that they really had a foundation for
% all of mathematics.  That's part of why I want to include this.

Second, the reader may have felt uncomfortable defining
functions in terms of ``$S(y)$'' rather than ``$y$.''
For example, the primitive recursion for the factorial function,
with $0!$ standardly defined to be $1$, gives us
%
\[
\mbox{\tt fact(0) = 1  |  fact(y+1) = (y+1)*fact(y);}
\]
%
here ``{\verb+|+}'' separates the base and recursion cases.
This would actually be valid syntax in the programming language ML
{\em except\/} that 
``{\tt fact(y+1)}'' is an illegal function header.
The syntax of ML forces one to write it this way:\
%
\[
\mbox{\tt fact(0) = 1  |  fact(y) = y*fact(y-1);}
\]
%
this is literally the example used in many texts.
To make the formal equation (\ref{recursion}) for primitive recursion
reflect the syntax of programming languages, we can use $P$
in place of $S$ to change it to
%
\begin{equation}
f(\seqn{x},y)\ =\ h(\seqn{x}, y, f(\seqn{x}, P(y))),
\end{equation}
%
and alternately make the middle argument of $h$ be $P(y)$
instead of $y$.  Either way, one might then expect to be able to
recover the function $S$ by defining it in terms of $P$ and
the other two basis functions, just as we defined $P$
in terms of $S$ above.  However, this is impossible---one
could never define any increasing functions at all.
This curious asymmetry partly explains why 
primitive recursion was defined the way it is.
Nevertheless, if $S$ as well as $P$ is provided in the basis,
then one can use the modified definition and obtain
exactly the same class of primitive recursive functions.
For instance, addition is definable by
$\plus(x,0) = x~|~ \plus(x,y) = S(\plus(x,P(y)))$, and so on.
Hence primitive recursion is for the most part
exactly what ML and other functional languages {\em do\/}.\footnote{
%
Primitive recursion has its counterpart in imperative languages as well,
aside from the fact that most of them support recursion directly.
The ``table $T[y]$'' computation above shows how primitive recursion can be
simulated by a simple for-loop
{\bf for} $y$ = $0$ {\bf to} $z$ {\bf do\dots end} that fixes its bounds
and never alters $y$ in the loop body.  A theorem \cite{MEYER} in 
programming languages states that the primitive recursive functions are
exactly the total functions computable by programs that use only
if-then-else and simple nested for-loops.
} %% end of footnote
%
% KSN This footnote may be AOK in the main text.  Authors, editor?
% (!!check): I can cite the primary source unless one of your
% favorite texts has it.  It's Floyd's theorem---does Floyd-Beigel have it?
% I tried to skirt around the fact that Pascal as well as C programmers can
% pervert for-loops by reassigning the loop variable or etc.  Go Ada!

%%% Is n't this by Meyer and Ritchie? We have a reference to this paper.
%%% KSN2: You are probably right--I misrembered what Go:del, Escher, Bach
%%% says.  (BTW, they use "Church-Turing" Thesis.)

Finally, the reader may wonder what has become of 
functions defined on {\em strings\/}.
A string over an alphabet $\Sigma$ can always be identified 
with its number in the standard lexicographic enumeration of
$\Sigma^*$, with $\emptystring$ corresponding to $0$.
%
% Indeed, Perl does almost EXACTLY that.  --KSN
%
Then a string function $f: \Sigma^* \rightarrow \Sigma^*$ can be
called primitive recursive if the corresponding numerical
function (of one variable)
is primitive recursive.  For instance, the function that
appends a `1' to a binary string $x$ corresponds to $2x+2$.
Cutting the other way,
under some transparent encoding of negative and rational and
complex numbers (etc.) by strings, one can extend the
concept of primitive recursion to define addition and
multiplication and nearly all familiar mathematical
functions in their full generality.
%
% KSN: one could refer to Maple or Mathematica etc. here.  I figured it was
% not necessary to say that these functions would be "discretized".
%
The meaning and proof of the following statement should now be clear;
full detail can be found in~\cite{sudkamp}.

\begin{theorem}
Every primitive recursive function is computable by a Turing machine.
\end{theorem}

The converse is false, however.
A famous example of a computable total function that is not
primitive recursive is {\em Ackermann's function\/}; this and
other examples may be found in \cite{MCN}.
To obtain all computable functions we need to introduce one
more scheme of recursion---at the inevitable cost, however,
of opening a Pandora's box of functions that are no longer total.


\subsection{$\mu$-Recursive Functions}
We will add a new operation called {\it minimalization\/} that does not 
preserve totality.
Again we restrict numerical arguments to be non-negative integers.
%
% To define minimalization, we need to define a predicate first.
% KSN: No ya don't---the "= 0" or "= 1" way is quicker and better here.
% Since the formal definition given was a silly space-waster, I 
% rewrote all of this from scratch.

\begin{definition}\label{mu-recursive}
\rm
A possibly-partial
function $f$ of $n$ variables is defined by {\bf $\mu$-recursion\/}
from a function $g$ of $n+1$ variables, written
\[
f(\seqn{x}) = \mu y.g(\seqn{x},y),
\]
if whenever $f(\seqn{x})$ is defined, it equals the least
number $y$ such that $g(\seqn{x},y) = 1$.
If $f(\seqn{x})$ is undefined, there must be no $y$ such that
$g(\seqn{x},y) = 1$.
The class of {\bf $\mu$-recursive functions} is the class of
all functions that can be built up from the successor, zero,
and projection functions by the operations of 
composition, primitive recursion, and $\mu$-recursion.
\end{definition}

The computation of $f(\seqn{x})$ that is implicit in
Definition~\ref{mu-recursive} can be described by building a table
as before.  First fill in the row $T[0] = g(\seqn{x},0)$,
then $T[1] = g(\seqn{x},1)$, and so on.  If and when one finds
a $y$ whose value $T[y]$ equals $1$, halt and output $y$.
The ``if'' is the big difference from the algorithm for primitive
recursion, because if $g(\seqn{x},y)$ never takes the value $1$,
this procedure will never halt.  This procedure is called
an {\em unbounded search\/}.  Compared another way to primitive
recursion, $\mu$-recursion increments its recursion variable rather than
decrement it.

There is nothing special about ``$= 1$'' here:\ zero or any other constant
could be used instead.  Our use of $1$ suggests the
special case in which $g$ is a total function that takes on only the
values $0$ and $1$.  Then we can regard its output as a Boolean truth
value, with $1 = \mbox{true}$ and $0 = \mbox{false}$, and call $g$
a {\em predicate\/}.  The class of
$\mu$-recursive functions is not changed under the restriction that $g$
be a predicate.  Then we can read the syntax ``$\mu y.g(\seqn{x},y)$''
in English as ``the least $y$ such that $g(\seqn{x},y)$ is true.''
%
% (The $\mu$ stands for ``minimum'' and comes after Church's $\lambda$
% for the $\lambda$-calculus.)   %% KSN--my own writing.
%
{}From all this we can see that whereas primitive recursion corresponds to
a {\bf for} loop, $\mu$-recursion corresponds to a
{\bf while} loop, with $g(\dots)$ as the test condition.

\begin{example}\label{square-root}
\rm
{\em Partial square-root function.\/}
Define the predicate $g(x,y)$ to hold if and only if $x = y^2$.
Then the function $f$ defined for all $x$ by
$f(x) = \mu y.g(x,y)$ computes the square root of $x$ when $x$ is
a perfect square.  When $x$ is not a perfect square, however, the
recursion is undefined, so $f$ is a partial recursive function.
\end{example}

\begin{example}\label{mightaswellreallyuseLPsomewhere}
% KSN: This is needed to keep a promise made on page 1.
\rm
{\em Linear programming.\/}
The standard {\em simplex algorithm\/} uses a {\bf while}
loop that executes a basic {\em pivot step\/} until a
predicate expressing optimality holds.  Hence the function that
embodies the solution to a linear programming problem is
$\mu$-recursive.  In point of fact, because a bound on the
number of polytope corner points is explicitly definable from
the problem instance, the same function can be computed via a
simple {\bf for} loop, so it is primitive recursive.
However, the former method is usually much faster.
\end{example}

Part~(a) of the next
theorem expresses the fact that {\bf while} loops, together with
{\bf if-then-else}, suffice to make a general-purpose programming language.
Part~(b) is the gist of the famous theorem, credited in various
forms to various sources, that {\em at most one\/} {\bf while} {\em loop
is needed in any program\/}.

\begin{theorem}
\begin{enumerate}
\item[(a)]
A (partial) function is $\mu$-recursive if and only if it is a
Turing-computable (partial) function.
\item[(b)]
Moreover, given any Turing machine $T$, we can find a
primitive recursive function $u$ and a primitive recursive
predicate $t$ such that for all $x$,
$T(x) = u(\mu y.t(x,y))$.
\end{enumerate}
\end{theorem}

\noindent
In the standard proof of part (b), the predicate $t(x,y)$ is designed
to hold if and only if $y$ encodes the sequence of configurations
of a halting computation of $T$ on input $x$, and the function $u$
picks off the output from the final configuration.  To complete the
proof of (a), all one needs to show is that given a Turing machine that
computes $g$ in Definition~\ref{mu-recursive}, one can build a 
Turing machine that computes $f$.  This is done
by following the unbounded-search procedure sketched above.

The corresponding theorem for formal languages also merits mention here.
In Chapter~24 we defined the {\em characteristic function\/} of a
language $L$ to be the function $f_L$ defined for all $x$ by
$f_L(x) = 1$ if $x \in L$, $f_L(x) = 0$ if $x \notin L$.
This is simply the predicate corresponding to membership in $L$.
The {\em partial characteristic function\/} still takes the
value $1$ when $x \in L$, but is undefined when $x \notin L$.

\begin{theorem}
\begin{enumerate}
\item[(a)]
A language is recursive if and only if its characteristic function
is $\mu$-recursive.
\item[(b)]
A language is r.e.\ if and only if its partial characteristic function
is $\mu$-recursive.
\end{enumerate}
\end{theorem}

\noindent
Part (a) explains how the term ``recursive'' became applied to
languages and predicates as a synonym for
``decidable.''  It is important to recall that not all languages $L$
accepted by Turing machines have computable characteristic functions
(i.e., are decidable); unless we find a Turing machine accepting $L$
that halts for all inputs, all we know is that the {\em partial\/}
characteristic function of $L$ is (partial-) computable.  
Before proceeding to {\em un\/}decidable languages,
we take time to interpret these two theorems and others presented
in the two previous chapters. 


\section{Equivalence of Computational Models and the Church-Turing Thesis}
In Chapter~24 we introduced various machine models, the most important
of which is the Turing machine. In Chapter~25 we introduced
the grammar hierarchy of Chomsky, of which the most powerful was
the Type-0 grammar. Here we have presented the purely mathematical model
of $\mu$-recursive functions. Although these models were defined over
different domains for different purposes,
they are all equivalent in a precise technical
sense---they all define the same class of computable functions
and decidable languages, and the same class of
partial computable functions
and partially decidable languages.
%
% KSN: The authors attempted to fold functions and languages together,
% but they fell into a lurking trap:
% \begin{theorem}
% (i) [sentence with typo deleted]  (ii) The class of $\mu$-recursive
% predicates is the same as the class of predicates associated with the
% languages accepted by Turing machines.
% \end{theorem}
% KSN: Oops, the predicate P for a language L (in repetitive text I deleted)
% was just defined to be total, but for L = HP, P is not \mu-recursive.
% The rest of the chapter stamped their identification as unsuccessful, too.
% Hence I prefer to keep functions and languages separate.

% KSN: I wrote the following, then took it out.
% For instance, a language is partially decidable (by a Turing machine)
% if and only if it can be generated by a type-0 grammar,
% if and only if its partial characteristic function is $\mu$-recursive.
% Since in Chapter~24 we discussed how a function $f$ may be computed
% by solving an associated decision problem, and since the
% difference between ``r.e.'' and ``recursive'' in all cases depends
% only on whether we demand a finite answer when the true answer
% is ``no,'' we can summarize all this by saying that Turing machines,
%
We can summarize all this by saying that Turing machines,
type-$0$ grammars, and $\mu$-recursive functions have the same
problem-solving power.

This equivalence extends to vastly many other computational models,
of which we mention a few:
%
\begin{enumerate} 
\item[(1)]
{\em Cellular Automata.\/}
Cellular automata are intended to
model the evolution of a colony of micro-organisms. Each cell is a 
deterministic finite
automaton that receives its input in discrete time steps
from neighboring cells,
so that its current state is defined by its own previous state and the
previous states of its neighbors.
All the cells execute the same DFA.
There are different schemes for specifying the representation of
the input to a cellular automaton and its output.
But under any reasonable
scheme, the largest class of problems that can be solved on cellular automata 
coincides with the class of solvable problems on a Turing machine.
\item[(2)]
{\em String-Rewriting Systems\/}
A string-rewriting system is similar to a
grammar. The main difference is that there are no non-terminals. 
Let the input alphabet be $\Sigma$. The production rules of a rewriting system
$T$ will be of the form $\alpha \rightarrow \beta$ where $\alpha$
and $\beta$ are 
strings over $\Sigma$.
One can apply such a rule by replacing any occurrence of
$\alpha$ in a string by $\beta$.
%
% If one requires that {\em all\/} occurrences be replaced in the
% same step, then one has a {\em Lindenmeyer L-system\/}.  [was KSN]
%
$T$ is defined as a finite set of rewrite
rules, along with a finite set of initial strings.
The language generated by $T$
is defined as the set of strings that can be obtained from an
initial string by
applying the rewrite rules a finite number of times.
The systems proposed before 1930 by Thue and Post fall roughly
into this category.
It turns out that the class of string-rewriting languages 
is the same as the r.e.\ languages (see ~\cite{Book and Otto}).
\item[(3)]
{\em Tree-Rewriting Systems.\/}
These are similar to string-rewriting systems except that the
local edits are done on subtrees of a tree, and rules may have
more than one argument.  
The subtrees typically represent {\em terms\/} in algebraic
or logical expressions that are being operated on.
Under reasonable schemes for encoding
numbers or strings by trees, all known tree-rewriting systems
generate r.e.\ languages or compute partial recursive functions.
Church's {\em $\lambda$-calculus\/} and most formal systems of
logic fall into this category.
%
% could plug Maple and equational solvers in general here.
\item[(4)]
{\em Extensions of Turing's Model.\/}
As mentioned in Chapter~24,
one can also create numerous modifications to the
basic Turing machine model, such as having multi-dimensional tapes
or binary trees with MOVE UP, MOVE DOWN LEFT, and MOVE DOWN RIGHT
instructions (the latter are tantamount to having random-access
to stored values), allowing nondeterminism or alternation,
making computation probabilistic (see Chapter~29, Section~2), and so on.
All of these machines compute the same functions as the simple
one-tape Turing machine.
\item[(5)]
{\em Random-Access Machines and High-Level Programming Languages.\/}
These can be mentioned in tandem because a RAM, as 
described in Chapter~24, is just an idealization of assembly
or machine language.  Every high-level language yet devised can be
compiled into some machine language.
Even the standard {\em Java Virtual Machine\/} is little more
than a RAM, with some added handling of class
objects via pointers that is not unlike the workings of a
pointer machine, and some hooks to enable the host system to
control physical devices and network communications.
Without excessive effort one can extend the construction of a
universal Turing machine in Section~2 to handle the case where
$P$ is a RAM program rather than a GOTO program.
%
% To me this is a second real conceptual payoff of "GOTO".  --KSN
%
The registers of $P$ can be simulated on the tape by adding one
more tape symbol $\#$ and using strings of the form
$\#i\#j\#$, where $i$ is the register's number and $j$ is its contents.
As stated in Chapter~24, Section~4, this simulation is even fairly
efficient.  Hence all these high-level languages have the same
problem-solving power as the lowly one-tape Turing machine.
\end{enumerate}

The convergence of so many disparate formal models on the
same class of languages or functions is the main evidence for
the assertion that they all exactly capture the informal
notion of what is mechanically or humanly computable.
%
% KSN: I originally tried to tell "The Full Story" in some
% entertaining prose that is commented-out below, which also
% would parallel the discussion in Allender's Chapter 33, but
% felt that shorter would be better.
%
This assertion is called the {\bf Church-Turing thesis}.
In one form, it asserts that
every problem that is humanly solvable is solvable by a Turing machine.
Put more precisely, any cognitive process that a human being could
or will ever use to distinguish certain numbers or strings as ``good''
defines an r.e.\ language---and if it also would determine that any
other given number or string is ``bad,'' it defines a recursive language.
An extension of the thesis claims that
no one will ever design a physical device to compute
functions that are not $\mu$-recursive.
The Church-Turing thesis is not a mathematical conjecture and is not
subject to mathematical proof; it is not even clear whether the
extension is resolvable scientifically.


% This assertion has been phrased in various forms, three of which
% we state below.  
% It is sometimes ascribed to Church alone, on the feeling that his claim
% (with ``$\lambda$-calculus'' in place of ``Turing machine'')
% antedated Turing's 1936 paper, but they had a joint role in that paper,
% and its importance is so great that the joint attribution is
% usually felt most appropriate.
% %
% % It is also vital for N.A.--U.K. relations, ask MI6 :-) KSN
% 
% \bigskip
% \noindent
% {\bf Church-Turing Thesis.}
% \begin{enumerate}
% \item[(a)]
% Every problem that is humanly solvable is solvable by a Turing machine.
% Put more precisely, any cognitive process that a human being could
% or will ever use to distinguish certain numbers or strings as ``good''
% defines an r.e.\ language---and if it also would determine that any
% other given number or string is ``bad,'' it defines a recursive language.
% \item[(b)]
% No one will ever design a physical device to compute
% functions that are not $\mu$-recursive.
% \item[(c)]
% No one will ever design a programming language that can be
% executed to compute functions that are not $\mu$-recursive.
% \end{enumerate}
% 
% \bigskip
% Form (a) is still hotly debated as discussed next.  Statement (b)
% recently came under threat with the advent of
% {\em quantum computation\/},
% but the model of a {\em quantum Turing machine\/} that is
% currently felt to represent quantum devices we can conceivably build
% abides by the Church-Turing thesis.  
% Statement (c) is essentially a corollary of (a) and (b) and
% finds wide agreement by itself.  Indeed, most agree that any
% cognitive process (or decision procedure)
% {\em that can be specified in a natural language\/}
% such as English or Chinese must define an r.e.\ (or recursive) set.
% Certain texts such as \cite{Rogers} say they are ``making an appeal
% to Church's thesis'' when they are describing a computational
% process in natural-language prose, such as ours for the universal Turing
% machine in Section~2.  It is important to note that they are
% using only this universally-accepted form of (c), and in all
% examples the formal details can readily (if laboriously) be supplied.
% As shown in Chapter~24, {\em oracle\/} Turing machines can decide
% nonrecursive languages, but the oracle is such that they can never
% be executed.
% 
% 
% The Church-Turing thesis is sometimes paraphrased as the assertion
% that ``every human being is equivalent to a computer.''
% That is, given a discrete encoding of sensory data as
% Turing outlined, for every human being there is a Turing machine that
% given the same input would make the same decisions and actions.
% For some people this statement is patently obviously true---a human
% being is a computer 
% %
% % with an estimated 100 gigabytes of storage
% %
% whose circuits happen to be based on carbon
% rather than silicon, a sophisticated web-crawling program for the
% world as World Wide Web.
% This goes for aliens as well.
% Others leave open the possibility that human beings may have special
% originating genius or may react to input of a non-local, non-encodable
% kind.  Some, championed recently by the Oxford mathematical physicist
% Roger Penrose, argue concretely
% that nondeterministic and/or non-local
% effects of quantum mechanics may be the source of such genius or input.
% The Church-Turing thesis is more a scientific hypothesis
% than a mathematical conjecture.  It is not subject to
% mathematical proof, and may not even
% be resolvable scientifically.

\comment{
} %% end of \comment

\comment{Finally, there is an effective way to transform a
given Turing machine $T$ into a set of equations in variables
$x,y_1,\dots,y_m$ such that for any $x$, $T$ on input $x$
halts if and only if the other $m$ variables can be set to solve
the equations.  This reduction shows that Hilbert's tenth
problem is undecidable.  
%
% if you want, you can remark that m can be fixed to be 9 here,
% and whether it can go as low as 3 is open.  --KSN
}

\section{Undecidability}\label{undecide}
% Recall the definition of an undecidable problem. In this section, we
% will establish the undecidability of Problem 2
% Section~\ref{sub.some}. The simplest way to establish the existence of
% undecidable problems is as follows: 
% There are more problems than there are programs, the former set being
% uncountable while the latter is countably infinite.
% But this argument is existential, and does not
% identify any specific problem as undecidable. In any case, what matters to us
% is whether problems arising from practical applications are decidable.
% In what follows, we will show that Problem 2 introduced in Section 2.2
% is one such problem.
%
% KSN: The inconsistent reference to "Problem 2, Section ?" made me wonder
% about the proofreading...and on my end the psychology becomes: "if I have
% to be in for a dime, might as well be in for a dollar...plus I noticed that
% if people take "problem"=="statable problem", a change was needed anyway.
% That's why I had to "put my oar in" so much...

The Church-Turing thesis implies that if a language is undecidable in the
formal sense defined above, then the problem it represents is
really, humanly, physically undecidable.
The existence of languages that are not even partially decidable 
can be established by a counting argument:\ Turing machines can be
counted $1,2,3,\dots$, but the mathematician Georg Cantor
proved that the totality of all sets of integers cannot be so counted.
Hence there are sets left over that are not accepted, let alone decided,
by any program.  This argument, however, does not apply to languages
or problems {\em that one can state\/}, since these are also countable.
The remarkable fact is that many easily-stated problems of high practical
relevance are undecidable.  This section shows that the five remaining
problems on our list in Section~\ref{sub.some}, namely
\ref{problem-halting}--\ref{problem-tiling} and \ref{problem-Hilbert},
are all unsolvable.

\subsection{Diagonalization and Self-reference}\label{sub.dia}
Undecidability is inextricably tied to the concept of {\em self-reference\/},
and so we begin by looking at this perplexing and sometimes paradoxical
concept.
% The idea of self-reference seems to be many centuries old, 
% and may have originated with a barber of Seville (in ancient Greece) who...
%
% KSN: Too much, too soon...and probably not the "origin"...better to
% start with the simplest and clearest short examples.
%
The simplest examples of self-referential paradox are statements such as
``This statement is false'' and ``Right now I am lying.''  If the former
statement is true, then by what it says, it is false; and if false,
it is true\dots
The idea and effects of self-reference go back to antiquity; a version of
the latter ``liar'' paradox ascribed to the Cretan poet Epimenides
even found its way into the New Testament, Titus 1:12--13.
%
% KSN: namely, in the RSV: ``One of themselves\dots said
%`Cretans are always liars\dots'  This testimony is true.''
% But NB--this one has an "out": E. is lying, but some Cretans are truthful
% (and the NT isn't:-).
%
For a more-colorful example, picture a
barber of Seville hanging out an advertisement reading,  
%
% ``I shave all those who do not shave themselves.''
% When the statement is applied to the barber himself, we get a
% self-contradictory statement.  Does he shave himself?
% If the answer is ``yes'', then he is one of those who shaves himself,
% and so the barber should not shave him.
%
% KSN: With this one, you have to make absolutely sure that the reader who
% doesn't already know it will not read the prose assertion as:
% "for all x, (x does not shave himself) --> (I shave x)"
% ---in which case, your last clause does not follow and there's no paradox.
% Either we need more words of description as Russell chose, or we need
% something in place of "all" to make "<-->" in place of "-->" clear.
% Admittedly "exactly those" or "precisely those" are clumsy, so I
% chose the empty word, and tightened the argument to clarify the point.
%
``I shave those who do not shave themselves.''
When the statement is applied to the barber himself, we need to ask:
Does he shave himself?  If {\em yes\/}, then he is one
of those who do shave themselves, which are not the people his statement
says he shaves.
The contrary answer {\em no\/} is equally untenable.
Hence the statement can be neither true nor false
(it may be good ad copy), and this is the essence of the paradox.
Such paradoxes have made entry into modern mathematics 
in various forms. We will present some more examples in the next few
paragraphs.
Many variations on the theme of self-reference can be found in the books
of the logician and puzzlist Raymond Smullyan, including 
\cite{Sm1} and \cite{Sm2}.

{\em Berry's paradox\/} concerns English descriptions of natural numbers. 
For example, the number 24 can be described by many different phrases:
``twenty-four,'' ``six
times four,'' ``four factorial,'' etc.
We are interested in the {\em shortest\/}
of such descriptions, namely
%
% the one with the fewest letters in it.
% KSN: Not well-defined, and the necessity to fix one "fewer than" that was
% missing a clumsy "or equal" below led me to make some other tweaks.  
%
one(s) having the fewest letters. 
Here, ``two dozen'' beats all of the above.
Clearly there are
(infinitely) many positive integers whose shortest descriptions require
one hundred letters or more. (A simple counting argument can be used to show
this. The set of positive integers is infinite, but the set of positive
integers with English descriptions of fewer than
one hundred letters is finite.) Let $D$ denote the
set of positive integers that do not have English descriptions of
fewer than one hundred letters. Thus $D$ is not empty. It is a well-known fact in set theory
that any nonempty subset of positive integers has a smallest integer. Let
$x$ be the smallest integer in $D$. Does $x$ have an English description
of fewer than one hundred letters?  By the definition of the set 
$D$ and $x$, the answer is {\em yes\/}:
such a description of $x$ is, ``the smallest
positive integer that cannot be described in English in fewer than one
hundred letters.''  This is an absurdity 
because the quoted part of the last sentence
is clearly a description of $x$, and it contains fewer than one hundred
letters.
%
% A similar paradox...   
% KSN: better treated as a separate pgh and linked with the barbers...

{\em Russell's paradox\/} similarly turns on issues in defining
sets.  In formal mathematics, we can perfectly easily describe
``the set of all sets
that do not include themselves as elements'' by the definition
$S = \{ x| x \notin x\}$.
The question ``Is \( S \in S \)?'' leads to a real conundrum.
This also resembles the barber paradox, with ``$\notin$'' read as
``does not shave.''  This paradox forced the realization that
the formal notion of a {\em set\/}, and importantly the formal
rules that apply to sets, do not and cannot apply to everything that
we informally regard as being a ``set.''

Our last example is a charming paradox
named for the mathematician William Zwicker.
% 
% Consider the collection of
% all two person games (such as chess, tic-tac-toe, etc.) in which
% players make alternate moves until one of them loses.
% KSN: Umm...no one should ever lose at tic-tac-toe...I'm forced to fix it!
%
Consider the collection of all two-person games that are {\em normal\/}
in the sense that every play of the game must end after a finite
number of moves.  Tic-tac-toe is normal since it always ends
within nine moves, while chess is normal because the official
``fifty move rule'' prevents games from going on forever.
Now here is
{\em hypergame\/}. In the first move of hypergame, the first player
calls out a normal game---and then the two players go on to play that 
game, with the second player making the first move. 
Now we need to ask, ``Is hypergame normal?'' If {\em yes\/}, then
it is legal for the first player to call out ``hypergame!''---since
it is a normal game.  By the rules, the second player must then
play the first move of hypergame---and this move can be
calling out ``hypergame!''  Thus the players can keep saying
``hypergame'' without end, but this contradicts the definition of a normal
game.  On the other hand, suppose hypergame is not normal.  Then in the
first move, player 1 cannot call out hypergame and must call a normal
game instead---so that the infinite move sequence given above is not
possible and hypergame is normal after all!

Let us try to implement Zwicker's paradox.  To play hypergame, we
need a way of formalizing and encoding the rules of a game as a
string $x$, and we need a decision procedure {\tt isNormal(x)}
to tell if the game is normal.  Then the rules of hypergame are
easily formalized:\ pick a string $x$, verify {\tt isNormal(}$x${\tt)},
and play game $x$.  Let $h$ be the string encoding of these rules.
Now we get a real contradiction 
when {\tt isNormal(}$h${\tt)} is run.
We must conclude that either (i) our formalization of games is
inadequate or inconsistent, or (ii) a decision procedure
{\tt isNormal} simply cannot exist.
Now (i) is the way out for Russell's paradox with ``sets'' in place of 
``games.''
For {\em computation\/}, however, we know
that our formalization is adequate and consistent---and hence we will
be faced with conclusions of type (ii), 
namely that our corresponding computational problems are unsolvable.
%
% NB: The eeriest aspect of Zwicker's paradox for me is that we can
% make (i) the culprit by formalizing "game" so that there are only
% two games, chess and hypergame.  Then the set of normal "game"s is
% finite and hence decidable---but we still have the paradox.  --KSN

Before showing how the above paradoxes
can be modified and ingrained into our problems, we need to review the 0-1
encoding of GOTO programs from Section~2.2, including the conventions that
ACCEPT has the same code 100 as STOP for programs that accept languages,
and that such an ACCEPT statement be last and unique.
We may assign the code 101 to REJECT, which may appear anywhere.
If a binary string $x$ encodes a program $P$, it is easy to decode
$x$ into $P$, and we may identify $x$ with $P$.
If $x$ does not encode a legal GOTO program, this fact is easy to
detect.  Then we may choose to treat $x$ as an alternate code for the
trivial GOTO program that consists of a single REJECT statement.

Now we can define the so-called ``diagonal language''
$L_d$ as follows:
%
% KSN: Sorry, changed my mind, lowercase d to match "L_u, L_h" in Chapter 24.
%
\begin{equation}\label{diagonal}
L_d\ =\ \{x ~|~\mbox{$x$ is a GOTO program that
does not accept the string $x$}\}
\end{equation}
%
This language consists of all programs in the
GOTO language that do not halt in
the ACCEPT statement when given their own encoding as input---they may
either REJECT or not halt at all on that input.
For example, consider $x = 01111101101100$, which encodes a 
program that accepts any string
beginning with~1 and rejects any string beginning with~0.
Then $x \in L_d$ since the program does not accept $01111101101100$.
Note the self-reference in (\ref{diagonal}).  Although the definition of
$L_d$ seems artificial, its importance will become
clear when we use it to show the undecidability of
other problems.  First we prove that $L_d$ is not even accepted by
any Turing machine, let alone decided by one.

\begin{theorem}
$L_d$ is not recursively enumerable.
\end{theorem}

\begin{proof}
Suppose for the sake of contradiction that $L_d$ is r.e.
Then there is a GOTO program that accepts $L_d$---call it $P$.
Now what does $P$ do on input $x = \code(P)$?
If $P$ accepts $x$, then $x$ is not in $L_d$, but this contradicts
$L(P) = L_d$.  But if $P$ does not accept $x$, then $x$ {\em is\/} in $L_d$,
and this also contradicts $L(P) = L_d$.  Hence a program $P$ such
that $L(P) = L_d$ cannot exist, and so $L_d$ is not r.e. 
\end{proof}

The definition of $L_d$ is motivated by Russell's paradox,
reading ``$\notin$'' as ``does not accept.''
Whereas in Russell's paradox we had to conclude that $S$ is not a
{\em set\/}, here we conclude that $L_d$ is not a
{\em Turing-acceptable\/} set.

We can similarly carry over Zwicker's paradox by treating a given string
$x$ as formally defining ``Game-$x$'' as follows: The first player
decodes $x$ into a GOTO program $P$, and then tries to choose
some string $x'$ in the language $L(P)$.  If $L(P)$ is empty, in particular
if $x$ decodes to the trivial program ``1. REJECT'' as stipulated above,
then the game ends then and there.  But if the first player finds
such an $x'$, then the second player must play the same way with $x'$.
Then we can say that $x$ is {\em normal\/} if every play of Game-$x$
must terminate (by reaching a GOTO program that
accepts the empty language) in a finite number of steps.
Finally define $L_Z$ to be the set of normal strings.
By applying the reasoning from Zwicker's paradox, one can imitate the
above proof to show that $L_Z$ is not recursively enumerable.
%
% KSN: That's as far as I was able to get.
% I would like to see the paragraph on Berry's paradox restored
% in connection to showing the string-compression function *uncomputable*. 


\subsection{Reductions and More Undecidable Problems}\label{sub.red}

Recall from Chapter 24 (section 2.3) the notion of Turing reducibility.
This is because a language $L_1$ is Turing reducible to $L_2$ if there
is a halting Turing machine for language $L_1$
using an oracle for language $L_2$.
If $L_1$ is reducible to $L_2$ and $L_2$ is decidable, 
then so is $L_1$.
Basically, one can replace queries to oracles by executing a halting
computation for $L_2$. The contrapositive of this statement can be used to show
undecidability. If $L_1$ is undecidable, then so is $L_2$.
We will first express Problem (2) as a language:
\[
L_U = \{ code(P)111x : P \mbox{~accepts the string $x$}\}.
\]
Thus $L_U$ takes as input a program in GOTO,
and a binary string $x$, and accepts the encoded
pair $(P,x)$ if and only if $P$ accepts $x$.
(Note 111 is used as a separator between $P$ and $x$.)
The universal program presented in Section 2.2 accepts
the language $L_U$ hence it is 
recursively enumerable.
We will show that $L_U$ is not recursive. First, we will show a simple
fact about recursive languages.

\begin{theorem}
Recursive languages are closed under complement.
\end{theorem}

\begin{proof}
Let $P$ be a GOTO program for language $L$. The program $P'$ obtained
by interchanging the ACCEPT and REJECT instructions
is easily seen to accept the language $\bar L$.
This standard trick works to complement the computations of
most of the deterministic devices
(such as DFA).  
\end{proof}

Now we show that $L_U$ is not recursive.

\begin{theorem}
$L_U$ is not recursive. 
\end{theorem}

\begin{proof}
Consider the language
$L'_U$ = $\{x|$ $x$ when interpreted as a GOTO
program accepts its own encoding$\}$.
Obviously, $L'_U$ = ${\bar L_d}$.
Since $L_d$ is not
recursively enumerable, it is not recursive.
(Recall that the set of recursive
languages is a subset of recursively enumerable languages.)
By the above theorem, $L'_U$ is not recursive.
Finally, note that $L'_U$ can be reduced to $L_U$ as follows: Given
an algorithm for $L_U$,
we can construct an algorithm for $L'_U$ as follows: Let $P$
be an algorithm for $L_U$.
To construct an algorithm for $L'_U$ simply note the connection
between the two problems.
An input string $x$ belongs to $L'_U$ if and only if $x111x$
belongs to $L_U$.
Thus, a simple copy program (similar to one presented in Section 2)
can be first used to convert the input $x$ into $x 111 x$.
Move the scanning head back
to the leftmost character of the first copy of $x$.
Now simply run the program $P$.
Note that the program $P'$ described above is being constructed
using only $P$, not $x$.
This reduction shows that $L_U$ is not recursive.
\end{proof}

Next we consider problem~3 in our list.
Earlier we showed that a special case of this
problem (when the input is restricted to type-1 grammar) is totally solvable.
It is not hard
to see that the general problem is partially solvable.
(To see this, suppose there is a
derivation for a string $x$ starting from $S$,
the start symbol of the grammar.
Suppose the length of one such derivation is $k$.
A program can try all possible derivations of
length 1, 2, etc.\ until it succeeds.
Such a program will always halt on strings $x$ generated
by the grammar $G$. Thus the language
\[
L_0 = \{G\#x : G \mbox{~is a type-0 grammar and $x$
can be generated by $G$}\}
\]
is recursively enumerable.
A standard result from formal language theory \cite{HU79} is that for every
Turing machine $M$, there is a type-0 grammar $G$ such that $L(M)$ = $T(G)$.
This conversion from $M$ to $G$
is the reduction that shows that the language $L_0$ is not recursive.

The string compression problem, numbered~4 on our list, is not a
decision problem, but reduction techniques can still be used to show
that it is unsolvable.  We refer the reader to \cite{LV} for details.

By a fairly elaborate reduction (from $L_d$), it
can be shown that tiling problem~5 in our list
is also not partially decidable.
We will not do it here and
refer the interested reader to ~\cite{Harel}.
But we would like to point out 
how the undecidability result can be used to
infer a result about {\it aperiodic tilings}. 
This deduction is interesting
because the result appears to have some deep implications 
and is hard to deduce directly.
We need the following discussion 
before we can state the result. 
A different way to pose the tiling problem is
whether a given set of tiles can tile
{\em an entire plane} in such a way that all the adjacent tiles
have the same color on the meeting quarter.
(Note that this question is different from the way
we originally posed it:
Can a given set of tiles tile any {\em finite\/} rectangular region?
Interstingly, the two problems are identical in
the sense that the answer to one version is
``yes'' if and only if it is ``yes'' for the other version.)
Call a tiling of the plane {\em periodic\/}
if one can identify a $k \times k$ square such
that the the entire tiling is made by repeating
this $k \times k$ square tile.
Otherwise, call it {\em aperiodic\/}. 
Consider the question:
Is there a (finite) set of unit tiles that can tile the
plane, but only aperiodically? The answer is ``yes''
and can be deduced from
the total undecidability of the tiling problem.
Suppose the answer is ``no''. Then, for any
given set of tiles, the entire plane can be tiled if and only if the plane 
can be tiled periodically.
But such a periodic tiling can be found, if one exists,
by trying to tile a $k \times k$
region for successively increasing values of $k$.
This process will eventually succeed (in a finite number
of steps) if the tiling exists.
This would make the tiling problem partially decidable, which contradicts
the total undecidability of the problem.
This means that the assumption that the entire plane can be tiled
if and only if some $k \times k$ region can be tiled is wrong.
Thus there must exist a finite set of tiles that
can tile the entire plane, but only aperiodically.

We conclude with a brief remark about problem~7 in our list.
After many years of effort by several
mathematicians and computer scientists (including Davis
and Robinson), Matiyasevich found 
an effective way to transform a
given Turing machine $T$ into a set of equations in variables
$x,y_1,\dots,y_m$ such that for any $x$, $T$ on input $x$
halts if and only if the other $m$ variables can be set to solve
the equations. 
This reduction shows that Hilbert's tenth
problem is undecidable.
Details behind this reduction can be found in \cite{floyd}.


\section{Defining Terms} 

\noindent
{\bf Decision Problem:} A computational problem with a yes/no answer.
Equivalently, a function whose range consists of two values $\{0,1\}$.

\noindent
{\bf Decidable Problem:} A decision problem that can be solved by a GOTO
program that halts on all inputs in a finite number of steps. For emphasis,
the equivalent term {\it totally decidable} problem is used. The associated
language is called {\bf recursive}.

\noindent
{\bf Partially Decidable Problem:}
A decision problem that can be solved by a GOTO
program that halts (and outputs ACCEPT) on all yes-instances. The program may
or may not halt on no-instances. Equivalently, the collection of yes-instance
strings forms a type-0 language. (See Chapter 25.)

\noindent
{\bf Recursively Enumerable Language:} Same as partially decidable language.

\noindent
{\bf $\mu$-Recursive Function:} A function that is a basic function (Zero,
Successor or Projection), or one that can be obtained from other $\mu$-recursive
functions using composition and $\mu$-recursion.

\noindent
{\bf Recursive Language:} A language that can be accepted by a GOTO program that
halts on all inputs. The associated problem is called {\bf decidable}.

\noindent
{\bf Solvable Problem:} A computational problem that can be solved by a halting
GOTO program. The problem may have a non-binary output.

\noindent
{\bf Totally Undecidable Problem:} A problem that cannot be solved by a GOTO
program. Equivalently, one for which
the set of yes instance strings is not a type-0 language.

\noindent
{\bf Undecidable Problem:} A decision problem that is not (totally) decidable.
It could be partially decidable or totally undecidable.

\noindent
{\bf Universal Turing Machine:} A Turing machine that can simulate any other
Turing machine. 

\noindent
{\bf Unsolvable Problem:} A computational problem that is not solvable.
The associated function is called an uncomputable function.

\begin{thebibliography}{99}
\setlength{\baselineskip}{0.6\baselineskip}
\bibitem[Book, 1993]{Book and Otto}
	Book, R. and Otto, F. 1993
	{\it String Rewriting Systems}.
	Springer-Verlag, Berlin.
\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[Davis, 1958]{Davis1}
	 Davis, M. 1958. 
	 {\it Computability and Unsolvability}
	 McGraw-Hill, New York.
\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[Harrison, 1978]{Harrison}
        Harrison, M. 1978.
        {\it Introduction to Formal Language Theory}.
        Addison-Wesley, Reading, MA.
\bibitem[Hartmanis, 1994]{hartmanis}
        Hartmanis, J. 1994.
        On computational complexity and the nature of computer science.
        {\it Communications of the ACM}. 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[Jones 1997]{Jones}
	 Jones, N.D. 1997.
	 {\it Computability and Complexity from a Programming Perspective.}
	 MIT Press, Cambridge, MA.
\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[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[Li and Vit\'{a}nyi, 1997]{LV}
        Li, M. and Vit\'{a}nyi, P. 1997.
        {\it An Introduction to Kolmogorov Complexity and Its Applications,
        2nd ed.}
        Springer Verlag.
\bibitem[Meyer and Ritchie]{MEYER}
	 Meyer, A. and Ritchie, D. 1967
	 The complexity of LOOP programs.
	 {\it Proc.\ 22nd\ ACM\ National\ Conf.}, 465-469.
\bibitem[McNaughton, 1993]{MCN}
	 McNaughton, R. 1993
         {\it Elementary Computability, Formal Languages and Automata}.
	 ZB Publishing Industries, Lawrence, Kansas.
\bibitem[Minsky, 1967]{Minsky}
	 Minsky, M. 1967
	 {\it Computation: Finite and Infinite Machines}
	 Prentice Hall, Englewood Cliffs, NJ.
\bibitem[Post, 1943]{Post}
        Post, E. 1943. 
        Formal reductions of the general combinatorial decision problems. 
        {\it Amer. J. Math.} 65:197-215.
\bibitem[Robinson, 1991]{Rob}
        Minsky's small universal Turing machine.
        {\it International Journal of Mathematics}. 2(5):551-562.
\bibitem[Rogers, 1967]{Rogers}
	 Rogers, H. 1967
	 {\it Theory of Recursive Functions and Effective Computability}.
	 MIT Press, Cambridge, MA.
\bibitem[Sipser, 1996]{Sipser}
	 Sipser, M. 1996
	 {\it Introduction to the Theory of Computation}, First Edition, 1996.
	 PWS Publishing Company, Boston, MA.
\bibitem[Smullyan, 1978]{Sm1}
	 Smullyan, R. 1978
	 {\it What is the Name of this Book?}, Prentice-Hall, Inc., Englewood Cliffs, NJ.
\bibitem[Smullyan, 1992]{Sm2}
	Smullyan, R. 1992
	{\it Satan, Cantor and Infinity}, Alfred A. Knopf Inc., 1992.
\bibitem[Sudkamp, 1997] {sudkamp}
	 Sudkamp, T. 1997.
	 {\it Languages and Machines An Introduction to the Theory of Computer
	 Science}, Addison-Wesley Longman Inc.
\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, 1936. 
\bibitem[Wood, 1987]{wood}
        Wood, D. 1987.
        {\it Theory of Computation}. Harper and Row.
\bibitem[Wang, 1961]{Wang}
	Wang, H. 1961
	Proving theorems by pattern recognition.
	{\it Bell System Technical Journal}, 40:1-42, 1961.
\end{thebibliography}

\bigskip
{\noindent \large \bf Further Information}\\
The fundamentals of computability can be found in many books
including the classic texts~\cite{Rogers, Davis1, Minsky}.
More-recent books on automata and formal languages have also devoted at
least a few chapters to
computability~\cite{floyd,gurari,Harel,Harrison,HU79,Sipser,wood}.
Early work on computability was motivated by a quest to
address profound questions about the basis of logical reasoning, mathematical
proofs, and automatic computation. Various formalisms discussed in this
chapter were proposed at around the same time, and soon thereafter,
their equivalence was tested. Thus, in a short time, the Church-Turing
thesis took
deep roots. Subsequent work has focussed on whether certain problems are
decidable or not. 
Another direction of research has been to make finer
distinctions among unsolvable problems by introducing degrees of
unsolvability. Recursive function theory and lambda calculus also
led to the development of functional programming languages, such as
Lisp, Scheme, Haskell, and ML. Computability theory is also closely
related to logic, formal deductive systems, and complexity theory. Logic
and deductive systems are of interest to philosophers and researchers
in artificial intelligence, as well as to computation theorists.
Although there are
no journals devoted exclusively to computability, many theory journals 
(such as those listed at the end of the last two chapters) publish papers on
this topic. In addition, the journal
{\it Annals of Pure and Applied Logic\/} publishes papers on 
logic and computability. 
\end{document}



