Effective Procedures

Abstract

The “somewhat vague, intuitive” notion from computability theory of an effective procedure (method) or algorithm can be fairly precisely defined, even if it does not have a purely mathematical definition—and even if (as many have asserted) for that reason, the Church–Turing thesis (that the effectively calculable functions on natural numbers are exactly the general recursive functions), cannot be proved. However, it is logically provable from the notion of an effective procedure, without reliance on any (partially) mathematical thesis or conjecture concerning effective procedures, such as the Church–Turing thesis, that the class of effective procedures is undecidable, i.e., that there is no effective procedure for ascertaining whether a given procedure is effective. The proof does not even appeal to a precise definition of ‘effective procedure’. Instead, it relies solely and entirely on a basic grasp of the intuitive notion of such a procedure. Though the result itself is not surprising, it is also not without significance. It has the consequence, for example, that the solution to a decision problem, if it is to be complete, must be accompanied by a separate argument that the proposed ascertainment procedure is, in fact, a decision procedure, i.e., effective—for example, that it invariably terminates with the correct verdict.

1. Effectiveness

The notion of an algorithm (in one sense)—an effective or mechanical procedure or method of calculation—is fundamental to computability theory. The basic idea is that of a finite, mechanical, step-by-step, automatic, and infallible procedure for accomplishing some specific purpose, especially for solving some specific problem. There are alternative characterizations of an effective procedure, but no characterization is universally accepted by experts.1 This situation raises questions. Is there, nevertheless, a generally intended notion? If so, can it be fully captured by a reasonably precise, sense-preserving definition? If so, does the definition provide or yield an effective procedure for determining of any given procedure whether it is effective?

The general recursive functions are the very functions on the natural numbers that are computable by a Turing machine and the λ-definable functions on the natural numbers, as well as the functions that satisfy certain other precise mathematical definitions. General recursive functions are paradigms of effectively, i.e., mechanically or algorithmically, calculable functions. The Church–Turing thesis is the proposition that all effectively calculable functions on natural numbers are general recursive. In effect, it is the conjecture that the effectively calculable functions on natural numbers are exactly the general recursive functions and, equivalently, exactly the so-called Turing-computable functions on the natural numbers.2

Computability theorists have accepted the Church–Turing thesis even in the absence of proof. A once standard view, enshrined in authoritative encyclopedia articles and the like, is that the Church–Turing thesis, even if correct, is not susceptible to proof, because the central notion of an effective procedure is not sufficiently formal and precise as to belong to mathematics, in a narrow sense excluding the theory of effectiveness, or to lend itself to proof of equivalence to a mathematical notion. In 1934, Gödel said of a thesis very close to what would come to be known as ‘Church’s thesis’ that it ‘cannot be proved, since the notion of finite computation is not defined, but it serves as a heuristic principle’. [4] (p. 44n3). In advancing his thesis, Church characterized the notion of an effectively calculable function as a ‘somewhat vague intuitive notion’ in contrast to the mathematical notion of a recursive function.3 Richard Jeffrey said, ‘This thesis is not susceptible of mathematical proof, for there is no limit to the variety of forms that clerical routines [effective procedures] might assume, and thus no general, precise definition of the term “clerical routine” of the sort we would need in order to prove the Church–Turing thesis’. [14] (p. 105) László Kalmár said, ‘Church’s thesis is not a mathematical theorem which can be proved or disproved in the exact mathematical sense, for it states the identity of two notions only one of which is mathematically defined while the other is used by mathematicians without exact definition’. [15] (p. 72) Similarly, Stephen Kleene said, ‘Since our original notion of effective calculability of a function (or of effective decidability of a predicate) is a somewhat vague intuitive one, the thesis cannot be proved’. [16] (p. 317). Later, he said, ‘This is a thesis rather than a theorem, in as much as it proposes to identify a somewhat vague intuitive concept with a concept phrased in exact mathematical terms, and thus is not susceptible of proof’. [17] (p. 232). Hartley Rogers said that the concept of a recursive function is ‘one way of making precise the informal mathematical notion of function computable “by algorithm” or “by effective procedure” …. The claim that each of the standard formal characterizations provides satisfactory counterparts to the informal notions of algorithm and algorithmic function cannot be proved’. [2] (pp. 1,20). Joseph Shoenfield said, ‘Unfortunately, no one has given a proof of Church’s thesis …, or even isolated the properties of calculable functions which would be needed in such a proof’. [18] (p. 120). Alan Turing wrote, ‘No attempt has yet been made to show that the “computable” numbers [i.e., the numbers whose decimal expansion are Turing–computable] include all numbers which would naturally be regarded as computable. All arguments which can be given are bound to be, fundamentally, appeals to intuition, and for this reason rather unsatisfactory mathematically’. [19] (p. 135) The Wikipedia entry on ‘effective method’ says of the Church–Turing thesis, ‘As this is not a mathematical statement, it cannot be proven by a mathematical proof’.

