« ブログテンプレート変更 | トップページ | 「门内有径」の意味 »

Errata and Typographical Remarks on Alan Turing's "On Computable Numbers, with an Application to the Entscheidungsproblem"

INTRODUCTION

I'm writing this article to provide you a list of typos found in Alan Turing's [main paper 1937](1) as well as a few typographical remarks. Punctuative and other trivial errors are excluded from the list. (e.g., “If there is no \alpha\rightarrow\mathfrak{B}.” should read “If there is no \alpha$, $\rightarrow\mathfrak{B}.” in the first right column on p.237.) None of his own peculiar wording, some of which appear to me too informal, are taken in either. (e.g., on p.237, he wrote “= \mathfrak{q}, say” where I would write “=, say, \mathfrak{q}”, and “the first symbol marked \alpha”, “the first symbol marked with \alpha”.)

The first half of the paper shows tables describing how the machine (the Turing Machine, which has a format superficially different from the current versions) computes. Unfortunately, there are no captions nor sections in those tables. With different numbers of lines in columns from table to table, the line number can't be effectively used to locate a letter/word on a page. Therefore, I will quote a piece of text including a concerned point for an enough length when I think it helps you to find quickly where the issue is.

Notes on the mathematical font: The fraktur font used here is a little different from the one seen in the [main paper 1937]. Though, they are so similar as to cause no difficulties, I believe. As for the script font, contrarily, the discrepancy is so great that I wish you cautious not to be misled by the different appearances of the typefaces.

LIST

page 238, rows 6-7 of the table It reads as follows:

\begin{tabular}{lll}
$\mathfrak{cr}(\mathfrak{C},\mathfrak{B},\alpha)\quad$ & $\quad\mathfrak{c}\Big(\mathfrak{re}(\mathfrak{C},\mathfrak{B},\alpha,a),\mathfrak{B},\alpha\Big)\qquad$  &\multirow{2}{2cm}{\rightcolumnnote{43mm}{\vspace{1mm}\quad$\mathfrak{cr}(\mathfrak{B},\alpha)$ differs from $\mathfrak{ce}(\mathfrak{B},\alpha)$ only in that the letters $\alpha$ are not erased.  The $m$-configuration $\mathfrak{cr}(\mathfrak{B},\alpha)$ is taken up when no letters “$a$” are on the tape.}}\\
$\ \mathfrak{cr}(\mathfrak{B},\alpha)$ & $\mathfrak{cr}\Big(\mathfrak{cr}(\mathfrak{B},\alpha), \mathfrak{re}(\mathfrak{B},a,\alpha),\alpha\Big)$ & \end{tabular}
However no typos are seen here, it may puzzle you until you realize that there are two different letters \alpha and a, which look quite alike in the original copy of the [main paper 1937]. Worse, using the Latin letter a deviates from Turing's own general convention of using a small Greek letter for a symbol (cf. p.236, l.1). The table should be rewritten by replacing a with a small Greek letter, say \beta, as follows:

\begin{tabular}{lll}
$\mathfrak{cr}(\mathfrak{C},\mathfrak{B},\alpha)\quad$ & $\quad\mathfrak{c}\Big(\mathfrak{re}(\mathfrak{C},\mathfrak{B},\alpha,\beta),\mathfrak{B},\alpha\Big)\qquad$  &\multirow{2}{35mm}{\rightcolumnnote{43mm}{\vspace{1mm}\quad$\mathfrak{cr}(\mathfrak{B},\alpha)$ differs from $\mathfrak{ce}(\mathfrak{B},\alpha)$ only in that the letters $\alpha$ are not erased.  The $m$-configuration $\mathfrak{cr}(\mathfrak{B},\alpha)$ is taken up when no letters “$\beta$” are on the tape.}}\\
$\ \mathfrak{cr}(\mathfrak{B},\alpha)$ & $\mathfrak{cr}\Big(\mathfrak{cr}(\mathfrak{B},\alpha), \mathfrak{re}(\mathfrak{B},\beta,\alpha),\alpha\Big)$ & \\
\end{tabular}

