\documentstyle[11pt,psfig]{article}
%to kill bld in label for 209:
\def\descriptionlabel#1{\hspace\labelsep #1}
\begin{document}
%\chapter{The
%Narrational Case Against Church's Thesis}
\title{The
Narrational Case Against Church's Thesis\thanks{I'm indebted to
Elliot Mendelson not only for his stimulating paper, but also
for his response to my analysis of it in personal communication.
Janet Folina provided insightful commentary on an ancestor of
this paper presented at the 1993 Eastern APA meetings in Atlanta --- comments
which I incorporate in my response to Mendelson's response.
I'm grateful
to Michael McMenamin
for providing, in his unpublished ``Deciding Uncountable Sets and
Church's Thesis," an excellent objection to my attack
on Church's Thesis (which I rebut below).}}
\author{Selmer Bringsjord\\
Dept.~of Philosophy, Psychology \& Cognitive Science\\
Department of Computer Science\\
Rensselaer Polytechnic Institute\\
Troy NY 12180 USA\\
{\tt selmer@rpi.edu} $\bullet$ {\tt http://www.rpi.edu/}$\sim${\tt brings}}
\date{}
\maketitle
\noindent In a recent and widely affirmed paper in
this journal,
%the {\em Journal of Philosophy},
Elliot Mendelson
\cite{mendelson}\footnote{Unless otherwise noted, all page references
are to this paper.}
challenges what he rightly calls the ``standard
conception" (230) of Church's Thesis (CT) --- the conception being that
CT is
unprovable. Unfortunately, as I demonstrate herein, once Mendelson's
target, and his attack upon it, are rigorously analyzed with help from
uncomputability theory, his challenge evaporates, and the cogent rationale
for the standard conception of CT is revealed.
This analysis will in turn constitute a foundation for overthrowing
CT on the basis of our rather remarkable ability to assimilate
and assess narrative.
After the foundation is
in place, I press forward in the hope, indeed, of refuting CT. I end by
considering some
other attacks on CT (some of which, as we shall see, Mendelson himself
tried to derail over forty years ago), and the relation between
these attacks and my own.
\section{Background}
At the heart of CT is the notion of an {\bf algorithm}, characterized in
traditional fashion by Mendelson as
\begin{small}
\begin{quote}
an effective and completely specified procedure for solving a whole class of
problems. $\ldots$ An algorithm does not require ingenuity; its application is
prescribed in advance and does not depend upon any empirical or random
factors. (\cite{mendelson}, p.~225)
\end{quote}
\end{small}
An {\bf effectively computable} function is then said to be the computing of a
function by an idealized ``worker"
or ``computist" following an algorithm.\footnote{In
his inaugural writings
(independent, by the way, of Turing's),
Post \cite{post.inaugural} spoke of mindless
``workers," humans whose sole job was to
slavishly follow explicit, excruciatingly
simple instructions. These are ``computists" for Turing.}
(Without loss
of generality, we can for present purposes view all functions as taking natural
numbers into natural numbers; i.e., for some arbitrary
$f$, $f : \mbox{{\bf N}} \rightarrow \mbox{{\bf N}}$). CT also
involves a more formal notion, typically that of a so-called
{\bf Turing-computable} function (or, alternatively, and equivalently,
that of a $\mu$-{\bf recursive}
function, or, $\ldots$). Mendelson employs Turing's approach, and Turing
machines will be familiar to most readers; we'll follow him:
a function $f : \mbox{{\bf N}} \rightarrow \mbox{{\bf N}}$ is
Turing-computable iff there exists a TM $M$ which, starting with $n$ on
its tape (perhaps represented by $n$ $\mid$s), leaves $f(n)$ on its tape after
processing.
(The details of the processing are harmlessly left aside
for now.) Given this
definition,
CT amounts to
\begin{small}
\begin{description}
\item[CT] A function is effectively computable if and only if it's
Turing-computable.\footnote{This is often called the Church-{\em Turing}
Thesis for obvious reasons.}
\end{description}
\end{small}
Now what exactly is Mendelson's aim? He tells us:
\begin{small}
\begin{quote}
Here is the main conclusion I wish to draw: it is completely unwarranted to
say that CT is unprovable just because it states an equivalence between a vague,
imprecise notion (effectively computable function) and a precise mathematical
notion (partial-recursive function). (\cite{mendelson}, p.~232)
\end{quote}
\end{small}
\noindent From this it follows that Mendelson's target is the traditional
{\em argument} for
the unprovability of CT. And the line of reasoning he means to attack runs as
follows.
\begin{small}
\begin{tabular}{llp{8.8cm}r}
\multicolumn{4}{c}{\rule [-3mm]{0mm}{8mm}\bf Arg$_1$}\\
& EQU & If some thesis T states an equivalence between a vague, imprecise notion and a
precise, mathematical notion, T is unprovable. &\\
{\tiny .}$^\cdot${\tiny .} & (1) & If CT states an equivalence between a vague, imprecise notion and a precise,
mathematical notion, CT is unprovable. & \\
& (2) & CT states an equivalence between a vague, imprecise notion and a precise,
mathematical notion. &\\
{\tiny .}$^\cdot${\tiny .} & (3) & CT is unprovable. & \\
\end{tabular}
\end{small}
\section{Mendelson's Attack}
Mendelson's attack on Arg$_1$ is based on ``theses" analogous to CT ---
``Peano's
Thesis," ``Tarski's Thesis," ``Frege's Thesis," and ``Weierstrass'
Thesis."\footnote{WT identifies the intuitive notion of limit with the
standard
$\epsilon$-$\delta$ definition.
Mendelson thinks that these
four theses are just some among many such ``theses." He mentions ``the notion
of measure as an
explication of area and volume, the definition of dimension in topology, the
definition of velocity as a
derivative, the definition of logical implication and logical equivalence in
first-order logic, and the
definitions of circle, triangle, interior of an angle, and many other geometric
concepts" (\cite{mendelson}, p.~232).}
The
first three, respectively, are:
\begin{small}
\begin{description}
\item[PT] $f$ is an intuitive, rule-based function if and only if
$f$ is a set of ordered pairs
satisfying ($\star$) if $(x, y) \in f$ and $(x, z) \in f$, then $y = z$.
\item[TT] Let $L$ be a first-order language, and $\cal I$
an interpretation based on $L$. Then a wff
$\phi$ of $L$ is true on $\cal I$ in the intuitive sense iff $\cal I$
$\models \phi$, i.e., $\cal I$ satisfies $\phi$, in the
Tarskian model-theoretic sense.
\item[FT] Again, let $L$ be a first-order language, and
$\cal I$ an interpretation based on $L$.
Then a wff $\phi$ is valid in Frege's intuitive sense iff $\models \phi$, i.e.,
$\phi$ is valid in the
model-theoretic sense.
\end{description}
\end{small}
\noindent But how does Mendelson use these three theses as ammunition for
his three-pronged (the prongs are distinguished on pp.~232-233;
he says his ``argument"
is based on ``three points") attack on Arg$_1$? Let's look at the three prongs in
turn, and blunt each.
The first prong, the most sophisticated and promising of the three, is an
attack on Arg$_1$'s premise (2): Mendelson seems to be saying that the
equivalence
this premise attributes to CT is chimerical:
\begin{small}
\begin{quote}
The concepts and assumptions that support the notion of partial-recursive
function are, in an essential way, no less vague and imprecise than the notion
of
effectively computable function; the former are just more familiar and are part
of a respectable theory with connections to other parts of logic and
mathematics. (The notion of effectively computable function could have been
incorporated into an axiomatic presentation of classical mathematics, but the
acceptance of CT made this unnecessary.) The same point applies to [PT, FT,
and TT]. Functions are defined in terms of sets, but the concept of set
is no clearer
than that of function and a foundation of mathematics can be based on a theory
using function as primitive notion instead of set. Tarski's definition of
truth is
formulated in set-theoretic terms, but the notion of set is no clearer than
that of
truth. The model-theoretic definition of logical validity is based ultimately
on set theory, the foundations of which are no clearer than our intuitive
understanding of logical validity. (p.~232)
\end{quote}
\end{small}
But how does not-(2) follow from this? What, exactly, is Mendelson's
argument? The key idea seems to be that (2) is false because
\begin{small}
\begin{description}
\item[(4)] The notion of Turing-computable function is no clearer than, nor more
mathematically useful (foundationally speaking) than, the notion of an
effectively computable function.
\end{description}
\end{small}
We can probably all agree that (4) implies not-(2). But is (4) true?
Mendelson gives both a direct rationale for (4) and an argument for it based
on PT, FT, TT, and WT. Let's consider, first, the argument based on these
other theses. Mendelson's hope seems to be that (4) follows from
$$
\mbox{$X$ is no clearer than, nor $\ldots$ than $Y$}
$$
when this template, tied to the other ``theses," is
filled in in the expected way.
For example, with respect to TT, the template becomes
$$
\mbox{`true on some $\cal I$' is no clearer than, nor} \ldots
\mbox{than, `intuitive truth'}$$
And with respect to PT the template becomes
$$
\mbox{`($\star$)-based function' is no less vague than, nor
$\ldots$ than, `intuitive function'}$$
But there is a problem: Mendelson
doesn't {\em establish} these statements. He
simply asserts them. And that's not enough --- especially when the default
intuition is likely to be that these statements are false. Now, Mendelson does
seem to think that such statements follow from (or are at least supported by)
the fact that things like ZF can in principle be replaced with foundations that
take the concept of function as primitive. But {\em how}
does it follow from
this that, e.g.,
$$
\mbox{`($\star$)-based function' is no clearer than, nor $\ldots$ than,
`intuitive function'?}$$
Mendelson doesn't answer this question.
But let's assume for the sake of argument that the template filled in for PT
(and FT, TT, WT) is true. We can then ask whether (4) follows from this
assumption. Does it? No. In fact, it seems relatively easy to show that
(4) is
false, once one looks a bit at uncomputability theory. Here's how the
demonstration works: Clearly, if
\begin{small}
\begin{description}
\item[(4)] The notion of Turing-computable function is no clearer than, nor more
mathematically useful (foundationally speaking) than, the notion of an
effectively computable function,
\end{description}
\end{small}
\noindent then
\begin{small}
\begin{description}
\item[(5)] The notion of Turing-decidable set is no clearer than, nor more mathematically
useful (foundationally speaking) than, the notion of an effectively decidable
set,
\end{description}
\end{small}
\noindent and
\begin{small}
\begin{description}
\item[(6)] The notion of Turing-enumerable set is no clearer than, nor more
mathematically useful (foundationally speaking) than, the notion of an
effectively enumerable set,
\end{description}
\end{small}
$$\vdots$$
Now suppose that (4) is true. From this assumption, and the conditional
indicated immediately above, it would seem to follow by {\em modus ponens} and
simplification of conjunction that
\begin{small}
\begin{description}
\item[(+)] The notion of a formally defined program for guiding the operation
of
a TM is no
clearer than, nor more mathematically useful (foundationally speaking) than,
the notion of an algorithm.
\end{description}
\end{small}
This proposition, it would then seem, is the very heart of the matter.
If (+) is
true then Mendelson has made his case; if this proposition is false, then his
case is doomed, since we can chain back by {\em modus tollens} and negate (4).
What's the verdict? It's possible to demonstrate the falsity of (+), by way of
the following straightforward reasoning.
\begin{center}
\begin{small}
\begin{tabular}{llp{8.8cm}r}
\multicolumn{4}{c}{\rule [-3mm]{0mm}{8mm}\bf Arg$_2$}\\
& (7) & If (+), then one should be able to construct the Arithmetic Hierarchy by way
of the notion of an algorithm. &\\
& (8) & One cannot construct the Arithmetic Hierarchy by way of the notion of an
algorithm. & \\
{\tiny .}$^\cdot${\tiny .} & (9) & Not-(+) & \\
\end{tabular}
\end{small}
\end{center}
This argument is obviously valid. Are the premises true? Of course, this
question may be premature for some, since some readers may be unfamiliar
with the Arithmetic Hierarchy (AH). So let's take a detour to encapsulate this
notion. (Cognoscenti be forewarned: space constraints make a thorough
presentation of AH impossible. What follows is in no way a detailed,
accomplished introduction to AH.\footnote{For a comprehensive discussion of
uncomputability, including the Arithmetic Hierarchy, a good text is
\cite{davis.weyuker}. I provide a self-contained introduction to
the realm of ``super"-computation in \cite{digital}.})
Suppose we have some {\bf totally computable} predicate
$S(P, u, n)$ iff TM $M$,
running program $P$ on input $u$, halts in exactly $n$ steps
(= $M_P : u \rightarrow_n$ halt).
(Throughout AH our machines, architecturally speaking, are always simply
TMs.) Predicate $S$ is totally computable in the sense that, given some
triple $(P,
u, n)$, there is some program $P^\star$ which, running on some TM $M^\star$, can
infallibly give us a verdict, {\bf Y} (``yes") or
{\bf N} (``no"), for whether or not $S$ is true
of this triple. ($P^\star$ could simply instruct
$M^\star$ to simulate $M$ for $n$ steps and see
what happens.) This implies that
$S \in \Sigma_0$, i.e., that $S$ is a member of the
starting point in AH, a point composed of totally computable predicates. But
now consider the predicate $H$, defined by
$$
H(P, i) \mbox{ iff } \exists n S(P, i, n).$$
Since the ability to determine, for a pair $(P, i)$, whether or not $H$ is
true of it, is
equivalent to solving the full halting problem, we know that $H$ is not totally
computable. Hence $H \not\in \Sigma_0$. However, there is a program which,
when asked
whether or not some TM $M$ run by $P$ on $u$ halts, will produce
{\bf Y} iff $M_P : u \rightarrow$
halt. For this reason {\em H} is declared
{\bf partially computable}, and hence in $\Sigma_1$. To
generalize, informally, the syntactic representation of AH is:
\begin{small}
\begin{description}
\item[$\Sigma_n$] set of all predicates definable in terms of totally computable predicates
using at most $n$ quantifiers, the first of which is {\em existential}
\item[$\Pi_n$] set of all predicates definable in terms of totally computable predicates
using at most n quantifiers, the first of which is {\em universal}
\item[$\Delta_n$] $\Sigma_n \cap \Pi_n$
\end{description}
\end{small}
We have, based on this scheme, the Arithmetic {\em Hierarchy} because, where
$\subset$
is proper subset,
\begin{small}
$$
\begin{array}{c}
\Sigma_0 \subset \Sigma_1 \subset \Sigma_2 \ldots\\
\Pi_0 \subset \Pi_1 \subset \Pi_2 \ldots\\
\mbox{for every $m >0$, } \Sigma_m \not= \Pi_m\\
\Pi_m \subset \Sigma_{m+1}\\
\Sigma_m \subset \Pi_{m+1}
\end{array}
$$
\end{small}
It's possible to devise a more procedural view of (at the least the lower end
of) AH. $\Sigma_0$ and
$\Sigma_1$ have already been viewed procedurally. How, then, could
$\Pi_1$, the first genuinely uncomputable stop in AH, be viewed procedurally?
Peter
Kugel \cite{kugel.thinking}
has aptly called $\Pi_1$-procedures
{\bf non-halting procedures}; here's how
they essentially work. (Notice that the term `procedures' is being used, rather
than `programs'. This is crucial, for reasons that will be discussed in a
moment.) Let $R$ be a totally computable predicate; then there is some
program $P$ which decides $R$. Now consider a corresponding predicate
$G \in \Pi_1$,
viz.,
$$
G(x) \mbox{ iff } \forall y R(x, y).
$$
Here's a non-halting procedure
$P^+$ [not a program: we count $P^+$'s last output
(if there is one) as its result] for solving $G$, in the sense that a
{\bf Y} is the result iff
$Gx$:\footnote{The reader should satisfy herself that the following
procedure {\em does} decide $G$.}
\begin{small}
\begin{itemize}
\item Receive $x$ as input
\item Immediately print {\bf Y}
\item Compute, by repeatedly calling $P,
R(x, 1), R(x, 2), \ldots$, looking for a {\bf N}
\item If {\bf N} is found, erase {\bf Y} and leave result undefined
\end{itemize}
\end{small}
Notice that it would be
{\em impossible} to represent this procedure as a {\em program}.
This can be verified by looking at any formal specification of `program.' For
example, in {\em Mathematical Logic}, by Ebbinghaus {\em et al.}, \cite{ebb}
programs can have
only one {\sc print} instruction. (Typically, procedures are formalized by
{\em adding}
to programs the notion of an ``oracle.") But the point is that once you tinker
with the formalization of `program,' the world of uncomputability opens up,
a paradise that is richer than the small, familiar sub-hierarchy on the
computable side, which runs from finite automata, to push-down automata,
to linear-bounded automata, to TMs. Space doesn't permit exhibiting AH in
its full glory, but here's one more interesting fact about it, viz., that
procedures corresponding to
$\Sigma_2$, {\bf trial-and-error procedures}, can rather easily
solve the full halting problem --- as follows. Let a TM ---
$M^{\star \star}$ --- with $n^M$ as
input (G\"{o}del number of arbitrary TM $M$) output
{\bf N} immediately, and then let
it simulate $M$. If $M$ halts, $M^{\star \star}$ erases
{\bf N}, outputs {\bf Y} and halts itself. If we
count $M^{\star \star}$'s last output as its output, the full halting
problem is solved!
But what is the point of all this? The point is that even a cursory look at
AH reveals that Arg$_2$, Mendelson's counter-argument from above, is sound.
Why? I take it, first, that (7) is uncontroversial.\footnote{In
fact, it would seem that (7) is itself provable via conditional proof:
Start by assuming that (+), and
then simply consider building AH by way of the unformalized notion of an
algorithm.}
Since Arg$_2$ is formally valid,
if (8), the only other premise in the argument, is true, the argument is sound.
Premise (8), recall, is
\begin{small}
\begin{description}
\item[(8)] One cannot construct the Arithmetic Hierarchy by way of the
notion of an
algorithm.
\end{description}
\end{small}
But our look at AH has established this premise, for the simple reason that
algorithms correspond to those things (programs) which must be significantly
modified in order to open up the infinite landscape of AH. Mendelson is of
course correct that it's possible to supplant ZF with any number of equivalent
constructions which don't take `set' as primitive. But if one takes `algorithm'
as primitive, one will forever close off AH, since to gain access to this paradise
one must
{\em formalize} `algorithm,' and then begin to ``tinker" with the details of
this formalization.
It's important to note that the crucial (8) is distinct from
\begin{small}
\begin{description}
\item[(8$^\star$)] One cannot construct the Arithmetic Hierarchy
without the notion of an
algorithm.
\end{description}
\end{small}
Proposition (8$^\star$) is false, because it's possible (and to some, preferable) to
develop the theory of relative computability (of which AH is but a small part)
by way of the notion of a function, with programs, oracles, algorithms and the
like left by the wayside. Premise (8), on the other hand, says that AH cannot
be constructed by way of the notion of an algorithm --- and this is so, to
repeat, because such a route gives you nothing like the fine-grained analysis
of the ``function route" (which requires composition, primitive recursion,
unbounded minimalization, etc.).\footnote{Heading
off the erroneous conflation of (8$^\star$) and (8) is something Kostas
Arkoudas, in objecting to my
argument, stimulated me to consider; I'm indebted.}
What about the second prong in Mendelson's attack? This prong is aimed
against the EQU principle, which was the first premise in Arg$_1$, the argument
Mendelson believes he has undermined. Here is the relevant quote:
\begin{small}
\begin{quote}
The assumption that a proof connecting intuitive and precise mathematical
notions is impossible is patently false. In fact, half of CT (the ``easier" half),
the assertion that all partial-recursive functions are effectively computable, is
acknowledged to be obvious in all textbooks on recursion theory. (p.~232)
\end{quote}
\end{small}
Mendelson proceeds to give the ``proof" of the ``if" part of CT (p.~231). I
readily concede that he does in fact prove the ``if" part. But a question
remains: How does not-EQU follow from this sub-proof? EQU would be
overthrown by a counter-example in which this principle's antecedent is true
but its consequent is not. But this is {\em not} the situation Mendelson
creates by
way of his sub-proof. At best, he has overthrown {\em this} principle:
\begin{small}
\begin{description}
\item[EQU$^\rightarrow$] If some thesis
T states a conditional connection between a vague, imprecise
notion and a precise, mathematical notion, then T is unprovable.
\end{description}
\end{small}
The obvious question then arises: are any of PT, FT, TT provable? If so, then
Mendelson might be able to sustain the fight. But it's hard to see how one
would even begin to prove these. (Skeptics are encouraged to embark upon
the proofs. Better yet, next time you or a colleague teaches first-order logic,
assign one of these proofs on an exam.) At any rate, the proofs would clearly
be non-trivial; and since Mendelson has provided neither these proofs, nor
sketches for how to carry them out, there is no reason, in the context of the
present dialectic, to suppose that the trio analogous to CT --- PT, FT, TT --- is
provable.
What is M's third prong? Essentially, it's the claim that ``the usual
viewpoint concerning CT is that it assumes that the only way to ascertain the
truth of the equivalence asserted in CT is to
{\em prove} it" (p.~233). Mendelson
goes on to claim that
\begin{small}
\begin{quote}
$\ldots$ equivalences between intuitive notions and apparently more precise
mathematical notions often are simply ``seen" to be true without proof, or are
based on arguments that are a mixture of such intuitive perceptions and
standard logical and mathematical reasoning. (p.~233)
\end{quote}
\end{small}
\noindent Here Mendelson seems to commit a bald
{\em non sequitur}. For notice that
nothing in this quote threatens Arg$_1$. Nowhere in Arg$_1$ is there a
hidden premise
to the effect that there aren't arguments-short-of-proof for CT. On the
contrary, as is well-known, those impressed by
{\em inductive} arguments often
affirm CT on the basis of such reasoning. So how does Mendelson's third
prong constitute a challenge to the orthodox view on CT? Apparently, it
simply doesn't. Even Mendelson himself seems to concede that the third
prong is a bit beside the point:
\begin{small}
\begin{quote}
That CT is true follows, I believe, from Turing's analysis of the essential
elements involved in computation. But this is not what I have tried to
establish. The point I have attempted to make is the equivalences between
intuitive notions and ``precise" notions need not always be considered
unprovable theses.\footnote{The
last sentence here is somewhat peculiar, since it could be verified by
something that would not
necessarily defeat A1. Indeed, this sentence could be verified by an
argument which lacked reference to
CT.}
(p.~233)
\end{quote}
\end{small}
The third prong would be relevant if there were good deductive arguments
for CT, {\em and} if what Mendelson calls the ``usual viewpoint" ruled them out.
But to enlarge the ``usual viewpoint concerning CT" this way would be to
create a straw man. Besides, I have a
formidable deductive argument {\em against CT},
and so it would be rather double-minded
if I went in search of deductive arguments {\em for} the thesis. My deductive
argument against CT doesn't derive from the view that this thesis
connects a vague notion with a mathematical one. It derives from another
application of uncomputability theory. But before presenting that argument,
I consider Mendelson's response\footnote{Personal
communication, December 14, 1993.} to what I have so far said against him.
\section{Mendelson's Rebuttal}
Mendelson concedes that a significant
part of my case succeeds, that is,
that (4) is indeed false: He agrees that the
formal concepts in
question (e.g., `Turing-computable function') are more useful than
their informal partners (e.g., `effectively computable function'); and he
admits that ``One could, with some justification, claim that the notion
of a Turing-computable function is `clearer' than that of an effectively
computable function because the former is more specific and ties in closely
with other well-known mathematical concepts." However, Mendelson goes
on to say:
\begin{small}
\begin{quote}
My point in this case has nothing to do with relative clarity of concepts.
Rather, the point is that the notion of an effectively computable function
is not essentially different from the notions that underlie the theory of
Turing-computable functions, and, more specifically, that the former notion
can be used in mathematical proofs just as legitimately as the latter notions.
This was illustrated in my paper by the proof that all partial-recursive
functions are effectively computable. That proof, which Professor Bringsjord
himself accepts, undermines the basis for the traditional belief in the
unprovability of the the Church-Turing Thesis, namely, that there is in
principle an unbridgable gap between, on the one hand, arguments that
involve `vague, intuitive' notions, and, on the other hand, `respectable'
proofs that can be formalized within, say, ZF or PA.
\end{quote}
\end{small}
Unfortunately, this rebuttal fails. Yes, I did indeed concede that
Mendelson's mathematical argument for the so-called ``easier" half of
CT constitutes
a proof (though I think Mendelson's comment following
that argument --- ``This simple argument is as clear a proof as I have
seen in mathematics" (233) --- is at least peculiar, and possibly
disingenuous). But Mendelson seems to ignore my observation that
his proof doesn't substantiate the premise in Arg$_1$ called `EQU:'
\begin{small}
\begin{description}
\item[EQU]If some thesis T states an equivalence between a vague,
imprecise notion and a
precise, mathematical notion, T is unprovable.
\end{description}
\end{small}
Lest it be thought that I tendentiously cooked up
this premise, and set it as an unreachable
target for Mendelson, I remind the reader
that the text in question is clear: there can be little doubt that Mendelson
targets EQU. Consider again, for example, what he says on page 232:
\begin{small}
\begin{quote}
Here is the main conclusion I wish to draw: it is completely unwarranted to
say that CT is unprovable just because it states an
{\em equivalence} between a vague,
imprecise notion (effectively computable function) and a precise mathematical
notion (partial-recursive function). (\cite{mendelson}, p.~232;
emphasis mine)
\end{quote}
\end{small}
\noindent And again on page 233 Mendelson says
that ``{\em equivalences} between intuitive
and `precise' notions need not always be considered unprovable theses"
(emphasis mine).
Now Janet Folina \cite{folina}
has suggested that Mendelson's aim be charitably
scaled back --- so that what he is said to be aiming at
is {\em not} a demonstration
that CT is provable (an aim she agrees I have shown Mendelson cannot
reach), but rather a demonstration that proofs merely {\em connecting}
intuitive with formal notions are possible. This reconstruction of
Mendelson's main argument is, predictably, one that I would gladly
accept.\footnote{Incidentally, the reconstruction probably has fatal
problems, as Folina \cite{folina}
points out. After all, {\em is} what Mendelson
calls a proof here a proof? One common conception --- indeed, probably
the {\em dominant} conception --- of a proof is a transformation in
some formal system. Yes Mendelson says about his proof: ``The fact that
it is not a proof in ZF or some other axiomatic system is no drawback;
it just shows that there is more to mathematics than appears in ZF" (233).
(Remember this quote later when we consider Mendelson's rejection of
Kalm\'{a}r's argument against CT because in part because it falls
outside any standard formal system.)
A lot of thinkers will balk at this. As Folina
\cite{folina} notes, many will
diagnosis the situation by saying that what Mendelson has shown is that
there is more to mathematics than proofs. (This is something we've
known all along, of course.) Moreover, if Mendelson's reasoning {\em isn't}
a proof, then what is it? If it's merely a {\em precise, compelling argument}
connecting an intuitive notion with a formal one, then it shows something
we knew to be true all along.}
With our foundation laid, I turn now to my narrational attack on CT.
\section{Attacking Church's Thesis}
My suspicion that CT is false first arose in connection with the concept of
{\bf productive} sets, which have two properties:
\begin{small}
\begin{description}
\item[P1] They
are classically undecidable (= no program can decide such sets).
\item[P2] There is a computable function $f$
from the set of all programs to any such set, a function which, when
given a candidate program $P$, yields an element of the
set for which $P$ will fail.
\end{description}
\end{small}
\noindent Put informally, a set $A$ is productive iff it's not only classically
undecidable,
but also if any program proposed to decide $A$ can be counter-exampled with
some element of $A$. Clearly, if a set $A'$ has these properties, then
$A' \not\in \Sigma_0$ and
$A' \not\in \Sigma_1$. If $A'$ falls somewhere in AH, and is
effectively decidable, then CT falls. But what could possibly fit the bill?
I have become convinced that the set $\cal S$
of all interesting stories provides
a perfect fit.
This no doubt catches you a bit off guard. Interesting stories? Well,
let me remind you, first, that the view that there are productive
sets near at hand is far from unprecedented.
Douglas Hofstadter \cite{hof.knuth}, for example, holds that the set $\cal A$
of all {\tt A}s is a productive set. In order to satisfy P1, $\cal A$
must forever resist attempts to write a program for deciding this set;
in order to satisfy P2, there must at minimum always be a way to ``stump"
a program intended to decide $\cal A$. That $\cal A$ satisfies both
these conditions isn't all that implausible --- especially when one
faces up to the unpredictable variability seen in this set. For example,
take a look at Figure 1 (from \cite{letraset}).
\begin{figure}
\centerline{\psfig{figure=/dept/ppcs/SUPER/CT/letter.as.ps,height=2.5in}}
\caption{Various Letter {\tt A}s}
\end{figure}
In order for a program to decide $\cal A$, it must capitalize on some
rules that capture the ``essence" of the letter in question. But
what sorts of rules could these be? Does the bar in the middle need
to touch the sides? Apparently not (see 2 A). Does there have to
be a bar that {\em approximates} connecting the sides?
Apparently not (see 7 G). And on and
on it goes for other proposed rules.
However, it must be conceded that no {\em argument} for the
productivity of $\cal A$ has been provided by Hofstadter. For all we know,
some company could tomorrow announce a letter recognition system
that will work for all {\tt A}s. The situation is a bit different
in the case of the mathematician Peter
Kugel \cite{kugel.thinking}, who makes clever use of
an elementary theorem in unmistakably {\em arguing} that the
set of all beautiful objects is located above $\Sigma_1$ in AH:
\begin{small}
\begin{quote}
We seem to be able to recognize, as beautiful, pieces of music that we almost
certainly could not have composed. There is a theorem about the partially
computable sets that says that there is a uniform procedure for turning a
procedure for recognizing members of such sets into a procedure for generating
them. Since this procedure is uniform --- you can use the same one for all
computable sets --- it does not depend on any specific information about the set
in question. So, if the set of all beautiful things were in
$\Sigma_1$, we should be able to
turn our ability to recognize beautiful things into one for generating them
\ldots
This suggests that a person who recognizes the Sistine Chapel Ceiling as
beautiful knows enough to paint it, [which] strikes me as
somewhat implausible. (\cite{kugel.thinking}, pp.~147-148)
\end{quote}
\end{small}
The main problem with this line of reasoning is that it's disturbingly
exotic. Beauty is perhaps
a promising candidate for what Kugel is after, but
it must be conceded that most of those scientists who
think seriously about human cognition don't think a lot about beauty.
Indeed, they don't seem to think {\em at all} about beauty.\footnote{A
search for coverage of this concept in standard texts about cognition ---
e.g., \cite{ashcraft} and \cite{stillings} --- turns up nothing
whatever.}
And this isn't (they would insist) because beauty is a daunting concept,
one that resists recasting in computational terms. The stance would
doubtless be that beauty is left aside because one can
exhaustively analyze cognition
(and replicate it on a machine) without bothering to grapple in earnest
with
this concept.
This claim about the
irrelevance of beauty may strike some as astonishing,
and it certainly isn't a view affirmed by each and every
computationalist,
but I gladly concede it for the sake of argument:
for the record, I grant that ignoring beauty, in the
context of attempts to model, simulate, and replicate mentation, is
acceptable.\footnote{What argument could be mustered for ignoring
beauty in the context of attempts to reduce cognition to computation,
or to build an artificial agent capable of behaviors analogous to human
ones typically taken to involve beauty? I envisage an argument
running parallel to the one John Pollock
\cite{pollock.cc} gives for ignoring human emotions
in his attempt to build an artificial person. Pollock's view, in a nutshell,
is that human emotions are in the end just ``time savers;" with fast
enough hardware, and clever enough algorithms, artificial persons could
{\em compute} the need to quickly flee (say) a lion, whereas we take one
look and immediately feel a surge of fear that serves to spark our
rapid departure.}
However, I think there is another concept
that serves my purposes perfectly: namely, the concept of
a {\em story}. Stories
are thought by many to be at the very heart of
cognition.
For example, in their lead target chapter in
{\em Knowledge and Memory:~The Real Story} \cite{wyer}, Roger Schank and
Robert Abelson, two of the most eminent scientists in the
world working in the
area of cognition and computation, boldly assert on
the first page that ``virtually
all human knowledge" is based on stories.\footnote{An
insightful review of this book has been written by
Tom Trabasso \cite{trabasso}.} Schank and Abelson
go on to claim that since the essence of cognition inheres in narrative,
we can jettison propositional, logic-based, rule-based, formal $\ldots$
schemes
for knowledge representation. Among the 17 commentators who
react to the target piece, 13 affirm the story-based
view (the remaining
four authors are skeptical).\footnote{Schank
has devoted a book to the view that stories are at the very heart
of human cognition: \cite{schank.tell}. This is probably as good
a place as any to point out that Dennett's {\em Consciousness Explained}
\cite{dennett.ce}
can be read as a defense of the view (his ``multiple
drafts" view of consciousness) that thinking is at bottom
the the spinning out of parallel stories.}
The other nice thing about stories, from my perspective, is that
apparently
I know a thing or two about them, especially in the context
of computation.
For six years now, I have co-directed an
AI research group --- {\em Autopoeisis} ---
devoted to creating an artificial agent capable of autonomously
creating sophisticated fiction. I first discussed this project
in my {\em What Robots Can and Can't Be} \cite{wrccb}, in
which I specifically
discussed the challenge of characterizing, precisely, the class of
{\em interesting} stories. (My main claim was that analytic philosophy
offers the best hope of supplying this characterization.)
For those who seek to build agents capable of creative feats like
good storytelling, this is a key challenge. It's easy enough to build
systems capable of generating {\em un}interesting stories. For
example, the world's first artificial story generator, TALE-SPIN
\cite{tale.spin}, did a good job of that. Here, for example,
is one of TALE-SPIN's best stories:
\medskip
\begin{small}
\begin{quote}
\centerline{``Hunger"}
Once upon a time John Bear lived in a cave. John knew that John was in
his cave. There was a beehive in a maple tree. Tom Bee knew that the
beehive was in the
maple tree. Tom was in his beehive. Tom knew that
Tom was in his beehive. There was some honey in Tom's beehive.
Tom knew that the honey was in Tom's beehive. Tom had the honey. Tom knew that
Tom had the honey. There was a nest in a cherry tree. Arthur Bird knew
that the nest was in the cherry tree. Arthur was in his next.
Arthur knew that John was in his cave. $\ldots$
\end{quote}
\end{small}
\medskip
How are things to be improved? How is one to go about building an
agent capable of creating truly interesting stories? It has been
the sustained attempt to answer this question, in conjunction with
the concept of productivity discussed above, that has persuaded me
that CT is indeed false. Let me explain.
First, to ease exposition, let $\cal S$$^I$ denote the set of all
interesting stories. Now,
recall that productive sets must have two properties,
P1 and P2; let's take them
in turn, in the context of $\cal S$$^I$. First, $\cal S$$^I$ must be
classically undecidable; i.e., there
is no program (= TM) which answers the question, for an arbitrary story
in $\cal S$,
whether or not it's interesting. Second, there must be some computable
function $f$ from the set of all programs to $\cal S$$^I$ which, when given
as input a
program $P$ that purportedly decides $\cal S$$^I$, yields an element of
$\cal S$$^I$ for which $P$
fails. It seems to me that $\cal S$$^I$ does have both of these
properties --- because, in a
nutshell, the {\em Autopoeisis} research group seems to invariably and
continuously turn up these two properties ``in action." Every time someone
suggests an algorithm-sketch for deciding $\cal S$$^I$, it's easily
shot down by a
counter-example consisting of a certain story which is clearly interesting
despite the absence in it of those conditions $P$ regards to be necessary for
interestingness. (It has been suggested that interesting stories must have
inter-character conflict, but monodramas can involve only one character. It
has been suggested that interesting stories must embody age-old plot
structures, but some interesting stories are interesting precisely because they
violate such structures, and so on.)
The situation we have arrived at can be crystallized in deductive form
as follows.
%\mbox{$\cal S$$^I$}
\begin{center}
\begin{small}
\begin{tabular}{llp{8cm}l}
\multicolumn{4}{c}{\rule [-3mm]{0mm}{7mm}\bf Arg$_3$}\\
& (9) & If $\mbox{$\cal S$$^I$} \in \Sigma_1$ (or $\mbox{$\cal S$$^I$}
\in \Sigma_0$),
then there exists a
procedure $P$ which
adapts programs for deciding members of $\mbox{$\cal S$$^I$}$ so as to
yield programs
for enumerating members of $\mbox{$\cal S$$^I$}$. &\\
& (10) & There's no procedure $P$ which adapts programs for deciding
members of $\mbox{$\cal S$$^I$}$ so as to yield programs for
enumerating members of $\mbox{$\cal S$$^I$}$.\\
.$^\cdot$. & (11) & $\mbox{$\cal S$$^I$} \not\in \Sigma_1$
(or $\mbox{$\cal S$$^I$}
\not\in \Sigma_0$). & 10, 11\\
& (12) & $\mbox{$\cal S$$^I$} \in$ AH. &\\
.$^\cdot$. & (13) & $\mbox{$\cal S$$^I$} \in \Pi_1$ (or above in the AH). & disj syll\\
& (14) & $\mbox{$\cal S$$^I$}$ is effectively decidable. &\\
.$^\cdot$. & (15) & CT is false. & {\em reductio}\\
\end{tabular}
\end{small}
\end{center}
Clearly, Arg$_3$ is
formally valid.
Premise (9) is not only true, but necessarily
true, since it's part of the canon of elementary computability theory.
What about premise (10)? Well, this is the core idea,
the one expressed above by Kugel,
but transferred now to a different domain:
People who can {\em decide} $\cal S$$^I$, that is,
people who can decide whether something is an interesting story,
can't necessarily {\em generate} interesting stories.
Students in {\em Autopoeisis} have been a case in
point: with little knowledge of, and
skill for, creating interesting stories,
they can nonetheless recognize such narrative.
That is,
students who are, by their own admission, egregious creative writers, are
nonetheless discriminating critics. They can decide which stories are
interesting (which is why they know that the story generators AI has
produced so far are nothing to write home about), but {\em producing} the set of
all such stories
(including, as it does, such works as
not only {\em King Lear}, but {\em War and Peace}) is quite another matter.
These would be, necessarily, the {\em same} matter if the set of all interesting
stories, $\cal S$$^I$, was in either
$\Sigma_0$ or $\Sigma_1$, the algorithmic portion of AH.
But what's the rationale behind (13),
the claim that $\cal S$$^I$ is effectively decidable?
The rationale is simply the brute fact that a normal, well-adjusted human
computist can effectively
decide $\cal S$$^I$.
Try it yourself: First, start with the sort of
story commonly discussed in AI, for example:
\medskip
\begin{small}
\begin{quote}
\centerline{``Shopping"}
Jack was shopping at the supermarket. He picked up some milk from the
shelf. He paid for it and left.\footnote{From page 592
of \cite{charniak.intro}. The story is studied in the context of
attempts to resolve pronouns: How do we know who the first
occurrence of `He' refers to in this story? And how do render
the process of resolving the pronoun to Jack as a computational
one?}
\end{quote}
\end{small}
\medskip
Well? Your judgement?
Uninteresting, I wager.
Now go back to ``Hunger," and come up
with a judgement for it, if you haven't done so already.
Also uninteresting,
right? Now render a verdict on ``Betrayal,"
a story produced
by {\em Autopoeisis}' artificial intelligence,
{\sc brutus}:\footnote{{\sc Brutus}'s cognitive anatomy is described in
detail in \cite{brutus}.}
\medskip
\begin{small}
\begin{quote}
\centerline{``Betrayal"}
Dave Striver
loved the university. He loved its ivy-covered clocktowers, its
ancient and sturdy brick, and its sun-splashed verdant greens and eager
youth. He also loved the fact that the university is free of the stark
unforgiving trials of the business world --- only this {\em isn't} a
fact: academia has its own tests, and some are as merciless as any in
the marketplace. A prime example is the dissertation defense: to earn
the PhD, to become a doctor, one must pass an oral examination on one's
dissertation. This was a test Professor Edward Hart enjoyed giving.
Dave wanted desperately to be a doctor. But he needed the signatures
of three people on the first page of his dissertation, the priceless
inscriptions which, together, would
certify that he had passed his defense. One of the signatures had
to come from Professor
Hart, and Hart had often said --- to others
and to himself --- that he was honored to help Dave secure his well-earned
dream.
Well before the defense, Dave gave Hart a penultimate copy of
his thesis. Hart read it and told Dave that it was
absolutely first-rate, and that he would gladly sign it at the defense.
They even shook hands in Hart's book-lined office. Dave noticed
that Hart's eyes were bright and trustful, and his bearing paternal.
At the defense, Dave thought that he eloquently summarized Chapter 3
of his dissertation. There were two questions, one from Professor
Rogers and one from Dr.~Meteer; Dave answered both, apparently to
everyone's satisfaction. There were no further objections.
Professor Rogers signed. He slid the tome to Meteer; she too signed,
and then slid it in front of Hart. Hart didn't move.
``Edward?" Rogers said.
Hart still sat motionless. Dave felt slightly dizzy.
``Edward, are you going to sign?"
Later, Hart sat alone in his office, in his big leather chair,
saddened by Dave's failure. He tried to think of ways he could help Dave
achieve his dream.
\end{quote}
\end{small}
\medskip
This time, interesting, right?
Now at this point some readers may be thinking: ``Now wait a minute.
Isn't your position inconsistent? On the one hand you cheerfully
opine that `interesting story' cannot be captured. But on the other you
provide an interesting story! ---
a story that must, if I understand your project,
capitalize upon some careful account of interestingness in narrative."
``Betrayal"
is based in significant part upon formalizations, in
intensional logic, of definitions taking the classic
form of necessary and sufficient conditions seen in analytic philosophy.
These definitions are given for ``immemorial themes;" in ``Betrayal"
the two themes are self-deception and, of course, betrayal.
Here is the definition of betrayal with which {\sc brutus}
works:\footnote{Note that the variables $t_i$ range over times,
and that $\le$ means ``earlier or simultaneous." Note also the
following clauses, which appear in clause 3$'$.
\begin{description}
\item[3] $s_r$ agrees with $s_d$ that $p$ ought to occur;
\item[6$'$] $s_d$ wants that there is some action $a$ which $s_r$ performs
in the belief that thereby $p$ {\em will} occur.
\end{description}}
\begin{small}
\begin{description}
\item[D] Agent $s_r$ betrays agent $s_d$ at $t_b$ iff there
exists some state of affairs
$p$ and $\exists t_i, t_k \: (t_i \le t_k \le t_j \le t_b)$ such that
\begin{description}
\item[1] $s_d$ at $t_i$ wants $p$ to occur;
\item[2] $s_r$ believes that $s_d$ wants $p$ to occur;
\item[3$'$] (3 $\wedge$ 6$'$) $\vee$
\begin{description}
\item[6$''$] $s_d$ wants at $t_k$ that there is no action $a$ which
$s_r$ performs in
the belief that thereby $p$ will not occur;
\end{description}
\item[4$''$] there is some action $a$ such that:
\begin{description}
\item[4$''$a] $s_r$
performs $a$ at $t_b$
in the belief that thereby $p$ will {\em not} occur; and
\item[4$''$b] it's not the case that there exists a state of affairs $q$ such
that $q$ is believed by $s_r$ to be good for $s_d$ and $s_r$ performs $a$
in the belief that $q$ will not occur;
\end{description}
\item[5$'$] $s_r$ believes at $t_j$ that
$s_d$ believes that there is some action $a$ which $s_r$
will perform in the belief that thereby $p$ {\em will} occur.
\end{description}
\end{description}
\end{small}
All of this sort of work (i.e.,~the gradual crafting
of such definitions in the face of counter-example after
counter-example) is perfectly consistent with the absence of
an account of `interesting story.' {\em In fact}, this kind of philosophical
analysis figures in the observation that proposed accounts of interestingness
are invariably vulnerable to counter-example. For example, suppose we
try
(here, schematically)
something I have tried: Let $c_1, \ldots, c_n$ enumerate the definitions
of all the immemorial
themes involved in narrative. Now suppose we venture a defintion having
the following structure.
\begin{small}
\begin{description}
\item[D$'$] A story $s$ is interesting iff
\begin{description}
\item[1] $\ldots$
\item[] $\vdots$
\item [$k$] $s$ instantiates (inclusive) either $c_1$ or $c_2$ or $\ldots$
or $c_n$.
\item[$k+1$] $\ldots$
\item[] $\vdots$
\item[$p$] $\ldots$
\end{description}
\end{description}
\end{small}
The problem --- and, alas, I have experienced it
time and time again --- is that
along will come a counter-example; in this case, a story which explicitly
fails to satisfy $k$ from D$'$'s definiens
will arrive. For example, an author can write a very interesting story
about a phenomenon like betrayal as cashed out in definition D,
except that instead of clause 4$''$, the following weaker clause
is satisfied.
\begin{small}
\begin{description}
\item[4$'$] there is some action $a$ which $s_r$
performs in the belief that thereby $p$ will {\em not} occur.
\end{description}
\end{small}
\noindent The story here might involve a
courageous, self-sacrificial mother who assures
her addicted son that she will procure drugs to relieve
his misery (as he desires), but intends only to confront the
pusher and put an end to his destructive dealings.
Ironically, clearly some of the interestingness in this
story will derive precisely
from the fact that the mother is not betraying her son. On the
contrary, she plans to save him and others.
In short, devising accounts like $D'$ seems to be to fight a battle that
can never be won; good narrative cannot be bottled.
At this point, I suspect that many readers
are chomping at the bit, raring
to tear into my position with additional objections.
Let's see if I can't anticipate and disarm them
now.
\section{Objections}
\subsection{Objection 1}
``Look, Bringsjord, you must have gone wrong somewhere! Stories
are just strings over some finite alphabet. In your case, given
the stories you have put on display above, the alphabet in question is
\{ {\tt Aa, Bb, Cc, $\ldots$, :, !, ;, $\ldots$}\}, that is, basically
the characters I see before me on my computer keyboard. Let's denote this
alphabet by `$E$.' Elementary string theory tells us that though
$E^\ast$, the set of all
strings that can be built from $E$, is infinite,
it's {\em countably} infinite, and that therefore there
is a program $P$ which enumerates $E^\ast$. ($P$, for example, can
resort to lexicographic ordering.) From this it follows that your
$\cal S$, the set of all stories, is itself countably infinite. (If
we allow, as no doubt we must, all natural languages to be included ---
French, Chinese, and even Norwegian --- the situation doesn't change:
the union of a finite number of countably infinite sets is still
just countably infinite.) So what's the problem? You say that your
students are able to decide $\cal S$$^I$? Fine. Then here's what we
do to enumerate $\cal S$$^I$: Start $P$ in motion, and for each item $S$
generated by this program, call your students to pass verdict on
whether or not $S$ is interesting. This composite program ---
call it $P'$: $P$ working
in conjunction with your students --- enumerates $\cal S$$^I$. So
sooner or later, $P'$ will manage to write {\em King Lear}, {\em War
and Peace}, and even more recent belletristic narrative like that
produced in the United States by Mark Helprin."
There is good reason to think that even
if $\cal S$ is in some sense typographic, it needn't be countably
infinite. Is $\cal A$, the set of all {\tt A}s, countable? (You might
at this point want to return to Figure 1.) If not, then simply imagine
a story associated with every element within $\cal A$; this provides
an immediate refutation of Objection 1. For a parallel route to the same
result, think of a story about $\pi$, a story about $\sqrt{2}$, indeed
a story for every real number!
On the other hand, stories,
in the real world, are often
neither strings nor, more generally,
typographic. After all, authors often think about, expand, refine, ...
stories without considering anything
typographic whatsoever. They may ``watch" stories
play out before their mind's eye, for example. In fact, it seems
plausible to say
that strings (and the like) can be used to {\em represent} stories,
as opposed to
saying that the
relevant strings, strictly speaking, {\em are} stories.\footnote{Someone
might at this point complain that this lattitudinarian view of stories
implies that they are not the sort of well-defined
things that are in the Arithmetic Hierarchy. This complaint can't
be on the right track, for if it were, then even the concepts
involved in standard, well-oiled computational work would have to be
said to fall outside of AH, which would in turn cut an
unacceptable chasm between
the theory of computation and computation itself. For example,
a good chess move, a sensible medical test to be conducted given the
presentation of certain symptoms, an expert judgement about where
to drill for oil given certain evidence, and so on --- the assumption
is always that these concepts, each of which is at the core of
concrete work, are ultimately in AH, even though it seems well nigh
impossible to express them in terms of quantifiers over computable
predicates.}
\subsection{Objection 2}
``Ah! You concede then that you have a decision
procedure for $\cal S$$^I$. But uncountably infinite sets like {\bf R},
the reals, are {\em not}
decidable!"
This objection is anemic (though I have had it earnestly
expressed to me). And the reason it
is, of course, is that I need only maintain that $\cal S$$^I$ is
{\em effectively} decidable, not that there is some program (or Turing
Machine, etc.)~that can decide this set. (CT is the customary
justification given for identifying effective decidability with formal
decidability, but of course one can hardly invoke CT in the present
context without falling prey to a {\em petitio}.)
Though Objection 2 is misguided, it does suggest an interesting
parallel for Arg$_3$:
\begin{center}
\begin{small}
\begin{tabular}{llp{8cm}l}
\multicolumn{4}{c}{\rule [-3mm]{0mm}{7mm}\bf Arg$_3'$}\\
& (9$'$) & If {\bf R} $\in \Sigma_1$ (or {\bf R}
$\in \Sigma_0$),
then there exists a
procedure $P$ which
adapts programs for deciding members of {\bf R} so as to
yield programs
for enumerating members of {\bf R}. &\\
& (10$'$) & There's no procedure $P$ which adapts programs for deciding
members of {\bf R} so as to yield programs for
enumerating members of {\bf R}.\\
.$^\cdot$. & (11$'$) & {\bf R} $\not\in \Sigma_1$
(or {\bf R}
$\not\in \Sigma_0$). & 10, 11\\
& (12$'$) & {\bf R} $\in$ AH. &\\
.$^\cdot$. & (13$'$) & {\bf R} $\in \Pi_1$ (or above in the AH). & disj syll\\
& (14$'$) & {\bf R} is effectively decidable. &\\
.$^\cdot$. & (15$'$) & CT is false. & {\em reductio}\\
\end{tabular}
\end{small}
\end{center}
As we know by now, premise (9$'$) is
an instantiation of a simple theorem
of elementary computability theory; (11$'$) and
(13$'$) are simply intermediate conclusions; (15) does indeed follow from
(13$'$)
and (14$'$), since these two propositions counter-example CT's ``only if" part;
and the other two inferences are unassailable. Everything boils down to (10$'$)
and
(14$'$). But we know that in the case of the
reals, (11$'$)
is true (and, of course, so is (10$'$)), but
we don't need it), and the technique of getting {\bf R} from
{\bf N} (the natural numbers) via (e.g.)~
(e.g.)~Dedekind cuts constitutes a proof of (12$'$). Of course, it's doubtful
that {\bf R} or a
subset thereof is effectively decidable. Such is not the case, as I've
explained, with $\cal S$$^I$.
\subsection{Objection 3}
``I now see your error, Bringsjord: premise (12) in Arg$_3$.
If $\cal S$$^I$ is to be in AH, then your key predicate --- `Interesting';
denote it by `I' ---
must be a bivalent one. (More precisely, $I$ must be isomorphic to
a predicate that is built {\em via} quantification out of the totally
computable bivalent predicates of $\Sigma_0$.) But a moment's reflection
reveals that $I$ {\em isn't} bivalent: different people have radically
different opinions about whether certain fixed stories are interesting!
Clearly, though Jones and Smith may share the same language, and may thus
be able to fully understand ``Shopping," ``Hunger," ``Betrayal," {\em King
Lear}, and {\em War and Peace}, their judgements may differ.
``Shopping" might be downright thrilling to an AInik interested in
determining how, upon reading such a story, humans know instantly that
the pronoun `He' refers to Jack."\footnote{This intelligent objection
is essentially
due to Michael McMenamin \cite{mcmenamin}, though a number of
thinkers have conveyed its gist to me.}
It is important to realize that I am talking about stories {\em qua}
stories; stories as narrative. Hence a better way to focus the
present objection is to note that
Jones
may find {\em Kind Lear} to be genuine
drama, but monstrously boring drama
(because, he says, King Lear, is but a lunatic), while Smith is
transfixed.
It's undeniable that differences of opinion like those existing between
Jones and Smith are common. But this fact
is not a threat to my argument. First, note that such differences
are present in {\em all} domains, not just in the domain of narrative.
Wittgenstein, remember, teased much out of a clash between someone who
says that $2+2=4$ and someone who flatly denies it --- so even the arithmetical
realm, if Objection 3 goes through, would lack bivalent properties,
and if anything is suffused with bivalence, it's arithmetic.
Moreover, there is nothing to prevent
me from stipulating that these agents come decked out with some
fixed ``value system" --- for judging stories. In fact, let me heretofore
insist that $I$ be read as not just interesting $simpliciter$, but
interesting given (what must surely be one of the world's
most refined systems for gauging
stories) the knowledge and ability of none other than Umberto Eco.\footnote{Those
unfamiliar with Eco's non-fiction
work, might start with his surprising
reasons for finding
Ian Fleming's 007 (James Bond) series to be very interesting; see ``Chapter Six:~Narrative
Structures in Fleming," in \cite{eco.role}.}
Our
new predicate, then, can be $I_{\mbox{{\tiny UE}}}$.
\subsection{Objection 4}
``At this start of this paper you affirmed Mendelson's
characterization of `algorithm.' Let me remind you that according
to that characterization, `An algorithm does not reaquire ingenuity.'
Are you not now bestowing
remarkable ingenuity upon the readers/judges you have in mind?"
Recall that
in order to parse `effectively computable,' as we have noted, it's
necessary to invoke the generic
concept of an agent, either Turing's ``computist" or
Post's ``worker." The agent in question,
as none other than Elliot Mendelon reminded us nearly
forty years ago \cite{mendelson.first},
needn't be a {\em human} agent, because, following
the mantra at the heart of computability theory, we impose no practical
restrictions on the length of calculations
and computations. It follows immediately that the agents I have in
mind have enough raw time and energy to process the longest and most
complex contenders in $\cal S$. Furthermore,
if we are going to seriously entertain CT, we must,
all of us, allow the agents in question to have
certain knowledge and ability, for example the knowledge and
ability required to grasp the concepts of number, symbol, change,
movement, instruction, and so on. The agents I have in mind are outfitted
so as to be able to grasp stories, and the constitutents of stories.
And in
deploying $I$, and in moving to $I_{\mbox{{\tiny UE}}}$, I assume {\em less}
on the part of agents (workers, computists, etc.) than what even defenders
of CT through the years have assumed. This is so because such thinkers
freely ascribe to the agents in question the knowledge and ability
required to
carry out sophisticated proofs --- even proofs which cannot be formalized
in first-order logic. The agents capable of deciding $\cal S$$^I$ need
only read the story (and, for good measure, read it $n$ subsequent times ---
something mathematicians
routinely do in order to grasp proofs), and render their decision.
\subsection{Objection 5}
``Yes, but what your computists do is not decomposable into smaller,
purely
mechanical steps, which is the hallmark of an algorithm. They are
supposed to read a story (and, if I understand you, perhaps read it again
some finite number of times), and then, just like that, render a
judgment. This is more like magic than mechanism."
This is objection is a complete non-starter. In order to see this,
let's prove, in a thoroughly traditional manner, that a certain well-defined
problem is effectively solvable.
Recall that all Turing Machines
can be recast as flow diagrams (cf.~\cite{boolos.jeffrey}).
Next, note that any TM
represented by a flow diagram having as part the fragment shown in
Figure 2 would be a non-halting TM (because if started
in state 1 with its read/write
head scanning the leftmost 1 in a block of 1s --- and we
can assume the alphabet in question to
be a binary one consisting of \{0,1\} --- it will loop forever in this fragment. Let $M$ be a fixed
TM specified for computist Smith in flow diagram form, and let this
diagram contain the fragment of Figure 2. Suppose that Brown looks
for a minute at the diagram, sees the relevant fragment, and declares:
``Nonhalter!" In doing this, Brown assuredly decides $M$, and his
performance is effective. And yet what's the difference between what
Brown does and what my ``Eco-ish" agents do? The
activity involved is decomposable in both cases.
There are innumerable
``subterranean" cognitive
processes going on beneath Brown's activity, but they are beside the point:
that we don't (or perhaps can't) put them on display does not tell
against the effectiveness in question. The fact is that Brown
simply looks at the diagram, finds the relevant fragment,
assimilates, and returns a verdict.\footnote{My example is
perfectly consistent with the fact that the set of TMs, with
respect to whether or not they halt, is neither Turing-decidable
nor effectively decidable.}
The same is true of my
agents in the case of stories.
\begin{figure}
\centerline{\psfig{figure=/dept/ppcs/SUPER/CT/sound.procedure.eps,height=1in}}
\caption{A Flow-Diagram Fragment That Entails Non-Halting}
\end{figure}
Before turning to the next objection,
let me point out that the predicates $I$ and $I_{\mbox{{\tiny UE}}}$
really aren't exotic, despite appearances to the contrary.
All those who try to harness the concepts of theoretical
computer science (concepts forming a superset of the formal ones
canvassed in this paper)
in order to get things done end up working with predicates {\em at
least} as murky as these two. A good example is to be found in
the seminal work of John Pollock, which is based on the harnessing
of theoretical computer science (including AH)
so as to explicate and
implement concepts like warrant, defeasibility, {\em prima facie}
plausibility, and so on.\footnote{Here is one example (from \cite{pollock.cc}):
Pollock's OSCAR
system is designed so as to constantly update that which
it believes in response to the rise and fall of arguments given in support
of candidate beliefs. What constitutes correct reasoning in such a scheme?
Pollock notes that because a TM with an ordinary program canŐt decide
theorems in first-order
logic (the
set of such theorems isn't
Turing-decidable), answering this question is quite tricky.
He ingeniously turns to
super-computation for help: the basic idea is that OSCAR's reasoning is
correct when it generates successive sets of beliefs that approach the ideal
epistemic situation in the limit. This idea involves AH, as Pollock explains.}
\section{My Arg$_3$ in Context:~Other Attacks on Church's Thesis}
Over the past six decades, the possibility of CT's falsity
has not only been raised,\footnote{Boolos
and Jeffrey, for example, in their classic textbook
{\em Computability and Logic} \cite{boolos.jeffrey}, provide a sustained
discussion of CT --- and take pains to leave the reader with the impression
that CT can be overthrown.}
but CT has been subjected to
a number of attacks. While I
obviously don't have the book-long
space it would take to treat each and every attack,
I think it's possible to provide a provisional analysis
that is somewhat informative, and serves
to situate the attack on CT I have articulated
above. What this analysis shows, I think, is that
Arg$_3$ is the best attack going.
Following R.J.~Nelson, I partition attacks on CT
into three categories:
\begin{small}
\begin{description}
\item[CAT1] Arguments against the arguments for CT;
\item[CAT2] Arguments against CT itself; and
\item[CAT3] Arguments against doctrines (e.g., the computational
conception of mind) which are said to presuppose CT.
\end{description}
\end{small}
Consider category CAT3 first. Perhaps the most promising
argument in this category runs
as follows. Assume for the sake of argument that all human
cognition consists in the execution of effective processes (in brains,
perhaps). It would then follow by CT that such processes are
Turing-computable, i.e., that
computationalism is true. However, if computationalism is false,
while there remains incontrovertible evidence that human cognition
consists in the execution of effective processes, CT is overthrown.
Attacks of this sort strike me as decidedly unpromising. For starters,
many people aren't persuaded that computationalism is false (despite
the many careful arguments I myself have given; cf.~\cite{irr},
\cite{wrccb}).
Secondly, this argument
silently presupposes some sort of physicalism, because the evidence
for the effectiveness of cognition no doubt derives from observation
and study of processes in the central nervous system. Thirdly, it
is certainly an open question as to whether the processes involved
{\em are} effective. At present, we just don't know enough about the
brain, physics, and computability theory (and the interrelationships
among these things) to conclude that cognition rests completely on
effective processes. (To be a bit more specific, perhaps cognition
arises from physical processes which are irreducibly analog and chaotic,
a type of process mathematized in the final section of this very
paper.)
What about CAT1? Well, my refutation of Mendelson falls within
it --- and yet who would claim that what I have revealed about
Mendelson's reasoning constitutes, by itself, a serious attack on CT?
The same fundamental question derails even the work of those who
intend to attack CT by attacking the time-honored rationales for it.
For example, William Thomas \cite{thomas.ct}
seeks to capitalize on the fact (and it {\em is} a fact, that
much is uncontroversial) that the main rationale behind CT
involves empirical induction --- a form of reasoning that has
little standing in mathematics.
Unfortunately, Thomas' observations don't
threaten CT in the least, as is easy to see.
Most of us believe, {\em unshakably} believe,
that the universe is more than 3 seconds
old --- but what mathematical rationale have we for this belief?
As Russell pointed out, mathematics is quite consistent with the
proposition that the universe popped into existence 3 seconds ago,
replete not only with stars, but with light here on Earth from
stars, and also with minds whose memories include those we have.
More generally, of course,
from the fact that $p$
doesn't follow deductively from a set of propositions $\Gamma$,
it hardly follows that $p$ is false; it doesn't even follow that $p$
is the slightest bit implausible.
We are left, then, with CAT2 --- the category into which my own attack
on CT falls. How does Arg$_3$ compare with other attacks in this category?
To support the view that my own
attack is superior, let us consider a notorious argument from four
decades back, one due to L\'{a}szl\'{o}
Kalm\'{a}r
\cite{kalmar} (and rejected by none other than
Elliott Mendelson \cite{mendelson.first}),
and the only other modern attack on CT that I know of, one given
by Carol Cleland \cite{cleland.ct}, \cite{cleland.ct2}.\footnote{Perhaps
I should mention here
something that students of CT and its history will
be familiar with, viz., {\em given an intuitionistic
interpretation of `effectively computable function,'} CT can be disproved.
The basic idea is to capitalize on the fact that any subset of {\bf N}
is intuitionistically enumerable, while many such sets aren't
effectively enumerable. (A succinct presentation of the disproof can be found
on page 592 of \cite{nelson.ct}.) The main problem with such attacks on
Church's Thesis, of course, is that they presuppose (certain axioms of ---
see \cite{kreisel.ml}, \cite{kreisel.ct},
e.g.)~intuitionistic logic, which most reject.}
\subsection{Kalm\'{a}r's Argument Against CT}
Here's how Kalm\'{a}r's argument runs. First, he draws our
attention to a function $g$
that isn't Turing-computable, given that $f$ is:\footnote{The original
proof can be found on page 741 of \cite{kleene.genrec}.}
\begin{small}
\begin{center}
\[ g(x) = \mu_y(f(x, y) = 0) = \left\{
\begin{array}{l}
\mbox{the least $y$ such that $f(x, y) = 0$ if $y$ exists}\\
0 \mbox{ if there is no such $y$}\\
\end{array}
\right. \]
\end{center}
\end{small}
\noindent Kalm\'{a}r proceeds to point out that for any $n \in$ {\bf N}
for which a natural number $y$ with $f(n, y) = 0$ exists,
``an obvious method for the calculation of the least such $y$ $\ldots$
can be given," namely, calculate in succession the values $f(n, 0),
f(n, 1), f(n, 2), \ldots$ (which, by hypothesis, is something
a computist or TM can do) until we hit a natural number $m$ such that
$f(n, m) = 0$, and set $y = m$.
\begin{small}
\begin{quote}
On the other hand, for any natural number $n$ for which we can prove,
not in the frame of some fixed postulate system but by means of arbitrary ---
of course, correct --- arguments that no natural number $y$ with $f(n, y) =
0$ exists, we have also a method to calculate the value $g(n)$ in a finite
number of steps: prove that no natural number $y$ with $f(n, y)= 0$ exists,
which requires in any case but a finite number of steps, and gives
immediately the value $g(n) = 0$. (\cite{kalmar}, p.~74)
\end{quote}
\end{small}
\noindent Kalm\'{a}r goes on to argue as follows.
The definition of $g$ itself
implies the {\em tertium non datur}, and from
it and CT
we can infer the existence of a natural number $p$ which is such that
\begin{small}
\begin{description}
\item[(i)] there is no natural number $y$ such that $f(p, y)= 0$; and
\item[(ii)] this cannot be proved by any correct means.
\end{description}
\end{small}
\noindent Kalm\'{a}r claims that (i) and (ii) are very strange, and
that therefore CT is at the very least implausible.
This argument is interesting, but really quite hopeless, as a number
of thinkers have indicated. For example, as
Mendelson \cite{mendelson.first} (see also Moschovakis' \cite{moschovakis}
review of both Kalm\'{a}r's paper and Mendelson's reaction)
points out,
Kalm\'{a}r's notion of
`correct proof,' for all Kalm\'{a}r tells us, may fail to be effective, since
this proof is outside the standard logical system (set theory formalized
in first-order logic). This is surely historically
fascinating, since --- as we have seen --- it would be
Mendelson who, nearly thirty years later, in another
defense of CT (the one we examined earlier), would offer a proof of
the `only if' direction of this thesis ---
a proof that he assumes to be correct but
one that he admits to be beyond ZF. Mendelson's proof, however,
at least has the virtue of having been
presented.
The root of Kalm\'{a}r's
problem is that his proofs, on the other hand, are wholly
hypothetical: we don't have a single one to ponder.
And things get even worse for Kalm\'{a}r (as Nelson \cite{nelson.ct}
has pointed out), because even absent the proofs in question,
we know enough about them to know that they would vary for
each argument to $g$ that necessitates them, which would mean that
Kalm\'{a}r has failed to find a {\em uniform} procedure, a property
usually taken to be a necessary condition for a procedure to qualify
as
effective.
Though Kalm\'{a}r does anticipate the problem of lack of uniformity,\footnote{He
says:
\begin{quote}
By the way, [the assumption that the procedure in question] must be
uniform seems to have no objective meaning. For a school-boy, the method
for the solution of the diverse arithmetical problems he has to solve does
not seem uniform until he learns to solve equations; and several methods in
algebra, geometry and theory of numbers which are now regarded group-theoretic
methods were not consider as uniform before group-theory has (sic)
been discovered. (\cite{kalmar}, 73)
\end{quote}}
and though I personally happen to side with him on this issue, it is
clear that his argument against CT falls flat: If Kalm\'{a}r's argument is to
succeed, (ii) can be supplanted with
\begin{small}
\begin{description}
\item[(ii$'$)] this cannot be proved by any effective means.
\end{description}
\end{small}
\noindent But then how can the argument be deductively valid?
It is not, at bottom, a {\em reductio}, since (i) and (ii$'$) surely
are not absurd, and this is the only form a compelling version of the
argument could at core be.
Kalm\'{a}r himself, as we have
noted, confesses that his argument is designed only to
show that CT is implausible, but this conclusion goes through only
if (i) and (ii$'$), if not absurd, are at least counter-intuitive.
But are they? For some, perhaps; for others, definitely not.
My own take on Kalm\'{a}r's argument is that it can be rather easily
{\em shown} to be impotent {\em via} the machinery
we set out above to analyze Mendelson's this-decade defense
of CT: First, let
$$M^P_1, M^P_2, \ldots, M^P_n, M^P_{n+1}, \ldots$$
enumerate all the Turing Machine/Program pairs that figured in our
earlier discussion.
Now substitute for Kalm\'{a}r's $g$ the following
function (which is just a trivial
variation on the predicate $H(P, i)$ from above).
\begin{small}
\begin{center}
\[ h(M_i) = \left\{
\begin{array}{ll}
1 & \mbox{ if $M_i$ halts}\\
0 & \mbox{ if $M_i$ doesn't halt}\\
\end{array}
\right. \]
\end{center}
\end{small}
\noindent Recall that if a TM halts, simulating this machine will eventually
reveal this fact. (This was why, though $H \not\in \Sigma_0$, we
could place $H$ in $\Sigma_1$.)
This allows us to produce an exact parallel to
Kalm\'{a}r's reasoning: Start with $M^P_1$; proceed to simulate this
machine. Assuming it halts, return 1, and move on to $M^P_2$, and do
the same for it; then move to $M^P_3$,
and so on. While this process is running, stand ready to proof
``not in the frame of some fixed postulate system but by means of arbitrary ---
of course, correct --- arguments" that the machine $M^P_i$ fails to halt,
in which case 0 is returned. The parody continues as follows. Given CT,
and the law of the excluded middle (which the definition of the function
$h$ presupposes), we infer two implausible propositions --- propositions
so implausible that CT is itself cast into doubt. They are:
\begin{small}
\begin{description}
\item[(i$_h$)] there exists an $M^P_k$ such that $h(M_k) = 0$; and
\item[(ii$'_h$)] this cannot be proved by any effectively
computable means.
\end{description}
\end{small}
\noindent This is a parody, of course, because both of these propositions are
fully expected and welcomed by all those who both affirm CT and
have at least some familiarity with the formalisms involved.
Now, what about {\em my} case against
CT? Well, it would seem to be free of the defects
that plague Kalm\'{a}r's argument. First, my narrational case is
deductive, as Arg$_3$ makes plain. Second, the process of reading
(and possibly rereading a finite number of times) a story, assimilating
it, and judging whether or not it's interesting on a fixed evaluation
scheme --- this process is transparently effective. (Indeed, related
processes are routinely requested on standardized tests containing
reading comprehension problems, where stories are read, perhaps reread,
and judged to express one from among $n$ ``main ideas.") Third,
the process I'm exploiting would seem to be uniform.\footnote{No
doubt test designers are correct that a uniform procedure needs to
be followed in order to excel in their reading comprehension sections.
So why wouldn't the process at the heart of Arg$_3$ be uniform as
well?}
\subsection{Cleland's Doubts About CT}
Cleland \cite{cleland.ct}, \cite{cleland.ct2}
discusses three variants on our CT:
\begin{small}
\begin{description}
\item[CT$_1$] Every effectively computable number-theoretic function is
Turing-computable.
\item[CT$_2$] Every effectively computable function is
Turing-computable.
\item[CT$_3$] Every effective procedure is
Turing-computable.
\end{description}
\end{small}
\noindent Before evaluating Cleland's
arguments against this trio, some exegesis is in order.
First, each of these three theses is a conditional,
whereas
our CT is a {\em bi}conditional. There should be no question that
the biconditional is more accurate, given not only Mendelson's
authoritative affirmation of the biconditional form, but also
given that Church himself
originally refers to his
thesis as a {\em definition} of ``effectively calculable function"
in terms of ``recursive function" \cite{church}.\footnote{On
the other hand, Church then immediately proceeds to argue
for his ``definition," and the reader sees that Church is
without question urging his readers to affirm a {\em thesis}.} However,
since I have
happily conceded the `if' direction in CT, there is no reason to
worry about this aspect of Cleland's framework. The second
point is this: by `number-theoretic'
function Cleland simply means what we have hitherto called a function,
that is, a mapping from {\bf N} to {\bf N}. We thus now understand
function {\em simpliciter}, as for example as it's used in CT$_2$,
to allow functions from the reals to reals.\footnote{It will not
be necessary to present here the formal extension of computability
with number-theoretic
functions to computability with functions over the reals. (For the
formal work, see, e.g.,
\cite{grzegorczyk.55} and \cite{grzegorczyk.57}.)}
There is of course no denying that Church and Turing failed to
advocate CT$_2$, but CT$_1$ is certainly the ``left-to-right" direction
of our CT.
Now, what does Cleland say against CT$_1$--CT$_3$? She claims, first,
that CT$_3$ can be disproved; the argument is simply this. One
type of effective procedure coincides
with what Cleland calls ``mundane procedures," which are ``ordinary,
everyday procedures such as recipes for making Hollandaise sauce and
methods for starting camp fires; they are methods for manipulating physical
things such as eggs and pieces of wood" (\cite{cleland.ct2}, 11).
Turing Machine procedures, on the other hand, are ``methods for
`manipulating' abstract symbols" (\cite{cleland.ct2}, 11). Since
mundane procedures have ``causal consequences," and TMs ({\em qua}
mathematical objects) don't, it
follows straightaway that mundane procedures aren't Turing-computable,
that is, $\neg$CT$_3$.
Cleland's reasoning, when formalized, is valid; no question
about that. The problem is that CT$_3$ (at least
on her reading) has next to nothing to
do with those
propositions placed in
the literature under the
title ``Church's Thesis"! CT$_3$ is a variant that no one
has ever taken seriously. It may {\em seem} to some that CT$_3$
has been taken seriously, but this is only because one construal of it,
a construal at odds with Cleland's, has in fact been recognized.
On this construal, that a procedure is Turing-computable can be certified
by either a relevant design (e.g., a TM flow-graph for making
Hollandaise sauce, which
is easy to come by), or by a relevant artifact (e.g., an artificial
agent capable of making Hollandaise sauce, which again is easy to come
by). At any rate, I'm quite willing to concede that CT$_3$, on
Cleland's idiosyncratic reading, is provably false.
(Note
that we have known for decades that even CT$_1$, on an
intuitionistic (and hence idiosyncratic)
reading of ``effectively computable function,"
is provably false. See note 24.) It's worth noting that Cleland
herself has sympathy for those who hold that her reading of CT$_3$
is not a {\em bona fide} version of
Church's Thesis (\cite{cleland.ct2}, 10).
What then, about
CT$_2$ and CT$_1$?
Here Cleland no longer claims to have a refutation in hand; she aims only
at casting doubt on these two theses. This doubt is supposed to derive
from reflection upon what she calls ``genuinely continuous devices"
(\cite{cleland.ct2}, 18), which are objects said to ``mirror"
Turing-uncomputable functions (\cite{cleland.ct2}, 16-17).
An object is said to {\bf mirror} a function iff (a)
it
includes a set of distinct objects which are in one-to-one
correspondence with the numbers in the field of the function,
and (b) the object pairs each and every object corresponding to a number
in the domain of the function with an object corresponding to the
appropriate number in the range of the function.
Cleland
takes pains to argue, in intuitive fashion, that there are objects
which mirror Turing-uncomputable functions (e.g., an object
moving through a 2-dimensional Newtonian universe).
She seems
completely unaware
of the fact that such objects {\em provably} exist --- in the form, for example,
of analog chaotic neural nets
and, generally, analog chaotic
dynamical systems \cite{siegelmann.sontag}, \cite{siegelmann}.
(These objects are known to exist in the mathematical sense. Whether
they exist in the corporeal world is another question, one everyone ---
including Cleland --- admits
to be open.) We will be able to see Cleland's fundamental error (and,
indeed, the fundamental error of anyone who attacks CT by taking her
general route) if we pause for a moment to get clear about the devices
in question. Accordingly, I'll present here an
analog dynamical system via the ``analog shift map," which is remarkably
easy to explain.
First let's get clear on the general framework for the
``shift map." Let $A$ be a finite alphabet. A {\bf dotted sequence}
over $A$ is a sequence of characters from $A^\ast$ wherein one dot
appears. For example, if $A$ is the set of digits from 0 to 9, then
3.14 is a dotted sequence over $A$. Set
$A^\cdot$ to the set of all dotted sequences over
$A$. Dotted sequences can be finite,
one-way infinite (as in
the decimal expansion of
$\pi$), or bi-infinite. Now, let $k \in$ {\bf N};
then the shift map
$$S^k : A^\cdot \rightarrow A^\cdot : (a)_i \rightarrow (a)_{i+k}$$
shifts the dot $k$ places, negative values for a shift to the left,
positive ones a shift to the right. (For example, if $(a)_i$ is
3.14159, then with $k = 2$, $S^2(3.14159) = 314.159.$) Analog
shift is then defined as the process of first replacing a dotted
substring with another dotted substring of equal length according
to a function $g : A^\cdot \rightarrow
A^\cdot$. This new sequence is then shifted an integer
number of places left or right as directed by a function
$f : A^\cdot \rightarrow$ {\bf Z}. Formally,
the analog shift is the map
$$\Phi : a \rightarrow S^{f(a)}(a \oplus g(a)),$$
where $\oplus$ replaces the elements of the first dotted
sequence with the corresponding element of the second dotted sequence
if that element is in the second sequence, or leaves it untouched
otherwise. Formally:
\begin{small}
\begin{center}
\[ (a \oplus g)_i = \left\{
\begin{array}{ll}
g_i & \mbox{ if $g_i \in A$}\\
a_i & \mbox{ if $g_i$ is the empty element}\\
\end{array}
\right. \]
\end{center}
\end{small}
\noindent Both $f$ and $g$ have ``finite domains of dependence" (DoDs),
which
is to say that they depend only on a finite dotted substring of the
sequence on which they act. The domain of {\em effect} (DoE) of $g$, however,
may be finite, one-way infinite, or bi-infinite. Here is an example from
\cite{siegelmann} (547) which will make things clear, and allow
us to see the fatal flaw in Cleland's rationale for doubting CT$_2$ and
CT$_1$. Assume that the analog shift is defined by (where
$\pi^2$ is the left-infinite string $\ldots 51413$ in base 2)
\begin{small}
\begin{center}
\begin{tabular}{|ccc|}
\hline
DoD & $f$ & $g$\\
\hline
0.0 & 1 & $\pi^2$\\
0.1 & 1 & .10\\
1.0 & 0 & 1.0\\
1.1 & 1 & .0\\
\hline
\end{tabular}
\end{center}
\end{small}
\noindent and that we have a starting sequence of $u = 000001.10110$;
then the following
evolution ensues:
$$000001.00110$$
$$0000010.0110$$
$$\pi^2.0110$$
$$\pi^20.100$$
$$\pi^20.100$$
$$\pi^201.00$$
$$\pi^21.00$$
$$\pi^201.00$$
At this point the DoD is 1.0 and hence no changes occur; this is a {\bf
fixed point}. Only the evolution from an initial dotted sequence to fixed
point counts. In this case the input-output map is defined as the
transformation of the initial sequence to the final subsequence to the right
of the dot. (Hence in our example $u$ as input leads to 00.) The class
of functions determined by the analog shift includes as a proper subset
the class of Turing-computable functions. (The proof is
straightforward: \cite{siegelmann}.) Moreover, the analog shift map
is a mathematical model of idealized physical phenomena (e.g., the
motion of a billiard ball bouncing among parabolic mirrors). From
this it follows that we provably have
found exactly what Cleland desires, that is,
a genuinely continuous device that mirrors a Turing-uncomputable function.
So, if Cleland can establish that
\begin{small}
\begin{description}
\item[(16)] If $x$ mirrors a function, then $x$ computes it.
\end{description}
\end{small}
\noindent she will have overthrown both CT$_2$ and CT$_1$. Unfortunately,
given our analysis of the analog shift map, we can see that Cleland
doesn't have a chance; here is how the reasoning runs. Recall, first,
the orthodox meaning of
`effectively computable function,' with which we started this paper:
a function $f$ is effectively computable provided that,
an agent having essentially our powers, a computist (or
worker), can compute $f$ by following an algorithm. So let's suppose that
you are to be the computist in the case of the analog shift map. There
is nothing impenetrable about the simple math involved; we'll assume that
you have assimilated it just fine. So now we would like you to compute
the function $\Phi$ as defined in our example involving $\pi$. To make
your job as easy as possible, we will guarantee your immortality, and
we will supply you with an endless source of pencils and paper (which is
to say, we are ``idealizing" you). Now, please set to work, if you will;
we will wait and observe your progress $\ldots$
What happened? Why did you stop? Of course, you
stopped because you hit a brick wall:
it's rather challenging to write down and manipulate (or imagine
and manipulate mentally) strings like $\pi$ in base 2! (Note that the
special case where the DoE of $g$ is finite in the analog shift map
generates a class of functions identical to the class of Turing-computable
ones.) Yet this is precisely what needs to be done in order to
attack CT$_2$ and CT$_1$ in the way Cleland prescribes.
Cleland sees the informal version of the problem,
for
she writes:
\begin{small}
\begin{quote}
Is there a difference between mirroring a function and
computing a function? From an intuitive standpoint, it seems that there is.
Surely, falling rocks don't compute functions, even supposing that they
mirror them. That is to say, there seems to be a difference between a
mere representation of a function, no matter how detailed, and the computation
of a function. [Q:] But what could this difference amount to?
(\cite{cleland.ct2}, 20)
\end{quote}
\end{small}
\noindent She then goes on to venture an answer to this question:
\begin{small}
\begin{quote}
A natural
suggestion is that computation requires not only the mirroring of a function
but, also, the {\em following} of a procedure; falling rocks don't compute
functions because they don't follow procedures.
(\cite{cleland.ct2}, 20)
\end{quote}
\end{small}
\noindent Cleland then tries to show that this answer is unacceptable.
The idea is that since
the answer doesn't cut it, she is entitled to conclude that (16) is true,
that is, that
there {\em isn't} a difference between mirroring a function and computing
a function,\footnote{This reasoning is certainly enthymematic (since it hides
a premise to the effect that there are no other answers that can be
given to Q), but I
charitably leave this issue aside.} which then allows the mere
existence of (say) an
idealized billiard ball bouncing among parabolic mirrors to kill off
CT$_2$ and CT$_1$.
What, then, is Cleland's argument for the view that the ``natural suggestion"
fails in response to Q fails? It runs as follows:
\begin{small}
\begin{quote}
Turing machines are frequently construed as {\em purely} mathematical
objects. They are defined in terms of the same kinds of basic entity
(viz., sets, functions, relations and constants) as other mathematical
structures. A Turing machine is said to {\em compute} a number-theoretic
function if a function can be {\em defined} on its mathematical structure
which has the same detailed structure as the number-theoretic function
concerned; there isn't a distinction, in Turing machine theory, between
computing a function and defining a function $\ldots$ If computing a
function presupposes following a procedure, then neither Turing machines
nor falling rocks can be said to compute functions.
\end{quote}
\end{small}
This argument is an enthymeme; its hidden premise is that `compute'
is used univocally
in the relevant theses,
i.e., that `compute'
means the same thing on both the left and right sides of CT, CT$_1$,
and CT$_2$. This premise is false. The locution `$f$ is effectively
computable,' on the orthodox conception
of Church's Thesis, does imply that there is
an idealized
agent capable of {\em following} an algorithm in order to compute $f$.
But it hardly follows
from this that when `compute' is used in the locution `$f$ is
Turing-computable' (or in the related locution `TM $M$ computes $f$'), the
term `compute'
must have the same meaning as it does in connection with idealized
agents. Certainly anyone interested in CT, and in defending it, would
hasten to remind Cleland that the term `compute' means one thing when
embedded within CT's left side, and another thing when embedded within
CT's right side.\footnote{Unexceptionable parallels abound: We can
say `My friend told me that Burlington is a nice city,' and we can
say `My CD-ROM travel program told me that Burlington is a nice city,'
but we needn't accept the view that `told me' means the same in both
utterances.}
Having said this, however, and having implicitly
conceded the core mathematical point (viz.,
that at least some definitions of TMs and Turing-computability
deploy `compute' in the absence of the concept of ``following"\footnote{Consider,
e.g., one I myself use in teaching mathematical logic:
A {\bf Turing machine} is a quadruple $(S, \Sigma, f, s)$ where
\begin{enumerate}
\item $S$ is a finite set of {\bf states};
\item $\Sigma$ is an alphabet containing the black symbol --, but
not containing the symbols $\Leftarrow$ (``go left") and
$\Rightarrow$ (``go right").
\item $s \in S$ is the {\bf initial state};
\item $f : S \times \Sigma \longrightarrow (\Sigma \cup
\{\Leftarrow, \Rightarrow\}) \times S$ (the {\bf transition function}).
\end{enumerate}}), I should probably draw Cleland's attention to
the formal approach we took
above,
where in order to characterize information-processing beyond the
Turing Limit, we distinguished between a TM as a type of architecture,
and a program which this architecture {\em follows} in order to compute.
This is why we spoke of TM-program pairs.
Cleland never intended to literally refute CT$_1$ and CT$_2$. (As we
have seen, she did intend to refute the heterodox CT$_3$, and for the
sake of argument we agreed that here she succeeds.)
But I conclude
that she fails even in her attempt to cast doubt upon these theses,
and that therefore CT is unscathed by her discussion. In contrast,
my own case against
CT targets this thesis with a deductive argument having
no hidden premises and presupposing no
convenient construal of CT. I have laid my cards on the table for
all to see. I'm pretty sure my hand is the best one hitherto revealed, but
as to whether it wins, or merely marks
another chapter in the --- interesting --- story of Church's
Thesis, my readers must judge.
\newpage
\begin{thebibliography}{99}
\bibitem{ashcraft} Ashcraft, M.H.~(1994) {\em Human Memory and Cognition}
(New York, NY:~HarperCollins).
\bibitem{irr} Bringsjord, S.~\& Zenzen, M.~(forthcoming-a) ``Cognition is
Not Computation:
The Argument From Irreversibility," {\em Synthese}.
\bibitem{brutus} Bringsjord, S.~\& Ferrucci, D.~(forthcoming-b) {\em Artificial
Intelligence and Literary Creativity: The State of the Art}
(Hillsdale, NJ:~Lawrence Erlbaum).
\bibitem{digital} Bringsjord, S.~(forthcoming-c) ``Philosophy and
`Super'-Computation," in Moor, J., and Bynum, T., eds., {\em The Digital
Phoenix}, Basil Blackwell.
\bibitem{wrccb} Bringsjord, S.~(1992) {\em What Robots Can and Can't Be}
(Dordrecht, The Netherlands:~Kluwer Academic Publishers).
\bibitem{boolos.jeffrey} Boolos, G.S.~\& Jeffrey, R.C.~(1989)
{\em Computability and Logic 3rd edition} (Cambridge, UK:~Cambridge
University Press).
\bibitem{charniak.intro} Charniak, E.~\& McDermott, D.~(1985)
{\em Introduction to Artificial Intelligence} (Reading, MA:~Addison-Wesley).
\bibitem{church} Church, A.~(1936) ``An Unsolvable Problem of Elementary
Number theory," in Dave, M., ed., {\em The Undecidable} (New York, NY:~Raven
Press), 89-100.
\bibitem{cleland.ct2} Cleland, C.~(1995) ``Effective Procedures and
Computable Functions,"
{\em Minds and Machines} {\bf 5}:~9-23.
\bibitem{cleland.ct} Cleland, C.~(1993) ``Is the Church-Thesis True?"
{\em Minds and Machines} {\bf 3}:~283-312.
\bibitem{davis.weyuker} Davis, M.~\& Weyuker,E.~(1994) {\em Computability,
Complexity, and Languages:
Fundamentals of Theoretical
Computer Science 2nd Edition} (New York, NY: Academic Press).)
\bibitem{dennett.ce} Dennett, D.C.~(1991) {\em Consciousness Explained}
(Boston, MA: Little, Brown).
\bibitem{eco.role} Eco, U.~(1979) {\em The Role of the Reader: Explorations
in the Semiotics of Texts} (Bloomington, IN:~Indiana University Press).
\bibitem{ebb} Ebbinghaus, H.D., Flum, J., Thomas, W.~(1984) {\em Mathematical
Logic} (New York, NY:~Springer-Verlag).
\bibitem{folina} Folina, J.~(1993) ``Commentary on Selmer Bringsjord's
`Church's Thesis, Contra Mendelson, Is Unprovable $\ldots$ And Worse:
it May be False'," Annual Eastern Division APA Meeting, Atlanta, GA,
December 27, 1993.
\bibitem{grzegorczyk.57} Grzegorczyk, A.~(1957) ``On the Definitions
of Computable Real Continuous Functions," {\em Fundamentals of Mathematics}
{\bf 44}:~61-71.
\bibitem{grzegorczyk.55} Grzegorczyk, A.~(1955) ``Computable Functionals,"
{\em Fundamentals of Mathematics} {\bf 42}:~168-202.
\bibitem{hof.knuth} Hofstadter, D.~(1982) ``Metafont, Metamathematics,
and Metaphysics,"
{\em Visible
Language} {\bf 14.4}: 309-338.
\bibitem{kalmar}
Kalm\'{a}r, L.~(1959) ``An Argument Against the Plausibility of
Church's Thesis," in Heyting, A., ed., {\em Constructivity in
Mathematics} (Amsterdam, Holland:~North-Holland), 72-80.
\bibitem{kleene.genrec} Kleene, S.C.~(1936) ``General Recursive Functions
of Natural Numbers," {\em Math.~Annalen} {\bf 112}:~727-742.
\bibitem{kreisel.ct} Kreisel, G.~(1968) ``Church's Thesis:
A Kind of Reducibility Thesis for
Constructive Mathematics," in {\em Intuitionism
and Proof Theory:~Proceedings of a
Summer Conference at Buffalo, N.Y.}, eds.,
Kino, A., Myhill, J., and Vesley, R.E.~(Amsterdam,
Holland:~North-Holland).
\bibitem{kreisel.ml} Kreisel, G.~(1965) ``Mathematical Logic," {\em Lectures
in Modern Mathematics}, ed., Saaty, T.L.~(New York, NY:~John Wiley).
\bibitem{kugel.thinking} Kugel, P.~(1986) ``Thinking May Be More Than
Computing,"
{\em Cognition} {\bf 22}:~137-198.
\bibitem{letraset} (1981) {\em Graphic Art Materials Reference Manual}
(New York, NY:~Letraset).
\bibitem{mcmenamin} McMenamin, M.~``Deciding Uncountable Sets and
Church's Thesis," unpublished manuscript.
\bibitem{tale.spin} Meehan, J.~(1981) ``{\sc tale-spin}," in
Schank, R.~\& Reisbeck, C., eds., {\em Inside Computer Understanding:~Five
Programs Plus Miniatures} (Hillsdale, NJ:~Lawrence Erlbaum Associates),
197-226.
\bibitem{mendelson} Mendelson, E.~(1990)
``Second Thoughts About Church's Thesis and Mathematical Proofs,"
{\em Journal of Philosophy}
{\bf 87.5}:~225-233.
\bibitem{mendelson.first} Mendelson, E.~(1963) ``On Some Recent Criticism
of Church's Thesis," {\em Notre Dame Journal of Formal
Logic} {\bf 4.3}:~201-205.
\bibitem{moschovakis} Moschovakis, Y.~(1968) ``Review of Four Recent
Papers in Church's Thesis," {\em Journal of Symbolic Logic} {\bf 33}:~471-472.
(One of the four papers is:
Kalm\'{a}r, L.~(1959) ``An Argument Against the Plausibility of
Church's Thesis," in Heyting, A., ed., {\em Constructivity in
Mathematics} (Amsterdam, Holland:~North-Holland), 72-80.
\bibitem{nelson.ct} Nelson, R.J.~(1987) ``Church's Thesis and Cognitive
Science," {\em Notre Dame Journal of Formal Logic} {\bf 28.4}:~581-614.
\bibitem{pollock.cc} Pollock, J.~(1995) {\em Cognitive Carpentry: A
Blueprint for How to Build a Person}
(Cambridge, MA:
MIT Press).
\bibitem{post.inaugural} Post, E.L.~(1936) ``Finite Combinatory
Processes -- Formulation 1,"
{\em Journal of Symbolic Logic} {\bf 1.3}:~103-105.
\bibitem{schank.tell} Schank, R.~(1995) {\em Tell Me a Story}
(Evanston, IL:~ Northwestern University Press).
\bibitem{siegelmann} Siegelmann, H.~(1995)
``Computation Beyond the Turing Limit,"
{\em Science} {\bf 268}:~545-548.
\bibitem{siegelmann.sontag} Siegelmann, H.~and Sontag, E.D.~(1994)
``Analog Computation
Via Neural Nets," {\em Theoretical Computer Science}
{\bf 131}:~331-360.
\bibitem{stillings} Stillings, N.A., Weisler, S.E., Chase, C.H.,
Feinstein, M.H., Garfield, J.L.~\& Rissland, E.L.~(1995) {\em Cognitive
Science} (Cambridge, MA:~MIT Press).
\bibitem{thomas.ct} Thomas, W.~(1973) ``Doubts About Some Standard
Arguments for Church's Thesis," in {\em Papers of the Fourth
International Congress for Logic, Methodology, and Philosophy of
Science, Bucharest} (Holland:~D.~Reidel).
\bibitem{trabasso} Trabasso, T.~(1996) ``Review of {\em Knowledge
and Memory:~The Real Story}," Robert S.~Wyer, ed., Lawrence Erlbaum,
1995, {\em Minds \& Machines} {\bf 6}:~ 399-403.
\bibitem{wyer} Wyer, R.S.~(1995) {\em Knowledge and Memory:~The Real
Story} (Hillsdale, NJ:~Lawrence Erlbaum Associates).
\end{thebibliography}
\end{document}