Turing is properly credited with proof that there is no computational procedure for determining of any given computational procedure, whether it eventually terminates or ‘halts’. However, the proof invokes the proposed Church–Turing definition or identification of a calculable function in terms of a recursive or Turing-computable function.4 One might conclude from the remarks just quoted that the notion of an effective procedure, in contrast to the notion of a general recursive or Turing-computable function, is insufficiently mathematically precise to be amenable to an actual proof of anything about it. Keeping to the spirit of the existing widespread agreement that the notion of an effective procedure is excessively vague or intuitive to lend itself to the mathematical proof of the Church–Turing thesis, Elliott Mendelson said, ‘Of course, because of the vagueness of the intuitive notions of effectively computable functions and algorithm, it is impossible to prove the validity of Church’s Thesis’. [20] (p. 239). However, in 1990, Mendelson made a more nuanced observation, arguing that even if the converse is not provable, it is, in fact, rigorously provable that all general recursive functions are effectively calculable. He wrote:

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 in recursion theory. A straightforward argument can be given for it. … This simple argument is as clear a proof as I have seen in mathematics, and it is a proof in spite of the fact that it involves the intuitive notion of effective computability.

[9], (pp. 232–233)

A result similar to but broader than Turing’s is similarly provable from the notion of an effective procedure itself, without defining or identifying the notion in other computability–theoretic terms and without invoking any conjecture or ‘thesis’ providing such a definition for effectiveness.

2. Some Preliminaries

Among procedures (methods) for performing tasks (for accomplishing some end) are procedures for producing or constructing something, including (but not limited to) procedures for producing correct answers to wh-questions of a certain class—answers to definite who–what–when–where–which–whether–why questions of that class. Among task-performing procedures are thus general procedures for determining the wh-facts. Let us call such a procedure an ascertainment procedure for that class. For example, placing an object onto a bathroom scale is a ‘what weight’ ascertainment procedure for determining the weight of middle-sized objects. A valuation procedure for a function is a ‘what value’ ascertainment procedure for determining the value of that function for a given argument. A judgment procedure for a class of propositions is a procedure for ascertaining whether a proposition of that class is the case, yes or no. A genuine judgment procedure includes steps (at least one) for concluding truth and steps for concluding falsity, even if some of these steps will not be executed. A judgment procedure is representable by a valuation procedure for a corresponding function to {0, 1}.5

Consider how one might go about ascertaining, given an arbitrary entity of kind K, whether it has a particular property F. Let us call any ascertainment procedure for determining whether a given input of kind K has property F or instead lacks it a judgment procedure for property F applicable to (things of) kind K (‘a judgment procedure for Fness of Ks’). An example of a judgment procedure is the classical ‘she loves me; she loves me not’ method, applicable to females, of determining whether one is loved by a particular female by establishing the oddness or evenness of the number of petals on an associated flower.6 Let us also say that a judgment procedure for F applicable to K certifies all and only those things of kind K that it deems to have property F.

As a special case, a judgment procedure might be applicable to judgment procedures (i.e., it might be itself of a kind for which it is a judgment procedure). As a very special case, a judgment procedure applicable to judgment procedures—a judgment meta-procedure—might have its own target property. For example, a judgment meta-procedure consisting of an odd number of steps could consist of an odd number of steps. More typically, a judgment procedure will either be inapplicable to itself or lack its target property (or both). A judgment procedure for being a so-called perfect number is not itself a number (rather, it is a procedure), let alone a perfect number. Let us say that a judgment procedure is self-certifying iff it certifies itself and that it is non-self-certifying iff it is not self-certifying.

A valuation procedure for a function may be infallible, in the sense that it never delivers a wrong value for a given argument, and automatic or deterministic, in that it never calls for (or even permits) initiative or creative choice (‘ingenuity’), and furthermore a priori, while still failing to be effective or algorithmic. To be effective, a valuation procedure must also invariably eventually deliver the right value after a finite number of steps in a finite duration. An (effective) calculation procedure for a function is an effective valuation procedure for the function, i.e., an algorithm for calculating the function. A function is effectively calculable iff there exists a (known or unknown) effective calculation procedure for it.