page 238, row 8 of the table: The row

\begin{tabular}{ll}
 $\hspace{5mm}\mathfrak{cp}(\mathfrak{C},\mathfrak{A},\mathfrak{E},\alpha,\beta)\qquad$ &$\mathfrak{f}^{\prime}\left(\mathfrak{cp}_{1}(\mathfrak{C}_{1}\mathfrak{A},\beta),\mathfrak{f}(\mathfrak{A},\mathfrak{E},\beta),\alpha\right)$
\end{tabular}
should read

\begin{tabular}{ll}
 $\hspace{5mm}\mathfrak{cp}(\mathfrak{C},\mathfrak{A},\mathfrak{E},\alpha,\beta)\qquad$ &$\mathfrak{f}^{\prime}\left(\mathfrak{cp}_{1}(\mathfrak{C},\mathfrak{A},\beta),\mathfrak{f}(\mathfrak{A},\mathfrak{E},\beta),\alpha\right).$
\end{tabular}
.
Here, the subscript “1” after \mathfrak{C} in (\mathfrak{C}_{1}\mathfrak{A},\beta) is an error for a comma “,”.

page 239, rows 1-7 of the table: Two m-functions \mathfrak{q}(\mathfrak{C}) and \mathfrak{q}(\mathfrak{C},\alpha) are defined as follows:

\begin{tabular}{ll}
$
\mathfrak{q}(\mathfrak{C}) \qquad\ 
<br /><br />\begin{cases}
 \text{Any}\  \qquad R \quad & \quad\mathfrak{q}(\mathfrak{C})\\
 \text{None} \qquad R \quad & \quad\mathfrak{q}_{1}(\mathfrak{C})
\end{cases}
\qquad$
 & \hspace{5mm}\rightcolumnnote{40mm}{\vspace{2mm}\quad$\mathfrak{q}(\mathfrak{C},\alpha)$. \quad The machine finds the last symbol of form $\alpha. \quad \rightarrow\mathfrak{C}.$}
\\
\end{tabular}

\begin{tabular}{ll}
$
\mathfrak{q}_{1}(\mathfrak{C}) \qquad
\begin{cases}
 \text{Any}  \qquad\ R \quad & \quad\mathfrak{q}(\mathfrak{C})\\
 \text{None} \qquad \phantom{R} \quad & \quad\mathfrak{C}
\end{cases}
$
 &\\
\end{tabular}

\begin{tabular}{ll}
$\mathfrak{q}(\mathfrak{C},\alpha) \phantom{\text{Any}  R \qquad \quad \mathfrak{q}(\mathfrak{C})}$
 &$\quad\mathfrak{q}\left(\mathfrak{q}_{1}(\mathfrak{C},\alpha)\right)$\\
\end{tabular}

\begin{tabular}{ll}
$
\mathfrak{q}_{1}(\mathfrak{C},\alpha) \quad
<br /><br />\begin{cases}
 \quad\alpha  \phantom{L} \quad & \quad\mathfrak{C}\\
 \text{not}\ \alpha \qquad L \quad & \mathfrak{q}_{1}(\mathfrak{C},\alpha)
\end{cases}
$
 &\\
\end{tabular}
Notwithstanding, neither appears again in the paper. Instead, an m-function \mathfrak{g}(\mathfrak{C},\alpha) is used where \mathfrak{q}(\mathfrak{C},\alpha) should be. We must amend the original text to adopt only one of the two. Hence, I discard \mathfrak{g} with \mathfrak{q} left in, and proceed with my work.

page 244, the table and the note for the m-function \mathfrak{con}(\mathfrak{C,\alpha}): It reads:

\begin{tabular}{lll}
$\mathfrak{con}(\mathfrak{C},\alpha)$&
$
\begin{cases}
 \text{Not}\ A  \quad R,R & \mathfrak{con}(\mathfrak{C},\alpha)\\
 \quad A \quad L,P\alpha,R & \mathfrak{con}_{1}(\mathfrak{C},\alpha)
