Attacking Church's Thesis

My suspicion that CT is false first arose in connection with the concept of productive sets, which have two properties:

P1

They are classically undecidable (= no program can decide such sets).

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.

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 [18], for example, holds that the set $\cal A$ of all As 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 [24]).

 

Figure 1: Various Letter As

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 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 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 As. The situation is a bit different in the case of the mathematician Peter Kugel [23], who makes clever use of an elementary theorem in unmistakably arguing that the set of all beautiful objects is located above $\Sigma_1$ in AH:

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 ... This suggests that a person who recognizes the Sistine Chapel Ceiling as beautiful knows enough to paint it, [which] strikes me as somewhat implausible. ([23], pp. 147-148)

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 at all about beauty.¹⁴ 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.¹⁵ However, I think there is another concept that serves my purposes perfectly: namely, the concept of a story. Stories are thought by many to be at the very heart of cognition. For example, in their lead target chapter in Knowledge and Memory: The Real Story [39], 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.¹⁶ 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).¹⁷

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 -- Autopoeisis -- devoted to creating an artificial agent capable of autonomously creating sophisticated fiction. I first discussed this project in my What Robots Can and Can't Be [5], in which I specifically discussed the challenge of characterizing, precisely, the class of 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 uninteresting stories. For example, the world's first artificial story generator, TALE-SPIN [26], did a good job of that. Here, for example, is one of TALE-SPIN's best stories:

``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$

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

Arg3
	(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.	reductio

Clearly, Arg₃ 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 decide $\cal S$^I, that is, people who can decide whether something is an interesting story, can't necessarily generate interesting stories. Students in 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 producing the set of all such stories (including, as it does, such works as not only King Lear, but War and Peace) is quite another matter. These would be, necessarily, the 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:

``Shopping"

Jack was shopping at the supermarket. He picked up some milk from the shelf. He paid for it and left.¹³

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 Autopoeisis' artificial intelligence, BRUTUS:¹⁸

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

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 BRUTUS works:¹⁹

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

1

s_d at t_i wants p to occur;

2

s_r believes that s_d wants p to occur;

3'

(3 $\wedge$ 6') $\vee$

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;

4''

there is some action a such that:

4''a

s_r performs a at t_b in the belief that thereby p will not occur; and

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;

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 will occur.

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

D'

A story s is interesting iff

1

$\ldots$

$\vdots$

k

s instantiates (inclusive) either c₁ or c₂ or $\ldots$ or c_n.

k+1

$\ldots$

$\vdots$

p

$\ldots$

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.

4'

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

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.