A decision procedure (or a test) for property F applicable to things of kind K (a ‘decision procedure for Fness of Ks’) is an effective judgment procedure for Fness of Ks. That is, it is a step-by-step procedure for ascertaining, through algorithmic calculation, concerning any input of K, the correct true/false verdict, whether it has F or instead lacks it (See note 1). Decision procedures are not restricted to mathematical properties of natural numbers. To take an example from music theory, there is a decision procedure for the property of being a chord tone in a given musical key. The method of truth tables not only defines propositional-calculus validity (tautological validity) of logical arguments but also provides a decision procedure. A decision procedure can be provided by representing it as a general recursive function of a specific kind. A decision procedure for a property F (effectively) decides a class G iff G is the class of things having the decision procedure’s target property F. The method of truth tables thus decides the class of arguments that are derivable (deducible) in the propositional calculus. There are judgment procedures for validity in full first-order logic. However, assuming the Church–Turing thesis, by Church’s theorem (and Gödel’s completeness theorem), there can be no decision procedure for validity in full first-order logic.

We say that a class G is (effectively) decidable (or that ‘the Gs are decidable’) iff there exists a (known or unknown) decision procedure that decides G; otherwise, G is undecidable. The decision problem for a property F and a kind K is the problem of producing a decision procedure for the Fness of Ks. A decision problem (as the term is used here) is not to be confused with the relevant yes/no questions themselves about each appropriate input; it is a demand for an algorithm for ascertaining the answers to those questions. A decision problem is solved by providing a step-by-step decision procedure, or at least by establishing an effective method for producing a decision procedure. A decision problem is said to be solvable iff there exists a (known or unknown) decision procedure that solves it, and unsolvable otherwise.7

3. A Theorem about Effectiveness

Insofar as there is a generally intended notion of an effective procedure or algorithm, it is almost certainly definable to a reasonably high degree of precision (See note 1). I submit that whereas the notion of effective calculability belongs to computability theory, it is ultimately epistemic in content and is thereby not a notion of mathematics proper in a narrower sense. The logical notion of a proof is also partly epistemic in content, concerning an a priori and distinctly mathematical kind of epistemic justification. Mathematics, in the narrower sense, consists of what is epistemically justified by means of mathematical proofs, and of the justifications, the proofs, themselves, but not of the very notion of epistemic justification and its cognates. The latter belong to meta-mathematics or to the philosophy of mathematics, specifically to the epistemology of mathematics. Likewise, effective calculability concerns a distinctly mechanical, computational method of obtaining information and ascertaining the facts. It thereby invokes the philosophically rich and puzzling notions of knowing which or knowing what. Effective calculability is thus unlike the notion of a general recursive function, which is not a notion special to the epistemology of arithmetic. It is also noteworthy that effective procedures are a priori methods applied to inputs.8

Suppose a decision procedure is proposed as a solution to a decision problem, but it is questioned whether the proposed procedure is, in fact, effective. Is there a general recipe for effectively calculating whether a given candidate is, or is not, an effective or algorithmic calculation procedure? In particular, can a precise, sense-preserving definition for ‘effective procedure’ (assuming there is such) yield such a general recipe? This is, in effect, the decision problem for effective procedures. To be sure, there is something circular about the idea of ascertaining by means of an effective procedure whether a given procedure is effective, but it is not unreasonable merely on that ground to seek such a procedure. No vicious circularity is involved in the search. Given a solution to the decision problem for effective procedures, one need only apply that decision procedure to establish whether a proposed solution to a decision problem is effective. On the other hand, the mere nonexistence of known counter-instances is no proof that a proposed decision procedure is effective. If there is no effective recipe for deciding effectiveness, then (unless the effectiveness of a procedure is known immediately and non-inferentially) if a solution to a decision problem is to be definitive, it should be accompanied by proof of its effectiveness for the question at hand (even if that proof is trivial). It might be demonstrated, for example, that the procedure parallels the standard calculation of a recursive function. In actual practice, the effectiveness of a decision procedure is typically beyond a reasonable doubt, making proof of effectiveness otiose. Still, strictly speaking, if the effectiveness of a procedure is undecidable, then the very endeavor to solve a decision problem seems to require proof of effectiveness in order for the solution to be definitive. This requires at least a grasp of a reasonably precise, generally intended notion of effectiveness.

Insofar as the Church–Turing thesis, which invokes the notion of effective calculability, is a definite proposition, there are indeed substantive theorems primarily concerning effective calculation in general—including effective non-numeric calculation, such as a music-theoretic calculation of whether a given note is, or is not, a chord tone in the key of A♭m. In particular, it is logically provable solely and directly from the notion of an effective procedure—informal, imprecise, and ill-defined though it may be—that the decision problem for effective procedures is unsolvable, i.e., that there is no effective procedure for determining whether any given procedure is indeed effective.9

Theorem: The class of effective procedures is undecidable.

As a corollary, the notion of an effective procedure cannot be encoded by means of a general recursive function.