\end{cases}
$
 &\multirow{2}{3.5cm}{\rightcolumnnote{45mm}{\vspace{-2mm}\quad $\mathfrak{con}(\mathfrak{C},\alpha)$. Starting from an $F$-square, $S$ say, the sequence $C$ of symbols describing a configuration closest on the right of $S$ is marked out with letters $\alpha$. \qquad $\rightarrow{\mathfrak{C}}.$}}
\\
\vspace{-12mm}
$
\mathfrak{con}_{1}(\mathfrak{C},\alpha) $&$
\begin{cases}
 \quad A \quad R,P\alpha,R & \mathfrak{con}_{1}(\mathfrak{C},\alpha)\\
 \quad D \quad R,P\alpha,R & \mathfrak{con}_{2}(\mathfrak{C},\alpha)
\end{cases}
$\\
&&\\

$
\mathfrak{con}_{2}(\mathfrak{C},\alpha) $&$
\begin{cases}
 \quad C \quad R,P\alpha,R & \mathfrak{con}_{2}(\mathfrak{C},\alpha)\\
 \text{Not}\ C \quad R,R & \mathfrak{C}
\end{cases}
$&\rightcolumnnote{45mm}{\vspace{13mm}\quad $\mathfrak{con}(\mathfrak{C},\ )$. In the final configuration the machine is scanning the square which is four squares to the right of the last square of $C$.  $C$ is left unmarked.}
\\
\end{tabular}
In the second column of the table, the letter C refers to a single symbol in the standard description (S.D[.]) of a Turing machine for a specific computation (cf. p.240), while in the right column the letter C represents a sequence of symbols that makes up a configuration of the machine (cf. p.231). To avoid ambiguity, the right column should be rewritten to get rid of the letter C, though I'm afraid I must decline to write out the details.

page 244, the table and the note for the m-configuration \mathfrak{anf}: It reads as follows:

\begin{tabular}{lll}
$\mathfrak{anf}\hspace{25mm}$ &$\mathfrak{g}(\mathfrak{anf}_{1},:)$ &\hspace{5mm}\multirow{2}{3.5cm}{\rightcolumnnote{45mm}{\vspace{1mm}\quad $\mathfrak{anf}$. \quad The machine marks the configuration in the last complete configuration with $y$.\quad $\rightarrow{\mathfrak{kom}}$.}}
\\
$\mathfrak{anf}_{1}\hspace{10mm}$ &$\mathfrak{con}(\mathfrak{kom},y)$&
\\
\end{tabular}
Here \mathfrak{g}(\mathfrak{anf}_{1},:) should read as \mathfrak{q}(\mathfrak{anf}_{1},:).

page 244, the table and the note for the m-configuration \mathfrak{kmp}: It reads as follows:

\begin{tabular}{ll}
$
\mathfrak{kmp} \qquad\ \mathfrak{cpe}\left(\mathfrak{e}(\mathfrak{kom},x,y),\mathfrak{sim},x,y\right)$
 & \hspace{5mm}\rightcolumnnote{43mm}{\vspace{15mm}\quad$\mathfrak{kmp}$. \quad The machine compares the sequences marked $x$ and $y$. It erases all letters $x$ and $y$. \quad $\rightarrow\mathfrak{sim}$ if they are alike.  Otherwise $\rightarrow\mathfrak{kom}.$}
\\
\end{tabular}
In the first, the m-function \mathfrak{e}(\mathfrak{B},\alpha,\beta) is not defined in the paper, and should be given as \mathfrak{e}(\mathfrak{e}(\mathfrak{B},\beta),\alpha) (The definition of \mathfrak{e}(\mathfrak{B},\alpha) is seen on p.237).

Secondly, until the \mathfrak{kmp} process reaches \mathfrak{sim}, it should not end in \mathfrak{kom}, but in \mathfrak{anf}. The interested subroutine repeats a searching loop from \mathfrak{anf} to \mathfrak{kmp} to find a configuration in the S.D. that coincides with the last configuration in the complete configuration under construction. Therefore, \mathfrak{kmp}, which seems to stand for a German word “\mathfrak{Komparation}” (“comparison” in English), goes back to \mathfrak{anf} (“\mathfrak{Anfang}”, “start”) to start another search routine when the comparison shows a disparity. Therefore, the table and its note should be corrected to:

