\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 and Binary Addition}
\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 that computes the sum of two positive
integers in base two. First consider the examples of binary addition
afforded by
$$ 111 + 101 \ \ \ {\text{and}} \ \ \ 110 + 101 \, . $$
Explain how each of these sums is computed by hand, without the use of
a Turing machine. Pay careful attention to the operation of carrying.
Now consider positive integers $A$ and $B$ written in base 2 with
digits
\begin{align*}
& A = a_n \, a_{n-1} \, a_{n-2} \, \ldots \, a_2 \, a_1 \, a_0 \\
& B = b_n \,\, b_{n-1} \,\, b_{n-2} \, \ldots \, b_2 \,\, b_1 \,\, b_0 \, .
\end{align*}
Each $a_i \in \{ 0, \ 1 \}$, each $b_i \in \{ 0, \ 1 \}$, and the
subscript $n$ is the same for both $A$ and $B$. Suppose that *
appears on a tape followed by the $a_i$'s on every other square,
followed by \&, followed by the $b_i$'s on every other square, and
terminated by \#, as follows:
\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_n$ & \ & $\ldots$& \ & $a_1$ & \ & $a_0$ & \ & \&
& \ & $b_n$ & \ & $\ldots$&\ & $b_1$ & \ & $b_0$ & \ & \# \\
\hline
\end{tabular}
\smallskip
\noindent
Design a Turing machine $T$ that computes $A+B$ in base 2. Suppose
that $T$ begins reading the above tape at the far right, scanning the
symbol \# . Let $d_{n+1}$, $d_n$, $\ldots$, $d_1$, $d_0$ be the
digits of $A+B$. The machine should place the $d_i$'s to the left of
* with final output
\smallskip
\noindent
\hfill \begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline
\% & \ & $d_{n+1}$& \ & $d_n$ &\ & \ldots &\ & $d_2$
& \ & $d_1$ &\ & $d_0$ &\ \\
\hline
\end{tabular}
\smallskip
\noindent
\hfill \begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline
* & \ & $a_n$ & $\ldots$& \ & $a_1$ & \ & $a_0$ & \ & \&
& \ & $b_n$ & \ & $\ldots$&\ & $b_1$ & \ & $b_0$ & \ & \# \\
\hline
\end{tabular}.
\smallskip
\noindent
Before writing $T$, you may wish to consider the branching in logic
necessary to account for the cases $a_i = 0, \, 1$, $b_i = 0, \, 1$, and
whether there is a carried digit. Such branching can even be
represented schematically by a binary tree. To realize the effect of
a carried digit, one method ``to remember'' that a 1 needs to be
carried after adding $a_i$ and $b_i$ is to print a ``C'' immediately
to the left of $a_i$, or immediately to the left of $d_i$. To
indicate that a 1 need not be carried, print ``N'' instead. Finally,
design machine configurations with a specific purpose such as printing
1 in the space of $d_i$ or printing 0 there. Numbering configurations
may also be more efficient than lettering them. Briefly, state how
the procedure for computing $A+B$ is recursive.
\smallskip
\noindent
Extra Credit: Explain what difficulties are encountered when
designing a Turing machine to perform the addition $A+B$ in base 10.
\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}