The result itself is closely related to the proof that no Turing-computable function solves every case of the halting problem for Turing machines. There are differences, however. The latter result concerns ascertaining whether a given Turing program terminates. The former is concerned more broadly with ascertaining whether a given task-performing procedure is effective, including procedures such as the effective procedure for bisecting an angle in Euclidean geometry using only a compass and a straightedge. While all effective procedures terminate, not all terminating procedures are effective. Additionally, the present result is that no effective procedure—whether a Turing program or not—decides the effectiveness of a given procedure—whether a Turing program or not. (It is Turing’s thesis or conjecture that all effectively calculable functions from natural numbers to natural numbers are Turing-computable.)

That effectiveness of procedures is not itself decidable is not surprising. (Cf. Rice’s theorem). What is noteworthy is that the result is provable directly from the ‘somewhat vague intuitive’ notion of an effective step-by-step procedure. The proof proceeds primarily by applying Cantor’s method of diagonalization directly to the relation of certification by a decision procedure. No appeal is made to any lemma, conjecture, or thesis invoking recursiveness or Turing computability. In particular, the proof does not invoke the Church–Turing thesis or anything similar. In fact, there is no reliance on anything very mathematical. The undecidability of effectiveness belongs to computability theory, more specifically, to the theory of effective procedures. However, the proof does not even appeal to a precise definition of ‘effective procedure’. Instead, it relies solely and entirely on a basic grasp of the intuitive notion of such a procedure. The only non-logical observation employed in the proof is not subject to any real doubt.

Specifically, the proof may be regarded as invoking a principle stating a conditional relationship regarding the composition of an effective decision procedure out of effective sub-procedures, perhaps something like the following:

If a judgment procedure P^K_F, for Fness of Ks, consists of a finite sequence of steps such that:

(i)

Each of the steps is individually effectively executable (executable by an effective procedure);

(ii)

The first step is applied to an initial input I;

(iii)

Any input to a successor step is the result of an earlier step, or else is the initial input I; and

(iv)

For any initial input I′ to P^K_F, if I′ is of K, then: I′ has F iff invariably when the sequence of steps is fully implemented, P^K_F culminates in a finite duration in certifying I′,

then the result of replacing each effectively executable step of P^K_F with its corresponding effective procedure is a decision procedure for the Fness of Ks.

This principle is not merely a conjecture but presumably a theorem concerning effectiveness. Unlike the Church–Turing thesis, it is a trivial and obvious analytic truism concerning effective procedures. (Cf. [22] (p. 52n118)).

Although the notion of an effective procedure is not itself susceptible to a decision procedure, as noted above, the generally intended notion is evidently definable with a reasonably high degree of precision. In fact, an appropriate definition provides a checklist of necessary and sufficient conditions, which in turn yields a judgment procedure for the effectiveness of judgment procedures. However, the judgment procedure does not qualify as a decision procedure. In particular, the requirement that the procedure invariably eventually culminate in the correct verdict (‘halts’) after finitely many steps in a finite duration is not always decidable. In fact, it is a corollary of the undecidability of effectiveness that any proposed definition for ‘effective procedure’ that is itself decidable does not correctly capture the intended notion. There is thus a kernel of truth in the claim that the notion of an effective procedure is not precisely definable. While the intended notion can evidently be defined reasonably precisely, effectiveness is not a notion of mathematics proper (excluding computability theory), and no definition, however precise, can provide a decision procedure for it. A definition that provides a correct checklist without providing a test is the best of all possible worlds. This situation is not unfamiliar. The definition of a theorem of first-order logic, although precise, does not generate a decision procedure for first-order logical provability. Likewise, the definition of a general recursive function, although precise, does not generate a decision procedure for recursiveness. Otherwise, theoretically, Church’s theorem that the class of first-order-logical validities is not recursive could be proved by an effective calculation.10

This situation poses a difficulty in seeking solutions to decision problems. The effectiveness of a proposed judgment procedure may be questioned, and there are no certain means by which all such challenges may be effectively either validated or invalidated.11 However, the difficulty is surmountable. It does not follow from the undecidability of effectiveness that it is unknowable whether some judgment procedures are effective. Rather, no general algorithm is possible for resolving in every case whether a given ascertainment procedure is effective. If one is interested in the question of whether a proposed procedure is effective, in at least some cases, some creative initiative may be required to determine the answer.12 In particular, if a procedure is proposed as a solution to a decision problem, its effectiveness must be established without the aid of an effective recipe for doing so in all cases. (The present result notwithstanding, special subclasses of effective procedures are decidable, and indeed recursive.)

The undecidability of effectiveness echoes the proof that no Turing machine solves the halting problem for Turing valuation procedures. (See note 12 above.) The present result, however, does not specifically concern computer programs or recursive functions. The undecidability of effectiveness applies more broadly to judgment procedures for properties of any sort—mathematical or otherwise—including judgment procedures for properties not known to be representable by means of a mathematical function, such as some procedures for ascertaining which course of action among options will best serve one’s interests in the long run. Indeed, the undecidability of effectiveness applies to the full range of task-performing procedures.