\begin{tabular}{ll}
$
\mathfrak{kmp} \qquad\ \mathfrak{cpe}\left(\mathfrak{e}(\mathfrak{anf},x,y),\mathfrak{sim},x,y\right)$
 & \rightcolumnnote{43mm}{\vspace{17mm}\quad$\mathfrak{kmp}$. \quad The machine compares the sequences marked $x$ and $y$. It erases all letters $x$ and $y$. \quad $\rightarrow\mathfrak{sim}$ if they are alike.  Otherwise $\rightarrow\mathfrak{anf}.$}
\\
\end{tabular}

pages 245-246: There are a few typos:

  • The table for \mathfrak{sim}_{2} (p.245)
    
\begin{tabular}{l}
 $\mathfrak{sim}_{2}
\begin{cases}
 \quad A & \mathfrak{sim}_{3}\\
 \text{not}\ A \qquad R,Pu,R,R,R \quad & \mathfrak{sim}_{2}
\end{cases}$
\end{tabular}
    should read
    
\begin{tabular}{l}
 $\mathfrak{sim}_{2}
<br /><br />\begin{cases}
 \quad A & \mathfrak{sim}_{3}\\
 \text{not}\ A \qquad L,Pu,R,R,R \quad & \mathfrak{sim}_{2}
\end{cases}$
\end{tabular}.
.
  • The table for \mathfrak{mk} (p.245)
    
\begin{tabular}{ll}
 $\quad\mathfrak{mk}$& $\hspace{30mm}\mathfrak{g}(\mathfrak{mk},:)$\\
\end{tabular}
    should read

    
\begin{tabular}{ll}
 $\quad\mathfrak{mk}$& $\hspace{30mm}\mathfrak{q}(\mathfrak{mk}_{1},:)$\\
\end{tabular}.
.
  • The table for \mathfrak{sh}_{2} (p.245)
    
\begin{tabular}{l}
 $\mathfrak{sh}_{2}
<br /><br />\begin{cases}
 \quad D \qquad R,R,R,R \qquad & \mathfrak{sh}_{2}\\
 \text{not}\ D & \mathfrak{inst}
\end{cases}$
\end{tabular}
    should read
    
\begin{tabular}{l}
 $\mathfrak{sh}_{2}
<br /><br />\begin{cases}
 \quad D \qquad R,R,R,R \qquad & \mathfrak{sh}_{3}\\
 \text{not}\ D & \mathfrak{inst}
\end{cases}$
\end{tabular}.
.
  • The table for \mathfrak{inst} (p.246)
    
\begin{tabular}{ll}
 $\quad\mathfrak{inst}$& $\hspace{30mm}\mathfrak{g}\left(\mathfrak{l}(\mathfrak{inst}_{1}),u\right)$\\
\end{tabular}
    should read
    
\begin{tabular}{ll}
 $\quad\mathfrak{inst}$& $\hspace{30mm}\mathfrak{q}\left(\mathfrak{l}(\mathfrak{inst}_{1}),u\right)$\\
\end{tabular}.
.

page 246: The m-function \mathfrak{inst}_{1}(\alpha) is defined as follows:

\begin{tabular}{ll}
 $\mathfrak{inst}_{1}(L)$& $\hspace{15mm}\mathfrak{ce}_{5}(\mathfrak{ov},v,y,x,u,w)$\\
 $\mathfrak{inst}_{1}(R)$& $\hspace{15mm}\mathfrak{ce}_{5}(\mathfrak{ov},v,x,u,y,w)$\\
 $\mathfrak{inst}_{1}(N)$& $\hspace{15mm}\mathfrak{ce}_{5}(\mathfrak{ov},v,x,y,u,w),$\\
\end{tabular}
The m-function \mathfrak{ce}_{5} has not been defined explicitly in the paper, while the definitions of \mathfrak{ce}_{2} and \mathfrak{ce}_{3} are seen on p.239. Naturally, \mathfrak{ce}_{4} and \mathfrak{ce}_{5} should be defined as follows:

