Mendelson's Attack

Mendelson's attack on Arg₁ is based on ``theses" analogous to CT -- ``Peano's Thesis," ``Tarski's Thesis," ``Frege's Thesis," and ``Weierstrass' Thesis."⁶ The first three, respectively, are:

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.

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.

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.

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₁? 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₁'s premise (2): Mendelson seems to be saying that the equivalence this premise attributes to CT is chimerical:

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)

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

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

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{\lq true on some $\cal I$' is no clearer than, nor} \ldots \mbox{than, \lq intuitive truth'}$$

And with respect to PT the template becomes

$$\mbox{\lq ($\star$)-based function' is no less vague than, nor $\ldots$ than, \lq intuitive function'}$$

But there is a problem: Mendelson doesn't 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 how does it follow from this that, e.g.,

$$\mbox{\lq ($\star$)-based function' is no clearer than, nor $\ldots$ than, \lq 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

(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,

then

(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,

and

(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,

$$\vdots$$

Now suppose that (4) is true. From this assumption, and the conditional indicated immediately above, it would seem to follow by modus ponens and simplification of conjunction that

(+)

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.

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 modus tollens and negate (4). What's the verdict? It's possible to demonstrate the falsity of (+), by way of the following straightforward reasoning.

Arg2
	(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.
.$^\cdot$ .	(9)	Not-(+)

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

Suppose we have some 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, Y (``yes") or 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 Y iff $M_P : u \rightarrow$ halt. For this reason H is declared partially computable, and hence in $\Sigma_1$. To generalize, informally, the syntactic representation of AH is:

$\Sigma_n$

set of all predicates definable in terms of totally computable predicates using at most n quantifiers, the first of which is existential

$\Pi_n$

set of all predicates definable in terms of totally computable predicates using at most n quantifiers, the first of which is universal

$\Delta_n$

$\Sigma_n \cap \Pi_n$

We have, based on this scheme, the Arithmetic Hierarchy because, where $\subset$ is proper subset,

$$\begin{array}{c} \Sigma_0 \subset \Sigma_1 \subset \Sigma_2 ... ... \subset \Sigma_{m+1}\\ \Sigma_m \subset \Pi_{m+1} \end{array}$$

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 [23] has aptly called $\Pi_1$-procedures 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 Y is the result iff Gx:⁸

• Receive x as input
• Immediately print Y
• Compute, by repeatedly calling $P, R(x, 1), R(x, 2), \ldots$, looking for a N
• If N is found, erase Y and leave result undefined

Notice that it would be impossible to represent this procedure as a program. This can be verified by looking at any formal specification of `program.' For example, in Mathematical Logic, by Ebbinghaus et al., [14] programs can have only one PRINT instruction. (Typically, procedures are formalized by 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$, 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ödel number of arbitrary TM M) output N immediately, and then let it simulate M. If M halts, $M^{\star \star}$ erases N, outputs 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₂, Mendelson's counter-argument from above, is sound. Why? I take it, first, that (7) is uncontroversial.⁹ Since Arg₂ is formally valid, if (8), the only other premise in the argument, is true, the argument is sound. Premise (8), recall, is

(8)

One cannot construct the Arithmetic Hierarchy by way of the notion of an algorithm.

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

(8$^\star$)

One cannot construct the Arithmetic Hierarchy without the notion of an algorithm.

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

What about the second prong in Mendelson's attack? This prong is aimed against the EQU principle, which was the first premise in Arg₁, the argument Mendelson believes he has undermined. Here is the relevant 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)

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 not the situation Mendelson creates by way of his sub-proof. At best, he has overthrown this principle:

EQU$^\rightarrow$

If some thesis T states a conditional connection between a vague, imprecise notion and a precise, mathematical notion, then T is unprovable.

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 prove it" (p. 233). Mendelson goes on to claim that

$\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)

Here Mendelson seems to commit a bald non sequitur. For notice that nothing in this quote threatens Arg₁. Nowhere in Arg₁ 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 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:

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.⁵ (p. 233)

The third prong would be relevant if there were good deductive arguments for CT, 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 against CT, and so it would be rather double-minded if I went in search of deductive arguments 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¹¹ to what I have so far said against him.