\documentclass[11pt]{article}
\usepackage{amsmath}

\usepackage{amsthm} %\usepackage{thmdefs}
\theoremstyle{plain} %% This is the default
\newtheorem{theorem}{Theorem}[section]
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
%\newtheorem{axiom}{Axiom}[section]
%\newtheorem{remark}{Remark}[section]
%\newtheorem{example}{Example}[section]

%\theoremstyle{definition}
%\newtheorem{exercise}{Exercise}[chapter]
\numberwithin{equation}{section}

\newcommand{\al}{\alpha}
\newcommand{\be}{\beta}
\newcommand{\br}{\mathbf {R}}
\newcommand{\bn}{\mathbf {N}}
\newcommand{\om}{\omega}
\newcommand{\ot}{\otimes}
\newcommand{\ld}{\ldots}
\newcommand{\p} {\partial}
\newcommand{\g} {\mathsf g }
\newcommand{\nab}{\nabla}

\begin{document}
\title{An Introduction to Turing Machines}
\author{An Historical Project}
\date{ }
\maketitle

During the International Congress of Mathematicians in Paris in 1900
David Hilbert (1862--1943), one of the leading mathematicians of the
last century, proposed a list of problems for the following generations
to ponder.  On the list was whether the axioms of arithmetic are
consistent, a question which would have profound consequences for the
foundations of mathematics.  Continuing in this direction, in 1928
Hilbert proposed the decision problem (das 
Entscheidungsproblem), which asked whether there was a standard
procedure that can be applied to decide whether a given mathematical
statement is true.  In a revolutionary paper ``On Computable Numbers,
with an Application to the Entscheidungsproblem'' published in 1936,
Alan Turing (1912--1954) proved that the decision problem had no
solution, and in doing so he outlined the rudimentary ideas which form
the basis for the modern programmable computer.  Today his construction
is known as a Turing machine.

The goal of this project is to read a few excerpts from Turing's
original paper\footnote{Turing, A.M., ``On Computable Numbers with an
Application to the Entscheidungsproblem,'' {\em Proceedings of the
London Mathematical Society}, 42 (1936), pp. 230--265.} and outline a
machine that would verify the condition of set containment, a topic
discussed in class.  After carefully reading the attached pages,
answer the following:

\smallskip
\noindent
(a)  Describe the workings of a Turing machine (referred to as a
``computing machine'' in the original paper).

\smallskip
\noindent
(b) What is the precise output of the machine in Example 1.  Be sure
to justify your answer.

\smallskip
\noindent
(c)  Design a Turing machine which generates the following output.  Be
sure to justify your answer.
$$ 010010100101001 \ \ldots   $$

\smallskip
\noindent
(d)  Describe the behavior of the following machine, which begins with
a blank tape, with the machine in configuration $\alpha$.  

\smallskip

\begin{tabular}{|c|c|c|c|}\hline
\multicolumn{2}{|c|}{Configuration} & \multicolumn{2}{c|}{Behavior} \\ \hline
m-config. & symbol & operation & final m-config. \\ \hline
$\alpha$ & none & R P1 & $\beta$ \\
$\alpha$ & 1 & R P0 & $\beta$ \\
$\alpha$ & 0 & HALT & (none) \\
$\beta$  & 1 & R P1 & $\alpha$ \\
$\beta$  & 0 & R P0 & $\alpha$ \\ \hline
\end{tabular}

\bigskip
\noindent
(e)  Given finite, non-empty, sets $A$ and $B$, design a Turing
machine which tests whether $A \subseteq B$.  Suppose that the first
character on the tape is a 0, simply to indicate the beginning of the
tape.  To the right of 0 follow the (distinct, non-blank) elements of
$A$, listed in consecutive positions, followed by the symbol \&.  To
the right of \& follow the (distinct, non-blank) elements of $B$,
listed in consecutive positions, followed by the symbol Z to indicate
the end of the tape:

\bigskip
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|} \hline
0 & \ & \ & \ \ . . . \ \ & \ & \& & \ & \ \ . . . & \ & \ & Z \\
\hline
\end{tabular}

\bigskip
\bigskip
\noindent
The symbols 0, \&, Z are neither elements of $A$ nor $B$.  The machine
starts reading the tape in the right most position, at Z.  If $A
\subseteq B$, have the machine erase all the elements of $A$ and
return a tape with blanks for every square which originally contained
an element of $A$.  You may use the following operations for the
behavior of the machine:

\begin{itemize}
\item R:  Move one position to the right.
\item L:  Move one position to the left.
\item S:  Store the scanned character in memory.  Only one character
can be stored at a time.
\item C:  Compare the currently scanned character with the character in memory.
The only operation of C is to change the final configuration depending
on whether the scanned square matches what is in memory.
\item E:  Erase the currently scanned square
\item P(\ ):  Print whatever is in parentheses in the current square.
\end{itemize}
You may use multiple operations for the machine in response to a
given configuration.  Also, for a configuration $q_n$, you may use the
word ``other'' to denote all symbols ${\cal{S}}(r)$ not specifically
identified for the given $q_n$.  Be sure that your machine halts.