\begin{tabular}{ll}
$\mathfrak{ce}_{4}(\mathfrak{B},\alpha,\beta,\gamma,\delta)$ & $\hspace{15mm}\mathfrak{ce}\left(\mathfrak{ce}_{3}(\mathfrak{B},\beta,\gamma,\delta),\alpha\right)$\\
$\mathfrak{ce}_{5}(\mathfrak{B},\alpha,\beta,\gamma,\delta,\epsilon)$ & $\hspace{15mm}\mathfrak{ce}\left(\mathfrak{ce}_{4}(\mathfrak{B},\beta,\gamma,\delta,\epsilon),\alpha\right)$\\
\end{tabular}.
.

page 247, the 4th line from the bottom:H” should read “\mathscr{H}”.

page 252, line 20: The formula

\begin{tabular}{l}
 $(\exists{u})N(u) \mathand (x)\Big(N(x)\rightarrow{}(\exists{y})F(x,y)\Big) \mathand \Big(F(x,y)\rightarrow{N(y)}\Big)$
\end{tabular}
should read

\begin{tabular}{l}
 $(\exists{u})N(u) \mathand (x)\Big[N(x)\rightarrow{}\Big((\exists{y})F(x,y) \mathand (y)\big(F(x,y)\rightarrow{N(y)}\big)\Big)\Big]$\\
\end{tabular}
.

page 254, the 7th line from the bottom: The formula

