... Thesis¹

<>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).<>

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...[27]²

Unless otherwise noted, all page references are to this paper.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... Turing-computable.³

This is often called the Church-Turing Thesis for obvious reasons.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... algorithm.⁴

In his inaugural writings (independent, by the way, of Turing's), Post [32] spoke of mindless ``workers," humans whose sole job was to slavishly follow explicit, excruciatingly simple instructions. These are ``computists" for Turing.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... theses.⁵

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.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... Thesis."⁶

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" ([27], p. 232).

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... AH.⁷

For a comprehensive discussion of uncomputability, including the Arithmetic Hierarchy, a good text is [11]. I provide a self-contained introduction to the realm of ``super"-computation in [4].

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...:⁸

The reader should satisfy herself that the following procedure does decide G.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... uncontroversial.⁹

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.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... etc.).¹⁰

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.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... response¹¹

Personal communication, December 14, 1993.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... accept.¹²

Incidentally, the reconstruction probably has fatal problems, as Folina [15] points out. After all, is what Mendelson calls a proof here a proof? One common conception -- indeed, probably the 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á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 [15] 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 isn't a proof, then what is it? If it's merely a precise, compelling argument connecting an intuitive notion with a formal one, then it shows something we knew to be true all along.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... left.¹³

From page 592 of [7]. 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?

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... beauty.¹⁴

A search for coverage of this concept in standard texts about cognition -- e.g., [1] and [36] -- turns up nothing whatever.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... acceptable.¹⁵

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 [31] 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 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.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... stories.¹⁶

An insightful review of this book has been written by Tom Trabasso [38].

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... skeptical).¹⁷

Schank has devoted a book to the view that stories are at the very heart of human cognition: [33]. This is probably as good a place as any to point out that Dennett's Consciousness Explained [12] 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.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... BRUTUS:¹⁸

BRUTUS's cognitive anatomy is described in detail in [3].

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... works:¹⁹

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'.

3

s_r agrees with s_d that p ought to occur;

6'

s_d wants that there is some action a which s_r performs in the belief that thereby p will occur.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... stories.²⁰

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.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... Jack."²¹

This intelligent objection is essentially due to Michael McMenamin [25], though a number of thinkers have conveyed its gist to me.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... Eco.²²

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 [13].

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... verdict.²³

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.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... on.²⁴

Here is one example (from [31]): 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.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... raised,²⁵

Boolos and Jeffrey, for example, in their classic textbook Computability and Logic [6], provide a sustained discussion of CT -- and take pains to leave the reader with the impression that CT can be overthrown.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...[9].²⁶

Perhaps I should mention here something that students of CT and its history will be familiar with, viz., 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 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 [30].) The main problem with such attacks on Church's Thesis, of course, is that they presuppose (certain axioms of -- see [22], [21], e.g.) intuitionistic logic, which most reject.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... is:²⁷

The original proof can be found on page 741 of [20].

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... uniformity,²⁸

He says:

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. ([19], 73)

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... uniform.²⁹

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₃ be uniform as well?

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...[8].³⁰

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 thesis.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... reals.³¹

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., [17] and [16].)

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... function,³²

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.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... side.³³

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.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... ``following"³⁴

Consider, e.g., one I myself use in teaching mathematical logic: A Turing machine is a quadruple $(S, \Sigma, f, s)$ where

1.

S is a finite set of states;

2.

$\Sigma$ is an alphabet containing the black symbol -, but not containing the symbols $\Leftarrow$ (``go left") and $\Rightarrow$ (``go right").

3.

$s \in S$ is the initial state;

4.

$f : S \times \Sigma \longrightarrow (\Sigma \cup \{\Leftarrow, \Rightarrow\}) \times S$ (the transition function).

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.