\bigskip
{\sf  \centerline{ON COMPUTABLE NUMBERS, WITH AN APPLICATION TO}
\centerline{THE ENTSCHEIDUNGSPROBLEM} 

\smallskip
\centerline{{\em By} A. M. Turing.}

\bigskip
\centerline{1. {\em Computing Machines.}}

\smallskip
We have said that the computable numbers are those whose decimals are
calculable by finite means.  This requires more explicit definition.
No real attempt will be made to justify the definitions given until we
reach \S 9.  For present I shall only say that the justification lies
in the fact that the human memory is necessarily limited.

We may compare a man in the process of computing a real number to a
machine which is only capable of a finite number of conditions $q_1$,
$q_2$, $\ldots$, $q_R$, which will be called the
``$m$-configurations''.  The machine is supplied with a ``tape'' (the
analogue of paper) running through it, and divided into sections
(called ``squares'') each capable of bearing a ``symbol''.  At any
moment there is just one square, say the $r$-th, bearing the symbol
${\cal{S}}(r)$ which is ``in the machine''.  We may call this square the
``scanned square''.  The symbol  on the scanned square may be called
the ``scanned symbol''.  The ``scanned symbol'' is the only one of
which the machine is, so to speak, ``directly aware''.  However, by
altering its $m$-configuration the machine can effectively remember
some of the symbols it has ``seen'' (scanned) previously.  The
possible behaviour of the machine at any moment is determined by the
$m$-configuration $q_n$ and the scanned symbol ${\cal{S}}(r)$.  This pair
$q_n$, ${\cal{S}}(r)$ will be called the ``configuration'';  thus the
configuration determines the possible behaviour of the machine.  In
some of the configurations in which the scanned square is blank
(i.e. bears no symbol) the machine writes down a new symbol on the
scanned square;  in other configurations it erases the scanned
symbol.  The machine may also change the square which is being
scanned, but only by shifting it one place to right or left.  In
addition to any of these operations the $m$-configuration may be
changed.  Some of the symbols written down will form the sequence of
figures which is the decimal of the real number which is being
computed.  The others are just rough notes to ``assist the memory''.
It will only be these rough notes which will be liable to erasure.

It my contention that these operations include all those which are used
in the computation of a number.  The defense of this contention will
be easier when the theory of the machines is familiar to the reader.
In the next section I therefore proceed with the development of the
theory and assume that it is understood what is meant by ``machine'',
``tape'', ``scanned'', etc.

\bigskip
\centerline{2.  {\em Definitions.}}

\smallskip
{\em Automatic machines.}

If at each stage the motion of a machine (in the sense of \S 1)is {\em
completely} determined by the configuration, we shall call the machine
an ``automatic machine'' (or $a$-machine).

For some purposes we might use machines (choice machines or
$c$-machines) whose motion is only partially determined by the
configuration (hence the use of the word ``possible'' in \S 1).  When
such a machine reaches one of these ambiguous configurations, it cannot
go on until some arbitrary choice has been made by an external
operator.  This would be the case if we were using machines to deal
with axiomatic systems.  In this paper I deal only with automatic
machines, and will therefore often omit the prefix $a$-.  

\medskip
{\em Computing machines.}

If an $a$-machine prints two kinds of symbols, of which the first kind
(called figures) consists entirely of 0 and 1 (the others being
called symbols of the second kind), then the machine will be
called a computing machine.  If the machine is supplied with a blank
tape and set in motion, starting from the correct initial
$m$-configuration the subsequence of the symbols printed by it which
are of the first kind will be called the {\em sequence computed by the
machine}.  The real number whose expression as a binary decimal is
obtained by prefacing this sequence by a decimal point is called the
{\em number printed by the machine}.

At any stage of the motion of the machine, the number of the scanned
square, the complete sequence of all symbols on the tape, and the
$m$-configuration will be said to describe the {\em complete
configuration} at that stage.  The changes of the machine and tape
between successive complete configurations will be called the {\em
moves} of the machine. 

\bigskip
\centerline{3. {\em Examples of computing machines.}}

\smallskip
I.  A machine can be constructed to compute the sequence $010101
\ldots$.  The machine is to have the four $m$-configurations ``$b$'',
``$c$'', ``$f$'', ``$e$'' and is capable of printing ``0'' and ``1''.
The behaviour of the machine is described in the following table in
which ``$R$'' means ``the machine moves so that it scans the square
immediately on the right of the one it was scanning previously''.
Similarly for ``$L$''.  ``$E$'' means ``the scanned symbol is erased
and ``$P$'' stands for ``prints''.  This table (and all succeeding
tables of the same kind) is to be understood to mean that for a
configuration described in the first two columns the operations in the
third column are carried out successively, and the machine then goes
over into the $m$-configuration described in the last column.  When
the second column is blank, it is understood that the behaviour of the
third and fourth columns applies for any symbol and for no symbol.
The machine starts in the $m$-configuration $b$ with a blank tape.
(Example 1).

\medskip
\begin{tabular}{|c|c|c|c|}\hline
\multicolumn{2}{|c|}{Configuration} & \multicolumn{2}{c|}{Behaviour} \\ \hline
m-config. & symbol & operation & final m-config. \\ \hline
$b$ & none & P0, R & $c$ \\
$c$ & none & R & $e$ \\
$e$ & none & P1, R & $f$ \\
$f$ & none & R & $b$ \\ \hline
\end{tabular}

\bigskip
If (contrary to the description \S 1) we allow the letters $L$, $R$
to appear more than once in the operations column we can simplify the
table considerably.  

\medskip
\begin{tabular}{|c|c|c|c|}\hline
\multicolumn{2}{|c|}{Configuration} & \multicolumn{2}{c|}{Behaviour} \\ \hline
m-config. & symbol & operation & final m-config. \\ \hline
$b$ & none & P0 & $b$ \\
$b$ & 0 & R, R, P1 & $b$ \\
$b$ & 1 & R, R, P0 & $b$ \\ \hline
\end{tabular}}



\end{document}