\begin{tabular}{l}
 $\mathfrak{A}_{\phi} \mathand F^{(N^{\prime})} \rightarrow \left(-H(u^{(n)},u^{(m)}\right)$\\
\end{tabular}
should read

\begin{tabular}{l}
 $\mathfrak{A}_{\phi} \mathand F^{(N^{\prime})} \rightarrow \left(-H(u^{(n)},u^{(m)})\right)$.\\
\end{tabular}
.

page 255, line 1:\alpha_{n}=0” should read “\alpha_{n}=\pm{\infty}”.

page 256, line 3:-G(\alpha) \rightarrow \alpha \geqslant \xi” should read “-G(\alpha) \rightarrow \alpha > \xi”.

page 256, lines 7-11: There is a passage:

Owing to this restriction of Dedekind's theorem, we cannot say that a computable bounded increasing sequence of computable numbers has a computable limit. This may possibly be understood by considering a sequence such as

\hfill -1,\ -\frac{1}{2},\ -\frac{1}{4},\ -\frac{1}{8},\ -\frac{1}{16},\ \frac{1}{2},\ \cdots\ .\hfill
.

No matter of what I can't understand the passage, it refers unambiguously to, among others, what we call today the Specker sequence, that is “a computable, strictly increasing, bounded sequence of rational numbers whose supremum is not a computable real number.” (Wikipedia “Specker sequence”.)

He might argue here in effect a sequence \{\varepsilon_{K}\}_{K\in\pint} defined by

\varepsilon_{K} \equiv -2+\sum_{N=1}^{K}2^{N-R(N)-1}
where R(N) is the number of satisfactory positive integers (cf. p.241 and p.247) not greater than a positive integer N. The sequence is increasing with an upper bound, and has a supremum real number \displaystyle{}\lim_{K  \rightarrow \infty}{\varepsilon_{K}}. He might refer to a fact that every partial sum is rational and thus computable, though the supremum is not computable (cf. p.247).

As far as following Turing's convention in the [main paper 1937], the first positive integers reaching to a few thousands are unsatisfactory. As many first members of the sequence \{\varepsilon_{K}\}_{K\in\pint} are identical with those of a geometric sequence \{-2^{-K}\}_{K\in\pint}, that is

\hfill -1,\ -\frac{1}{2},\ -\frac{1}{4},\ -\frac{1}{8},\ -\frac{1}{16},\ -\frac{1}{32},\ \cdots\ .\hfill
.

page 257, line 9: The formula

\begin{tabular}{l}
  $\hspace{5mm}\mathand \Big[H(w,z) \mathand G(z,t) \mathbin{\mathrm{v}} G(t,z) \rightarrow \Big(-H(w,t)\Big)\Big]$
 \end{tabular}
should read

\begin{tabular}{l}
 $\hspace{5mm}\mathand \Big[H(w,z) \mathand \Big(G(z,t) \mathbin{\mathrm{v}} G(t,z)\Big) \rightarrow \Big(-H(w,t)\Big)\Big]$
 \end{tabular}
.
Composition of Logical conjunction “\&” and sum “\mathrm{v}” are not associative, and thus a pair of parentheses must be added to enclose “G(z,t) \mathbin{\mathrm{v}} G(t,z)”.

page 257, the 2nd line from the bottom:m \neq \eta(u)” should read “m \neq \eta(n)”.

page 257, the last line: The formula

\begin{tabular}{l}
 $\hspace{5mm} \mathfrak{A}_{\eta} \mathand F^{(M^{\prime})} \rightarrow G(u^{\eta((n))},u^{(m)}) \mathbin{\nu} G(u^{(m)},u^{\eta((n))})$\\
\end{tabular}
should read

\begin{tabular}{l}
 $\hspace{5mm} \mathfrak{A}_{\eta} \mathand F^{(M^{\prime})} \rightarrow G(u^{\eta((n))},u^{(m)}) \mathbin{\mathrm{v}} G(u^{(m)},u^{\eta((n))})$.
\end{tabular}
.
In the paper, the small Latin letter “\mathrm{v}” seems a prescribed symbol for the logical sum, and the small Greek letter “\nu” should be replaced with “\mathrm{v}”.

page 258, lines 2-3: The formula

\begin{eqnarray*}
  &&\mathfrak{A}_{\eta} \mathand F^{(M^{\prime})} \rightarrow \Big[\big\{G(u^{(\eta(n))},u^{(m)}) \mathbin{\nu} G(u^{(m)}, u^{(\eta(n))})\hspace{20mm}\\
 &&\hspace{40mm} \mathand H(u^{(n)},u^{(\eta(n))} \big\} \rightarrow \left(-H(u^{(n)},u^{(m)})\right) \Big]
 \end{eqnarray*}
should read

\begin{eqnarray*}
  &&\mathfrak{A}_{\eta} \mathand F^{(M^{\prime})} \rightarrow \Big[\Big\{\Big(G(u^{(\eta(n))},u^{(m)}) \mathbin{\mathrm{v}} G(u^{(m)}, u^{(\eta(n))})\Big)\hspace{20mm}\\
 &&\hspace{40mm} \mathand H(u^{(n)},u^{(\eta(n))}) \Big\} \rightarrow \left(-H(u^{(n)},u^{(m)})\right) \Big]
 \end{eqnarray*}
.

page 258, line 10: “the m-configuration b” should read “the m-configuration \mathfrak{b}”.

page 258, the 6th line from the bottom: The row

\begin{tabular}{ll}
 $\hspace{5mm} \mathfrak{u}_{2}$ & $\hspace{30mm}\mathfrak{re}(\mathfrak{u}_{3},\mathfrak{u}_{3},k,h)$\\
\end{tabular}
should read

\begin{tabular}{ll}
 $\hspace{5mm} \mathfrak{u}_{2}$ & $\hspace{30mm}\mathfrak{re}(\mathfrak{u}_{3},\mathfrak{b},k,h)$\\
\end{tabular}
.
The machine \mathscr{N}^{\prime} repeats the computation of the machine \mathscr{N} to get a figure \phi_{n}(n) for every positive integer n, and must bring its m-configuration back to \mathfrak{b}, the first m-configuration of \mathscr{N}, each time one figure is computed and the symbol k disappears from the complete configuration of \mathscr{N}^{\prime}. (I would warn you that the appearance of the script capital \mathscr{N} used here is quite different from the one seen in the [main paper 1937]).

page 259, the last line:S” should read “S_{l}” to accord with the term “R_{S_{l}}(x,y)” on the one line before.

page 260, lines 7-9: In his [correction paper 1938, p.544](2), Turing changed the definition of \mathrm{Inst}\{q_{i}S_{j}S_{k}Lq_{l}\} from

\begin{eqnarray*}
&&(x,y,x^{\prime},y^{\prime})\Big\{\Big(R_{S_{j}}(x,y) \mathand I(x,y) \mathand K_{q_{i}}(x) \mathand F(x,x^{\prime}) \mathand F(y^{\prime},y)\Big)\\
&&\rightarrow \Big(I(x^{\prime},y^{\prime}) \mathand R_{S_{k}}(x^{\prime},y) \mathand K_{q_{l}}(x^{\prime})\\
&&\hspace{40mm}\mathand (z)\left[F(y^{\prime},z) \mathbin{\mathrm{v}} \left(R_{S_{j}}(x,z) \rightarrow R_{S_{k}}(x^{\prime},z)\right)\right]\Big)\Big\}
\end{eqnarray*}
to

\begin{eqnarray*}
&&(x,y,x^{\prime},y^{\prime})\Big\{\Big(R_{S_{j}}(x,y) \mathand I(x,y) \mathand K_{q_{i}}(x) \mathand F(x,x^{\prime}) \mathand F(y^{\prime},y)\Big)\\
&&\rightarrow \Big(I(x^{\prime},y^{\prime}) \mathand R_{S_{k}}(x^{\prime},y) \mathand K_{q_{l}}(x^{\prime}) \mathand F(y^{\prime},z) \mathbin{\mathrm{v}} \Big[\big(R_{S_{0}}(x,z) \rightarrow R_{S_{0}}(x^{\prime},z)\big)\\
&&\mathand \big(R_{S_{1}}(x,z) \rightarrow R_{S_{1}}(x^{\prime},z)\big) \mathand \ldots \mathand \big(R_{S_{M}}(x,z) \rightarrow R_{S_{M}}(x^{\prime},z)\big)\Big]\Big)\Big\}.
\end{eqnarray*}
However, the new definition should be amended as follows:

\begin{eqnarray*}
&&(x,y,x^{\prime},y^{\prime})\Big\{\Big(R_{S_{j}}(x,y) \mathand I(x,y) \mathand K_{q_{i}}(x) \mathand F(x,x^{\prime}) \mathand F(y^{\prime},y)\Big)\\
&&\rightarrow \Big(I(x^{\prime},y^{\prime}) \mathand R_{S_{k}}(x^{\prime},y) \mathand K_{q_{l}}(x^{\prime}) \mathand (z)\Big(F(y^{\prime},z) \mathbin{\mathrm{v}} \Big[\big(R_{S_{0}}(x,z) \rightarrow R_{S_{0}}(x^{\prime},z)\big)\\
&&\mathand \big(R_{S_{1}}(x,z) \rightarrow R_{S_{1}}(x^{\prime},z)\big) \mathand \ldots \mathand \big(R_{S_{M}}(x,z) \rightarrow R_{S_{M}}(x^{\prime},z)\big)\Big]\Big)\Big)\Big\}
\end{eqnarray*}
to include the universal quantifier (z).

page 260, line 15: As Turing wrote in the [correction paper 1938, p.545, l.14], “logical sum” should read “conjunction”.

page 260, lines 18-21: The definition of \mathrm{Un}(\mathscr{M}) given on lines 18-21 was withdrawn and replaced with the new definition (the [correction paper 1938, p.545]):

 (\exists{u})A(\mathscr{M}) \rightarrow (\exists{s})(\exists{t})R_{S_{1}}(s,t)
where A(\mathscr{M}) is abbreviation for

 Q \mathand (y)R_{S_{0}}(u,y) \mathand I(u,u) \mathand K_{q_{1}}(u) \mathand \mathrm{Des}(\mathscr{M})
and Q is abbreviation for

\begin{eqnarray*}
 &&(x)(\exists{w})(y,z)\Big\{F(x,w) \mathand \Big(F(x,y) \rightarrow G(x,y)\Big) \mathand \Big(F(x,z) \mathand G(z,y) \rightarrow G(x,y)\Big)\\
&&\hspace{5mm}\mathand \Big[G(z,x) \mathbin{\mathrm{v}} \Big(G(x,y) \mathand G(y,z)\Big) \mathbin{\mathrm{v}} \Big(F(x,y) \mathand F(z,y)\Big) \rightarrow \Big(-F(x,z)\Big)\Big]\Big\}
\end{eqnarray*}
.
Here, in my opinion, A(\mathscr{M}) might be changed to “A(\mathscr{M})(u)” because the formula comes along with the free variable u.

page 261, line 10:\mathand (y)F\Big((y,u^{\prime})\mathbin{\mathrm{v}}\ldots” should read “\mathand (y)\Big(F(y,u^{\prime})\mathbin{\mathrm{v}}\ldots”.

page 261, line 29: As Turing wrote in the [correction paper 1938, p.545, l.13], 
 r\big(n,i(n)\big) = a, r\big(n+1,i(n+1)\big) = c, k\big(i(n)\big)=b, \mbox{ and } k\big(i(n+1)\big)=d
should read

 r\big(n,i(n)\big) = b, r\big(n+1,i(n)\big) = d, k(n)=a, \mbox{ and } k(n+1)=c .

page 261, line 33: As Turing wrote in the [correction paper 1938, p.545, l.11],

 \mathrm{Inst}(q_{a}S_{b}S_{d}Lq_{c}) \mathand F^{(n+1)} \rightarrow (CC_{n} \rightarrow CC_{n+1})
should read

 \mathrm{Inst}(q_{a}S_{b}S_{d}Lq_{c}) \mathand Q \mathand F^{(n+1)} \rightarrow (CC_{n} \rightarrow CC_{n+1}).

page 262, line 9:A(\mathscr{M}) \mathand F^{(N)} \rightarrow CC^{N}” should read “A(\mathscr{M}) \mathand F^{(N)} \rightarrow CC_{N}”.

page 263, line 20:1+\phi_{\gamma}(u)” should read “1+\phi_{\gamma}(n)”.

page 264, the 4th line from the bottom:U” should read “U_{\gamma}”.

page 265, the 8th line from the bottom: The definition of “Q

\begin{tabular}{l}
  $\hspace{5mm} \Big\{\{Q\}{W_{\gamma}}\Big\}(N_{s}) \mathbin{\mathrm{conv}} N_{r(z)}$
\end{tabular}
should read

\begin{tabular}{l}
  $\hspace{5mm} \Big\{\{Q\}{W_{\gamma}}\Big\}(N_{s}) \mathbin{\mathrm{conv}} N_{r(s)}$.
\end{tabular}
Namely, the subscript “{}_{r(z)}” should be changed to “{}_{r(s)}”.

REFERENCE

  1. [main paper 1937]
    Turing, Alan.
    “On Computable Numbers, with an Application to the Entscheidungsproblem”
    Proceedings of the London Mathematical Society. ser.2 vol.42: pp.230-265. 1937.
  2. [correction paper 1938]
    Turing, Alan.
    “On Computable Numbers, with an Application to the Entscheidungsproblem. A Correction”
    Proceedings of the London Mathematical Society. ser.2 vol.43: pp.544-546. 1938.

NOTE

1. I have drafted the PDF version of this article.

2. You can read the papers in the book below:

|
|

« ブログテンプレート変更 | トップページ | 「门内有径」の意味 »

ドイツ語/Deutsch」カテゴリの記事

数学」カテゴリの記事

英語/English」カテゴリの記事

読み物・書き物・刷り物」カテゴリの記事

コメント

コメントを書く



(ウェブ上には掲載しません)


コメントは記事投稿者が公開するまで表示されません。



トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/40172/52645111

この記事へのトラックバック一覧です: Errata and Typographical Remarks on Alan Turing's "On Computable Numbers, with an Application to the Entscheidungsproblem":

« ブログテンプレート変更 | トップページ | 「门内有径」の意味 »