Partial functions and Church’s Thesis
Alex Oliver and Tim Smiley’s magnum opus Plural Logic runs to some 340 pages before the end matter in the second edition. The final chapters are heavy going, involving detailed developments of some cumbersome (indeed, uninviting) formal theories. I wouldn’t be surprised if few readers have made it to the ‘Postscript’ touching on unfinished business.
So perhaps not many have read the discussion on p. 324 in which O&S argue that “a proper understanding of partial functions shows that the supposedly ‘easy part’ of Church’s Thesis is wrong”. They aim, then, to cast doubt on the standard claim that partial recursive functions (in the technical sense) are effectively, algorithmically, computable (in an intuitive, informal, sense). I am unpersuaded.
To start from their own example, suppose we have effectively Gödel-numbered the formulas of our favourite version of the predicate calculus. Consider two functions from [katex][/katex] to {0, 1}. First, g(x) is defined to equal 1 if x numbers a theorem, and to equal 0 otherwise. Second, h(x) is defined to equal 1 if x numbers a theorem, and is undefined otherwise. Uncontentiously, the total function g is not recursive (as shown by Church and Turing). While the partial function h is partial recursive (for example, there is a Turing machine which given input x, churns way to enumerate the Gödel-numbers of theorems, halting with output 1 if and only ifx turns up in the enumeration).
Now, O&S note that by Church’s Thesis h, being partial recursive, is therefore algorithmic computable. But they continue:
To our minds, this cannot be right. There cannot be an algorithm for computing h for the same reason that there cannot be an algorithm for computing g. Just as waiting to see whether g(x) is 1 or 0 would provide a decision procedure for the predicate calculus, so waiting to see whether h(x) is 1 or else has no value (however that may be encoded) would do the same. As we see it there is only a partial algorithm. When we ask ‘what is h(x)?’ we may get an answer, but we may be kept waiting, and waiting, and waiting . . .
This is the first time in the book that O&S talk about algorithms, and they don’t explicitly tell us what they mean by a “partial algorithm”. And standard accounts of the informal notion of an algorithm like the one at the beginning of Hartley Rogers’s classic book don’t help.
I suppose that one natural idea of a partial algorithm (but not O&S’s) would be illustrated by an algorithm which along the way says “Goto line 101” although there is no line 101: so in executing this partial algorithm we grind to a halt, not by gracefully executing a line such as “101: Halt!”, but by running out of instructions. But note that the Turing machine routine which we just imagined for computing h doesn’t implement a partial algorithm in that sense. Here the algorithm tells us what to do at every step – we are to keep on enumerating the Gödel-numbers of theorems until we get a match. We never run out of instructions, though in the case where x numbers a non-theorem the execution doesn’t terminate.
O&S regard the sketched algorithm as a partial algorithm for computing h in another sense. For they think of an algorithmic computation for h, properly so called, as one which for each x either delivers the output 1 or tells us that it “has no value (however that may be encoded)”. More generally, they stipulate that an algorithm for a partial function [katex]f [/katex] should answer the question ‘what is f(x)’ for every x, by either giving us the value of f(x) when that is defined or else telling us that f(x) has no value. Emphatically: “We say that if the function has no value, an adequate algorithm should always say so.” By that standard, our Turing machine routine for computing h isn’t “adequate”, it doesn’t deliver the full goods, and only implements a partial algorithm in the sense that it gives the value of h(x) when it has one but otherwise falls short by remaining silent in the other cases when h(x) is undefined.
Say that a c-algorithm (“c” for conventional) for computing a partial function f is one which returns the (correct!) value of f(x) whenever that is defined and is otherwise remains silent; while a n-algorithm (“n” for non-partial according to O&S) for computing a partial function f returns the value of f(x) whenever that is defined and returns “undefined” otherwise. We know that a c-algorithm for a partial function can’t always be upgraded to n-algorithm. This is in fact a standard result – there’s a related result in my Gödel book, and O&S have given us another example, by noting that there is an c-algorithm for computing h but there can’t be an n-algorithm for computing h (or else we could turn it into a c-algorithm for computing the total function g, which there can’t be). So yes, there can be partial recursive functions which aren’t computable by an “adequate” n-algorithm.
But so what? Why fuss? There is only some reason to suppose that we’ve found a flaw in Church’s Thesis that a partial recursive function is effectively computable by an algorithm if that Thesis is implicitly understood as a claim about computability by an n-algorithm, i.e. by a mechanical procedure which always terminates (either with a value for the computed function or a report that there isn’t a value). But is the Thesis understood that way?
O&S quote as typical Alan Hamilton’s remark “It is reasonable to say that a partial function is computable by algorithm if there is an algorithm which yields the value of the function whenever it is defined”, and they respond that such authors “confuse a partial algorithm with an algorithm for a partial function”. But to talk of confusion is only fair comment if these authors should be assuming that execution of a genuine algorithm for a partial function must always terminate (either giving us a value or reporting that no value is to be had).
But it is more than fifty years since Hao Wang wrote in his From Mathematics to Philosophy (p. 84):
Gödel points out that the precise notion of mechanical procedures is brought out clearly by Turing machines producing partial rather than general recursive functions. In other words, the intuitive notion does not require that a mechanical procedure should always terminate or succeed. A sometimes unsuccessful procedure, if sharply defined, still is a procedure, i.e. a well determined manner of proceeding. Hence we have an excellent example here of a concept which did not appear sharp to us but has become so as a result of a careful reflection. The resulting definition of the concept of mechanical by the sharp concept of ‘performable by a Turing machine’ is both correct and unique. Unlike the more complex concept of always-terminating mechanical procedures, the unqualified concept, seen clearly now, has the same meaning for the intuitionists as for the classicists. Moreover it is absolutely impossible that anybody who understands the question and knows Turing’s definition should decide for a different concept.
I’ll buy this: in so far as there is a widely-shared, intuitive, informally explicated, idea of an algorithmic procedure, it is by now not built in the very notion of such a procedure that it should always deliver an answer (a value or a “no value” output). It is nice, no doubt, when an n-algorithm is available; but the now-embedded-because-more-useful notion is that of a c-algorithm, and I don’t think authors are typically confused about this. Church’s Thesis doesn’t go wrong in claiming that partial recursive functions are algorithmically computable in that conventional sense.