Kalmár's Argument Against CT

Here's how Kalmár's argument runs. First, he draws our attention to a function g that isn't Turing-computable, given that f is:²⁷

$$g(x) = \mu_y(f(x, y) = 0) = \left\{ \begin{array}{l} \mbox{t... ...s}\\ 0 \mbox{ if there is no such $y$ }\\ \end{array}\right.$$

Kalmár proceeds to point out that for any $n \in$ 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.

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

Kalmár goes on to argue as follows. The definition of g itself implies the tertium non datur, and from it and CT we can infer the existence of a natural number p which is such that

(i)

there is no natural number y such that f(p, y)= 0; and

(ii)

this cannot be proved by any correct means.

Kalmá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 [28] (see also Moschovakis' [29] review of both Kalmár's paper and Mendelson's reaction) points out, Kalmár's notion of `correct proof,' for all Kalmá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á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ár (as Nelson [30] 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ár has failed to find a uniform procedure, a property usually taken to be a necessary condition for a procedure to qualify as effective.

Though Kalmár does anticipate the problem of lack of uniformity,²⁸ and though I personally happen to side with him on this issue, it is clear that his argument against CT falls flat: If Kalmár's argument is to succeed, (ii) can be supplanted with

(ii')

this cannot be proved by any effective means.

But then how can the argument be deductively valid? It is not, at bottom, a 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á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ár's argument is that it can be rather easily shown to be impotent 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ár's g the following function (which is just a trivial variation on the predicate H(P, i) from above).

$$h(M_i) = \left\{ \begin{array}{ll} 1 & \mbox{ if $M_i$\space... ... 0 & \mbox{ if $M_i$\space doesn't halt}\\ \end{array}\right.$$

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ár's reasoning: Start with M^P₁; proceed to simulate this machine. Assuming it halts, return 1, and move on to M^P₂, and do the same for it; then move to M^P₃, 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:

(i_h)

there exists an M^P_k such that h(M_k) = 0; and

(ii'_h)

this cannot be proved by any effectively computable means.

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 my case against CT? Well, it would seem to be free of the defects that plague Kalmár's argument. First, my narrational case is deductive, as Arg₃ 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.²⁹