\documentclass[11pt]{article}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}
\usepackage{amsfonts}
\usepackage{epsfig}
\setlength{\topmargin}{-.55in}
\setlength{\oddsidemargin}{0in}
\setlength{\evensidemargin}{0in}
\setlength{\textwidth}{6.5in}
\setlength{\textheight}{9.1in}
\newcommand{\br}{\mathbf {R}}
\newcommand{\bq}{\mathbf {Q}}
\newcommand{\bz}{\mathbf {Z}}
\newcommand{\bn}{\mathbf {N}}
\newcommand{\z}{$\circ$}
\newcommand{\lph}{$\leftharpoondown$}
\begin{document}
\title{A Study of Logic and Programming via Turing Machines}
\author{Jerry M. Lodder\footnote{Mathematical
Sciences; Dept. 3MB, Box 30001; New Mexico State University; Las
Cruces, NM 88003; {\tt jlodder@nmsu.edu}.}}
\date{}
\maketitle
\section*{An Introduction to Turing Machines}
\medskip
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 following generations
to ponder \cite[p.\ 290--329]{JLHilbert65} \cite{JLHilbertN}. 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)
\cite{JLHilbert30, JLHilbertA1, JLHilbertA2}, which asked whether
there was a standard
procedure that can be applied to decide whether a given mathematical
statement is true. Both Alonzo Church (1903--1995) \cite{JLChurch36, JLChurch36b}
and Alan Turing (1912--1954) \cite{JLTuring36}
published papers in 1936 demonstrating that the decision
problem has no solution, although it is the algorithmic character of
Turing's paper ``On Computable Numbers,
with an Application to the Entscheidungsproblem'' \cite{JLTuring36}
that forms the basis for the modern programmable computer.
Today his construction is known as a {\em Turing machine}.
Let's first study a few excerpts from Turing's original paper
\cite[p.\ 231--234]{JLTuring36},
and then design a few machines to perform certain tasks.
{\sf
\begin{quote}
\centerline{\sc{on computable numbers, with an application to}}
\centerline{\sc{the Entscheidungsproblem}}
\medskip
\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 is 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. $\ldots$
\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
[Example 1] 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.
\medskip
\begin{center}
\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 & P(0), R & $c$ \\
$c$ & none & R & $e$ \\
$e$ & none & P(1), R & $f$ \\
$f$ & none & R & $b$ \\ \hline
\end{tabular}
\end{center}
\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{center}
\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 & P(0) & $b$ \\
$b$ & 0 & R, R, P(1) & $b$ \\
$b$ & 1 & R, R, P(0) & $b$ \\ \hline
\end{tabular}
\end{center}
\end{quote} }
\noindent
1.1. Describe the workings of a Turing machine (referred to as a
``computing machine'' in the original paper).
\smallskip
\noindent
1.2. What is the precise output of the machine in Example 1? Certain
squares may be left blank. Be sure to justify your answer.
\smallskip
\noindent
1.3. Design a Turing machine which generates the following output. Be
sure to justify your answer.
$$ 010010100101001 \ \ldots $$
\smallskip
\noindent
1.4. Describe the behavior of the following machine, which begins with
a blank tape, with the machine in configuration $\alpha$.
\medskip
\begin{center}
\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 P(1) & $\beta$ \\
$\alpha$ & 1 & R P(0) & $\beta$ \\
$\alpha$ & 0 & HALT & (none) \\
$\beta$ & 1 & R P(1) & $\alpha$ \\
$\beta$ & 0 & R P(0) & $\alpha$ \\ \hline
\end{tabular}
\end{center}
\bigskip
\noindent
1.5. 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{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|} \hline
0 & \ & \ & \ \ . . . \ \ & \ & \& & \ & \ \ . . . & \ & \ & Z \\
\hline
\end{tabular}
\end{center}
\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.
\section*{Turing Machines, Induction and Recursion}
The logic behind the modern programmable computer owes much to Turing's
``computing machines,'' discussed in the first section of the project.
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 device. 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'' \cite[p.\ 232]{JLTuring36}.
Turing continues \cite[p.\ 235]{JLTuring36}:
{\sf \begin{quote}
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.
\end{quote} }
Let's examine the Englishman's use of these two types of squares. Determine the
output of the following Turing machine, which begins in configuration
$a$ with the tape
\smallskip
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|} \hline
$X$ & \ & \ &$\ldots$& \ & \ & \ \\ \hline
\end{tabular}
\end{center}
\smallskip
\noindent
and the scanner at the far left, reading the symbol $X$.
\bigskip
\begin{center}
\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}
\end{center}
\bigskip
\noindent
2.1. 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
2.2 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
2.3. 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
2.4. 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
write carefully the details of this proof by induction.
\smallskip
\noindent
2.5. 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
\medskip
\begin{center}
\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}
\end{center}
\medskip
\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:
\medskip
\begin{center}
\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}
\end{center}
\medskip
\noindent
where the number of ones between $C$ and $D$ is $n \cdot m$. Use
induction to verify that the machine produces the correct output.
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.
\section*{The Universal Computing Machine}
The decision problem of Hilbert asked whether there
is a standard procedure, an algorithm in modern terminology, which can
be invoked to decide whether an arbitrary statement (within some
system of logic) is valid. In answering this question, Turing
introduced several fundamental concepts, certainly of
importance to logic, but also pivotal to the development of the modern
programmable computer. The first of these is a ``computing machine,''
called a ``Turing machine'' today, which is the forerunner of a
modern computer program. The next concept is the ``universal computing
machine,'' which is in fact a particular type of Turing machine that
accepts the instructions of some other machine $M$ in standard form,
and the outputs the same sequence as $M$. Turing writes
\cite[p.\ 241--242]{JLTuring36}:
{\sf
\begin{quote} It is
possible to invent a single machine which can be used to compute any
computable sequence. If this machine $U$ is supplied with a tape on
the beginning of which is written the $S.D$ [standard description] of
some computing machine $M$, then $U$ will compute the same sequence as
$M$.
\end{quote} }
The reader should review \S 3 {\em Examples of computing machines} reprinted
above under ``An Introduction to Turing Machines,'' and have the table
from Example 1 at hand before reading
the following excerpts \cite[p.\ 239--241]{JLTuring36}:
{\sf
\begin{quote}
\centerline{5. {\em Enumeration of computable sequences.}}
\smallskip
A computable sequence $\gamma$ is determined by a description of a
machine which computes $\gamma$. Thus the sequence
001011011101111... is determined by the table on p. 234, and, in fact,
any computable sequence is capable of being described in terms of such
a table.
It will be useful to put these tables into a kind of standard form.
In the first place let us suppose that the table is given in the same
form as the first table, for example, 1 on p. 233. That is to say,
that the entry in the operations column is always one of the form
$E$: $E,R$: $E,L$: $P\alpha$: $P\alpha, R$: $P \alpha , L$: $R$: $L$: or
no entry at all. The table can always be put into this form by
introducing more $m$-configurations. Now let us give numbers to the
$m$-configurations, calling them $q_1, \, \ldots, \, q_R$ as in $\S
1$. The initial $m$-configuration is always to be called $q_1$. We
also give numbers to the symbols $S_1, \, \ldots, \, S_m$ and, in
particular, ${\text{blank}} = S_0$, $0 = S_1$, $1 = S_2$. The lines of the
table are now of form
\bigskip
\begin{tabular}{ccccc}
{\em m-config.} & {\em Symbol} & {\em Operations} & {\em Final m-config.} & \\
$q_i$ & $S_j$ & $PS_k ,\, L$ & $q_m$ & $(N_1)$ \\
$q_i$ & $S_j$ & $PS_k ,\, R$ & $q_m$ & $(N_2)$ \\
$q_i$ & $S_j$ & $PS_k $ & $q_m$ & $(N_3)$ \\
\end{tabular}
\bigskip
\noindent
Lines such as
\begin{tabular}{cccl}
$\ \ \ \ \ q_i \ \ \ \ \ $ &
$\ \ \ S_j \ \ \ $ & $\ \ \ E, \, R \ \ \ $ &
$\ \ \ \ \ \ \ \ q_m $
\end{tabular}
\smallskip
\noindent
are to be written as
\begin{tabular}{cccl}
$\ \ \ \ \ q_i \ \ \ \ \ $ &
$\ \ \ S_j \ \ \ $ & $\ \ PS_0, \, R \ \ $ &
$\ \ \ \ \ \ \ q_m $
\end{tabular}
\smallskip
\noindent
and lines such as
\begin{tabular}{cccl}
$\ \ \ \ \ q_i \ \ \ \ \ $ &
$\ \ \ S_j \ \ \ $ & $\ \ \ \ \ R \ \ \ \ $ &
$\ \ \ \ \ \ \ \ \ q_m $
\end{tabular}
\smallskip
\noindent
to be written as
\begin{tabular}{cccl}
$\ \ \ \ \ q_i \ \ \ \ \ $ &
$\ \ \ S_j \ \ \ $ & $\ \ PS_j, \, R \ \ $ &
$\ \ \ \ \ \ \ q_m $
\end{tabular}
\smallskip
\noindent
In this way we reduce each line of the table to a line of one of the
forms $(N_1)$, $(N_2)$, $(N_3)$.
From each line of form $(N_1)$ let us form an expression $q_i \, S_j
\, S_k \,
L \, q_m$; from each line of form $(N_2)$ we form an expression $q_i
\, S_j \,
S_k \, R \, q_m$; and from each line of form $(N_3)$ we form an expression
$q_i \, S_j \, S_k \, N \, q_m$.
Let us write down all expressions so formed from the table for the
machine and separate them by semi-colons. In this way we obtain a
complete description of the machine. In this description we shall
replace $q_i$ by the letter ``$D$'' followed by the letter ``$A$''
repeated $i$ times, and $S_j$ by ``$D$'' followed by ``$C$'' repeated
$j$ times. This new description of the machine may be called the {\em
standard description} (S.D). It is made up entirely from the letters
``$A$'', ``$C$'', ``$D$'', ``$L$'', ``$R$'', ``$N$'', and from
``;''. ...
\smallskip
Let us find a description number for the machine I of \S 3. When
we rename the $m$-configurations its table becomes:
\bigskip
\begin{tabular}{|c|c|c|c|}\hline
m-config. & Symbol & Operations & Final m-config. \\ \hline
$q_1$ & $S_0$ & $PS_1 ,\, R$ & $q_2$ \\
$q_2$ & $S_0$ & $PS_0 ,\, R$ & $q_3$ \\
$q_3$ & $S_0$ & $PS_2 ,\, R$ & $q_4$ \\
$q_4$ & $S_0$ & $PS_0 ,\, R$ & $q_1$ \\ \hline
\end{tabular}
\bigskip
Other tables could be obtained by adding irrelevant lines such as
$$ q_1 \ \ \ \ \ S_1 \ \ \ \ \ PS_1, \, R \ \ \ \ \ q_2 $$
Our first standard form would be
$$ q_1 \, S_0 \, S_1 \, R \, q_2 ; \ q_2 \, S_0 \, S_0 \, R \, q_3 ;
\ q_3 \, S_0 \, S_2 \, R \, q_4 ; \ q_4 \, S_0 \, S_0 \, R \, q_1 ; \, . $$
The standard description is
$$ DADDCRDAA;DAADDRDAAA;DAAADDCCRDAAAA;DAAAADDRDA;$$
\end{quote} }
Continuing from \cite[p.\ 243]{JLTuring36}, we read:
{\sf
\begin{quote}
Each instruction consists of five consecutive parts
\begin{itemize}
\item[(i)] ``$D$'' followed by a sequence of letters ``$A$''. This
describes the relevant $m$-configuration.
\item[(ii)] ``$D$'' followed by a sequence of letters ``$C$''. This
describes the scanned symbol.
\item[(iii)] ``$D$'' followed by another sequence of letters ``$C$''. This
describes the symbol into which the scanned symbol is to be changed.
\item[(iv)] ``$L$'', ``$R$'', or ``$N$'', describing whether the machine is
to move to left, right, or not at all.
\item[(v)] ``$D$'' followed by a sequence of letters ``$A$''. This describes
the final $m$-configuration.
\end{itemize}
\end{quote} }
\noindent
3.1. What is the output of the following machine, $T$, if $T$ begins
in configuration $a$ with a blank tape, scanning the blank at the far
left?
\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$ & 1 & R & $c$ \\
$a$ & blank & P(1), R & $b$ \\ \hline
$b$ & 0 & R & $a$ \\
$b$ & blank & P(1) & $a$ \\ \hline
$c$ & blank & P(0) & $b$ \\
\hline
\end{tabular}
\bigskip
\noindent
3.2. Rewrite the output of machine $T$ using the ``standard
description'' for the output symbols, i.e., $S_0 =$ blank, $S_1 = 0$,
$S_2 = 1$, and then replace each $S_j$ with $D$ followed by $C$
repeated $j$ times.
\bigskip
\noindent
3.3. What is the standard description ($S.D$) of machine $T$? Be sure
that every instruction, including the last one, is followed by a semi-colon.
Make sure that you have the correct answer to this before continuing.
\bigskip
\noindent
3.4. Suppose that the number of configurations for a given machine $M$
is limited to nine, while the number of symbols which $M$ can
recognize or write is limited to four. The machine $M$ begins in its
first listed configuration ($a$) with a blank tape, reading the blank
at the far left. Now suppose that the standard description of $M$ is
written on every other square (in fact the $F$-squares) of a second
tape, with each instruction followed by a semi-colon (on an $F$-square
as well), with the last semi-colon followed by the symbol ``::'' on an
$F$-square. Initially all other squares on this second tape are
blank. If the standard description for machine I of \S 3 in Turing's
paper is entered on tape in this way, what is the output
of the following machine $U$, which begins in configuration one reading
the tape at the far left? Note that 20R is shorthand for move 20
squares to the right, and similarly for 10R. How does this compare
with the actual output of machine I, \S 3?
\bigskip
\noindent
3.5. If the standard description of machine $T$ from question 3.1 is
written on tape as described in 3.4, what is the output of $U$ when
applied to this tape? How does this compare to the actual output of
$T$?
\bigskip
\noindent
3.6. Describe in words the operation of configuration one from machine
$U$. Describe separately the operations of configurations two, three,
and four.
\bigskip
\noindent
3.7. Note that only the first 16 configurations of $U$ are listed.
From this point, if $U$ was originally supplied with the standard
description of a machine $M$ (as specified in 3.4), then $U$ should
output the same sequence as $M$, except coded according to the
standard description of the output symbols. Moreover, $U$ keeps track
of the current configuration of $M$ in the first 18 squares
immediately following ``::''. The position of the scanner for $M$ is
recorded via the symbol ``T'' on the tape which $U$ processes. Beginning
with configuration 17, outline the remaining operations
of $U$. You may use phrases such as ``match m-configuration,''
``match scanned symbol,'' or `` move scanner for $M$,'' etc. Be sure
to include a written explanation of these and any other operations you
decide to use in your outline. For this part, you do not need to
design an actual Turing machine to perform these tasks. Does
recursion occur in your outline? How?
\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
1 & D & R & 1 \\
1 & A & R & 2 \\
1 & :: & none & none \\
1 & other & R & 1 \\ \hline
2 & blank & R & 2 \\
2 & A & R & 4 \\
2 & D & R, R & 3 \\ \hline
3 & D & R, P(X) & 5 \\
3 & C & R & 4 \\ \hline
4 & ; & R & 1 \\
4 & :: & none & none \\
4 & other & R & 4 \\ \hline
5 & :: & 20R, P(Y), R, R, P(D), 10R, P(Z) & 6 \\
5 & other & R & 5 \\ \hline
6 & X & E, R & 7 \\
6 & other & L & 6 \\ \hline
7 & C & R, P(X) & 8 \\
7 & R & R, P(X) & 10\\
7 & L & none & none \\
7 & N & R, P(X) & 11\\ \hline
8 & Y & 4R & 9 \\
8 & other & R & 8 \\ \hline
9 & blank & P(C) & 6 \\
9 & C & R, R & 9 \\ \hline
10 & Z & E, P(T) & 12 \\
10 & other & R & 10 \\ \hline
11 & Y & R, P(T) & 12 \\
11 & other & R & 11 \\ \hline
12 & X & E, 4R, P(X) & 13 \\
12 & other & L & 12 \\ \hline
13 & :: & R, R & 14 \\
13 & other & R & 13 \\ \hline
14 & blank & P(A) & 15 \\
14 & Y & none & none \\
14 & other & R, R & 14 \\ \hline
15 & X & E, R & 16 \\
15 & other & L & 15 \\ \hline
16 & ; & none & 17 \\
16 & A & R, P(X) & 13 \\
\hline
\end{tabular}
\bigskip
\noindent
3.8. Beginning with configuration 17, find the actual machine
instructions of $U$ so
that $U$ finds a match between an arbitrary configuration stored on
the 18 squares to the right of ``::'' and a configuration at the
beginning of a coded instruction to the left of ``::''. Suppose that
the standard description entered on tape is that of a machine $M$ for
which there is always a well-defined configuration to follow every
move of $M$. Use only the operations
``R,'' ``L,'' ``E,'' ``P( ),'' ``none,''
and be sure to explain the new steps of $U$. What is the
present-day terminology used to describe $U$?
\bigskip
\noindent
Extra Credit: Write a computer program for a universal computing
machine (in the language of your choice). Demonstrate with several
examples that your universal machine functions properly.
\section*{The Decision Problem, {\em Das Entscheidungsproblem}}
Turing's paper ``On Computable Numbers with an Application
to the Entscheidungsproblem'' proved most influential not
only for mathematical logic, but also for the development of the
programmable computer, and together with work of Alonzo Church
(1903--1995) \cite{JLChurch36, JLChurch36b} and others
\cite{JLGrattan-Guiness}, inaugurated a new field of
study known today as computability.
Recall that Turing's original motivation for
writing the paper was to answer the decision problem of David Hilbert,
posed in 1928 along with a list of other problems
\cite{JLHilbert30, JLHilbertA1}
dealing with the consistency, completeness and independence of the
axioms of a logical system in general.
The solutions to these problems, in particular Kurt G\"odel's
(1906--1978) demonstration of the incompleteness
of arithmetic with the existence of statements that are not provable
(as true or false) \cite{JLGodel31}, had profound consequences for
mathematics, and brought mathematical logic
to the fore as a separate field of study \cite{JLGrattan-Guiness}.
In this section, however, we deal primarily with the problem of
deciding whether a given statement is valid within a logical system,
the decision problem, which Hilbert expressed as
\cite[p.\ 112--113]{JLHilbertA2}:
{\sf
\begin{quote}
$\ldots$ [T]here emerges the fundamental importance of determining whether
or not a given formula of the predicate calculus is universally
valid. $\ldots \ $ A formula $\ldots$ is called {\em satisfiable} if the
sentential variables can be replaced with the values truth and
falsehood $\ldots$ in such a way that the formula [becomes] a true
sentence. $\ldots \ $ It is customary to refer to the equivalent problems
of {\em universal validity} and {\em satisfiability} by the common
name of the {\em decision problem}.
\end{quote} }
Following G\"odel's results, the decision problem remained, although
it must be reinterpreted as meaning whether there is a procedure
by which a given proposition can be determined to be
either ``provable'' or ``unprovable''. In the text {\em Introduction
to Mathematical Logic} \cite[p.\ 99]{JLChurch96},
Church formulated this problem as:
{\sf
\begin{quote}
{\em The decision problem} of a logistic system is the problem to
find an effective procedure or algorithm, a {\em decision procedure},
by which for an arbitrary well-formed formula of the system, it is
possible to determine whether or not it is a theorem $\ldots$ .
\end{quote} }
\noindent
To be sure, Church proves that the decision problem has no solution
\cite{JLChurch36, JLChurch36b}, although it is the algorithmic character
of Turing's solution that is pivotal to the logical underpinnings of the
programmable computer. Moreover, the simplicity of a Turing machine
provides a degree of accessibility to logic and computability ideal
for readers new to this material.
The concept of a universal computing machine, studied above, has
evolved into what now
is known as a compiler or interpreter in computer science, and is
indispensable for the processing of any programming language. The
question then arises, does the universal computing machine provide a
solution to the decision problem? The universal machine is the
standard procedure for answering all questions that can in turn be
phrased in terms of a computer program.
First, study the following excerpts from Turing's paper
\cite[p.\ 232--233]{JLTuring36}:
{\sf
\begin{quote}
\centerline{\em Automatic machines.}
\smallskip
If at each stage the motion of a machine is {\em completely}
determined by the configuration, we shall call the machine an
``automatic machine'' (or $a$-machine). $\ldots$
\medskip
\centerline{\em Computing machines.}
\smallskip
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 symbols printed by it which are of the first kind
will called the {\em sequence computed by the machine}. $\ldots$
\medskip
\centerline{\em Circular and circle-free machines.}
\smallskip
If a computing machine never writes down more than a finite number of
symbols of the first kind, it will be called {\em circular}.
Otherwise it is said to be {\em circle-free}. $\ldots$
A machine will be circular if it reaches a configuration from which
there is no possible move, or if it goes on moving and possibly
printing symbols of the second kind, but cannot print any more
symbols of the first kind.
\medskip
\centerline{\em Computable sequences and numbers.}
\smallskip
A sequence is said to be computable if it can be computed by a
circle-free machine. A number is computable if it differs by an
integer from the number computed by a circle-free machine. $\ldots$
\end{quote} }
\noindent
4.1. Consider the following machine, $T_1$, which begins in
$m$-configuration $a$ with a blank tape, reading the blank at the far
left. Is $T_1$ circle-free? Justify your answer.
\medskip
$T_1: \ $\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$ & blank & $R, \ P(1)$ & $b$ \\
$a$ & $0$ & $R$ & $b$ \\ \hline
$b$ & $1$ & $R, \ R, \ P(0)$ & $a$ \\
$b$ & blank & (none) & $a$ \\ \hline
\end{tabular}
\bigskip
\noindent
4.2. Consider the following machine, $T_2$, which begins in
$m$-configuration $a$ with a blank tape, reading the blank at the far
left. Is $T_2$ circle-free? Justify your answer.
\medskip
$T_2: \ $\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$ & blank & $R, \ P(1)$ & $b$ \\
$a$ & $0$ & $R$ & $b$ \\ \hline
$b$ & $1$ & $R, \ R, \ P(0)$ & $a$ \\
$b$ & $0$ & $R$ & $a$ \\ \hline
\end{tabular}
\bigskip
\noindent
4.3. Describe in your own words the key feature which distinguishes a
circle-free machine from a circular machine.
\medskip
\noindent
4.4. Is the sequence $101001000100001 \, \ldots$ computable? If so,
find a circle-free machine (with a finite number of
$m$-configurations) that computes this sequence on every other
square (the $F$-squares) of a tape which is originally blank. If not,
prove that there is no circle-free machine that computes the above
sequence.
\medskip
Turing's insight into the decision problem begins by listing all
computable sequences in some order:
$$ \phi_1, \ \phi_2, \ \phi_3, \ \ldots , \ \phi_n, \ \ldots , $$
where $\phi_n$ is the $n$-th computable sequence. Moreover, let
$\phi_n(k)$ denote the $k$-th figure (0 or 1) of $\phi_n$. For
example, if
$$ \phi_2 = 101010 \, \ldots , $$
then $\phi_2(1) = 1$, $\phi_2(2)=0$, $\phi_2(3)=1$, etc. Turing then
considers the sequence $\beta'$ defined by $\beta'(n) = \phi_n(n)$.
If the decision problem has a solution, then \cite[p.\ 247]{JLTuring36}:
{\sf
\begin{quote} We can invent a machine $D$ which, when supplied with the $S.D$
[standard description] of any computing machine $M$ will test this
$S.D$ and if $M$ is circular will mark the $S.D$ with the symbol ``u''
[unsatisfactory] and if it is circle-free will mark it with ``s''
[satisfactory]. By combining the machines $D$ and $U$ [the universal
computing machine] we could construct a machine $H$ to compute the
sequence $\beta'$.
\end{quote} }
\noindent
4.5. Is the number of computable sequences finite or infinite?
If finite, list the computable sequences. If infinite, find a
one-to-one correspondence between the natural numbers, $\bn$, and a
subset of the computable sequences.
Use the result of this question to carefully explain why
$H$ must be circle-free.
\medskip
\noindent
4.6. Since $H$ is circle-free, the sequence computed by $H$ must be
listed among the $\phi_n$'s. Suppose this occurs for $n=N_0$. In a
written paragraph, explain how $\beta'(N_0)$ should be computed. Is
it possible to construct a machine $H$ that computes $\beta'$? If so,
find the configuration table for $H$. If not, what part of $H$, i.e.,
$D$ or $U$, cannot be constructed? Justify your answer.
\medskip
\noindent
4.7. Does the universal computing machine solve the decision problem?
Explain.
\medskip
\noindent
4.8. By what name is the decision problem known today in computer
science? Support your answer with excerpts from outside sources.
\section*{Notes to the Instructor}
The project contains four sub-projects ``An Introduction to Turing
Machines,'' ``Turing Machines, Induction and Recursion,'' ``The
Universal Computing Machine,'' and ``The Decision Problem,'' with the
first two of these ideal for an introductory undergraduate course in
discrete mathematics or computer programming. The first could be
assigned as a separate two-week project while covering naive set
theory, while the second could be assigned while the class studies
inductive or recursive constructions. A variant of this second
sub-project used recently in a beginning programming course requires
the construction of a Turing machine to compute the sum of two
positive binary integers. This version of the project, ``Turing
Machines and Binary Addition,'' is available from the web resource
\cite{JLBLLPR}.
The latter two sub-projects, which sketch the main results of Turing's
paper, are well suited for an advanced or
intermediate course in discrete mathematics, logic, or programming.
The universal machine is a Turing machine that accepts as its input
any other machine, $T$, and computes the same output as $T$. This
foreshadows the development of a compiler or interpreter in computer
science. The decision problem asks whether there is a decision
procedure that can be applied to any well-formulated mathematical
statement and determine whether the statement is true or false.
Turing's negative solution to this problem forms the historical legacy
of his paper, not to mention the notion of ``Turing computable'' to
refer to that which can be computed via a Turing machine.
\begin{thebibliography}{99}
\bibitem{JLBLLPR} Bezhanishvili, G., Leung, H., Lodder, J., Pengelley,
D., Ranjan, D., ``Teaching Discrete Mathematics via Primary Historical
Sources,''
{\tt{math-old.nmsu.edu/hist{\_}projects/}}
\bibitem{JLChurch36} Church, A.,
``An Unsolvable Problem of Elementary Number Theory,''
{\em Amer. Journal Math.}, {\bf{58}} (1936), 345--363.
This paper with a short foreword by Davis was reprinted on
pages 88--107 of \cite{JLDavis65}.
\bibitem{JLChurch36b} Church, A., ``A Note on the
Entscheidungsproblem,'' {\em Journal of Symbolic Logic},
{\bf{1}} (1936), 40--41.
\bibitem{JLChurch96} Church, A., {\em Introduction to Mathematical Logic},
Princeton University Press, Princeton, New Jersey, 1996.
\bibitem{JLDavis65} Davis, M.,
{\em The Undecidable. Basic Papers on Undecidable Propositions,
Unsolvable Problems and Computable Functions}, Martin Davis (editor),
Raven Press, Hewlett, N.Y., 1965.
\bibitem{JLGodel31} G\"{o}del, K.,
``\"{U}ber Formal Unentscheidbare {S}\"{a}tze der {P}rincipia
{M}athematica und Verwandter {S}ysteme {I},'' {\em Monatsh. Math. Phys.},
{\bf{38}} (1931), 173--198.
The English translation of this paper by Mendelson with foreword
by Davis was reprinted on pages 4--38 of \cite{JLDavis65}.
\bibitem{JLGrattan-Guiness} Grattan-Guiness, I., {\em The Search for Mathematical
Roots, 1870--1940: Logics, Set Theories and the Foundations of
Mathematics from Cantor through Russell to G\"odel}, Princeton
University Press, Princeton, New Jersey, 2000.
\bibitem{JLHilbert65} Hilbert, D., {\em Gesammelte Abhandlungen}, Vol. III,
Chelsea Publishing Co., New York, 1965.
\bibitem{JLHilbertN} Hilbert, D., ``Mathematical Problems,'' Newson M.,
(translator) {\em Bulletin of the American Mathematical Society},
{\bf{8}} (1902), 437--439.
\bibitem{JLHilbert30} Hilbert, D., ``Probleme der Grundlegung der Mathematik,''
{\em Mathematische Annalen}, {\bf{102}}, (1930), 1--9.
\bibitem{JLHilbertA1} Hilbert, D., Ackermann, W., {\em Grundz\"uge der
Theoretischen Logik}, Dover Publications, New York, 1946.
\bibitem{JLHilbertA2} Hilbert, D., Ackermann, W., {\em Principles of
Mathematical Logic}, L. Hammond, G. Leckie, F. Steinhardt,
translators, Chelsea Publishing Co., New York, 1950.
\bibitem{JLTuring36} Turing, A. M., ``On Computable Numbers with an Application
to the Entscheidungsproblem,'' {\em Proceedings of the London
Mathematical Society} {\bf{42}} (1936), 230--265.
A correction, {\bf{43}} (1937), 544--546.
This paper with a short foreword by Davis
was reprinted on pages 115--154 of \cite{JLDavis65}.
\end{thebibliography}
\end{document}
\end