\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{Turing Machines, Induction and Recursion}
\author{An Historical Project}
\date{ }
\maketitle
The logic behind the modern programmable computer owes much to Turing's
``computing machines,'' discussed in the first project, which the
reader should review. Since the state of the machine, or
$m$-configuration as called by Turing, can be altered according to the
symbol being scanned, the operation of the machine can be changed
depending on what symbols have been written on the tape, and affords
the machine a degree of programmability. The program consists of the
list of configurations of the machine and its behavior for each
configuration. Turing's description of his machine, however, did not
include memory in its modern usage for computers, and symbols
read on the tape could not be stored in any separate devise. Using a
brilliant design feature for the tape, Turing achieves a limited type
of memory for the machine, which allows it to compute many arithmetic
operations. The numbers needed for a calculation are printed on every
other square of the tape, while the squares between these are used as
``rough notes to `assist the memory.' It will only be these rough
notes which will be liable to erasure'' [1, p. 232].
Turing continues:
{\sf{
The convention of writing the figures only on alternate squares is very
useful: I shall always make use of it. I shall call the one sequence
of alternate squares $F$-squares, and the other sequence $E$-squares.
The symbols on $E$-squares will be liable to erasure. The symbols on
$F$-squares form a continuous sequence. $\ldots$ There is no need to
have more than one $E$-square between each pair of $F$-squares: an
apparent need of more $E$-squares can be satisfied by having a
sufficiently rich variety of symbols capable of being printed on
$E$-squares}} [1, p. 235].
Let's examine the Englishman's use of these two types of squares. Determine the
output of the following Turing machine, which begins with the tape
\smallskip
\begin{tabular}{|c|c|c|c|c|c|c|} \hline
$X$ & \ & \ &$\ldots$& \ & \ & \ \\ \hline
\end{tabular}
\smallskip
\noindent
and the scanner at the far left, reading the symbol $X$.
\bigskip
\begin{tabular}{|c|c|c|c|}\hline
\multicolumn{2}{|c|}{Configuration} & \multicolumn{2}{c|}{Behavior} \\ \hline
m-config. & symbol & operation & final m-config. \\ \hline
$a$ & $X$ & R & $a$ \\
$a$ & 1 & R, R & $a$ \\
$a$ & blank & P(1), R, R, P(1), R, R, P(0)& $b$ \\ \hline
$b$ & $X$ & E, R& $c$ \\
$b$ & other & L & $b$ \\ \hline
$c$ & 0 & R, P($X$), R & $a$ \\
$c$ & 1 & R, P($X$), R & $d$ \\ \hline
$d$ & 0 & R, R & $e$ \\
$d$ & other & R, R & $d$ \\ \hline
$e$ & blank & P(1) & $b$ \\
$e$ & other & R, R & $e$ \\
\hline
\end{tabular}
\bigskip
Recall the meaning of the following symbols used for operations.
\begin{itemize}
\item R: Move one position to the right.
\item L: Move one position to the left.
\item E: Erase the currently scanned square
\item P(\ ): Print whatever is in parentheses in the current square.
\end{itemize}
\bigskip
\noindent
(a) What is the precise output of the machine as it just finishes
configuration $a$ and enters configuration $b$ for the first time?
Justify your answer.
\smallskip
\noindent
(b) What is the precise output of the machine as it just finishes
configuration $a$ and enters configuration $b$ for the second time?
Justify your answer.
\smallskip
\noindent
(c) What is the precise output of the machine as it just finishes
configuration $a$ and enters configuration $b$ for the third time?
Justify your answer.
\smallskip
\noindent
(d) Guess what the output of the machine is as it just finishes
configuration $a$ and enters configuration $b$ for the $n$-th time.
Use induction to prove that your guess is correct. Be sure to
carefully write the details of this proof by induction.
\smallskip
\noindent
(e) Design a Turing machine, which when given two arbitrary natural
numbers, $n$ and $m$, will compute the product $n \cdot m$. Suppose
that the machine begins with the tape
\smallskip
\noindent
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline
$A$& 1 & \ & 1 & \ &$\ldots$& \ & 1 & \ & 1 & $B$
& 1 & \ & 1 & \ &$\ldots$& \ & 1 & \ & 1 & $C$ \\
\hline
\end{tabular}
\smallskip
\noindent
where the number of ones between $A$ and $B$ is $n$, the number of
ones between $B$ and $C$ is $m$, and the machine begins scanning the
tape at the far left, reading the symbol $A$. The output of the
machine should be:
\smallskip
\noindent
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline
$A$& 1 &\ &$\ldots$& 1 & $B$
& 1 & \ &$\ldots$& 1 & $C$
& 1 & \ & 1 \ & \ &$\ldots$& \
& 1& $D$ \\
\hline
\end{tabular}
\smallskip
\noindent
where the number of ones between $C$ and $D$ is $n \cdot m$. Be sure
to justify your answer.
Letting $T$ denote the Turing machine which multiplies $n$ and $m$ together,
so that the value of $T(n, \, m)$ is $n \cdot m$, design $T$ so that
for $n \in \bn$,
$$ T(n, \, 1) = n $$
and for $m \in \bn$, $m \geq 2$, we have
$$ T(n, \, m) = T(n, \, m-1) + n. $$
Such an equation provides an example of a recursively defined
function, an important topic in computer science. In our case, the
algorithm for multiplication, $T$, is defined in terms of addition, a
more elementary operation.
\bigskip
\bigskip
\noindent
REFERENCES:
\medskip
\noindent
[1] Turing, A. M., ``On Computable Numbers with An Application to the
Entscheidungsproblem,'' {\em Proceedings of the London Mathematical
Society}, 42, 1936, pp. 230--265.
\end{document}