Cleland's Doubts About CT

Cleland [10], [9] discusses three variants on our CT:

CT₁

Every effectively computable number-theoretic function is Turing-computable.

CT₂

Every effectively computable function is Turing-computable.

CT₃

Every effective procedure is Turing-computable.

Before evaluating Cleland's arguments against this trio, some exegesis is in order. First, each of these three theses is a conditional, whereas our CT is a biconditional. There should be no question that the biconditional is more accurate, given not only Mendelson's authoritative affirmation of the biconditional form, but also given that Church himself originally refers to his thesis as a definition of ``effectively calculable function" in terms of ``recursive function" [8].³⁰ However, since I have happily conceded the `if' direction in CT, there is no reason to worry about this aspect of Cleland's framework. The second point is this: by `number-theoretic' function Cleland simply means what we have hitherto called a function, that is, a mapping from N to N. We thus now understand function simpliciter, as for example as it's used in CT₂, to allow functions from the reals to reals.³¹ There is of course no denying that Church and Turing failed to advocate CT₂, but CT₁ is certainly the ``left-to-right" direction of our CT.

Now, what does Cleland say against CT₁-CT₃? She claims, first, that CT₃ can be disproved; the argument is simply this. One type of effective procedure coincides with what Cleland calls ``mundane procedures," which are ``ordinary, everyday procedures such as recipes for making Hollandaise sauce and methods for starting camp fires; they are methods for manipulating physical things such as eggs and pieces of wood" ([9], 11). Turing Machine procedures, on the other hand, are ``methods for `manipulating' abstract symbols" ([9], 11). Since mundane procedures have ``causal consequences," and TMs (qua mathematical objects) don't, it follows straightaway that mundane procedures aren't Turing-computable, that is, $\neg$CT₃.

Cleland's reasoning, when formalized, is valid; no question about that. The problem is that CT₃ (at least on her reading) has next to nothing to do with those propositions placed in the literature under the title ``Church's Thesis"! CT<sub>3</sub> is a variant that no one has ever taken seriously. It may seem to some that CT<sub>3</sub> has been taken seriously, but this is only because one construal of it, a construal at odds with Cleland's, has in fact been recognized. On this construal, that a procedure is Turing-computable can be certified by either a relevant design (e.g., a TM flow-graph for making Hollandaise sauce, which is easy to come by), or by a relevant artifact (e.g., an artificial agent capable of making Hollandaise sauce, which again is easy to come by). At any rate, I'm quite willing to concede that CT<sub>3</sub>, on Cleland's idiosyncratic reading, is provably false. (Note that we have known for decades that even CT<sub>1</sub>, on an intuitionistic (and hence idiosyncratic) reading of ``effectively computable function," is provably false. See note 24.) It's worth noting that Cleland herself has sympathy for those who hold that her reading of CT₃ is not a bona fide version of Church's Thesis ([9], 10). What then, about CT₂ and CT₁?

Here Cleland no longer claims to have a refutation in hand; she aims only at casting doubt on these two theses. This doubt is supposed to derive from reflection upon what she calls ``genuinely continuous devices" ([9], 18), which are objects said to ``mirror" Turing-uncomputable functions ([9], 16-17). An object is said to mirror a function iff (a) it includes a set of distinct objects which are in one-to-one correspondence with the numbers in the field of the function, and (b) the object pairs each and every object corresponding to a number in the domain of the function with an object corresponding to the appropriate number in the range of the function. Cleland takes pains to argue, in intuitive fashion, that there are objects which mirror Turing-uncomputable functions (e.g., an object moving through a 2-dimensional Newtonian universe). She seems completely unaware of the fact that such objects provably exist -- in the form, for example, of analog chaotic neural nets and, generally, analog chaotic dynamical systems [35], [34]. (These objects are known to exist in the mathematical sense. Whether they exist in the corporeal world is another question, one everyone -- including Cleland -- admits to be open.) We will be able to see Cleland's fundamental error (and, indeed, the fundamental error of anyone who attacks CT by taking her general route) if we pause for a moment to get clear about the devices in question. Accordingly, I'll present here an analog dynamical system via the ``analog shift map," which is remarkably easy to explain.

First let's get clear on the general framework for the ``shift map." Let A be a finite alphabet. A dotted sequence over A is a sequence of characters from $A^\ast$ wherein one dot appears. For example, if A is the set of digits from 0 to 9, then 3.14 is a dotted sequence over A. Set $A^\cdot$ to the set of all dotted sequences over A. Dotted sequences can be finite, one-way infinite (as in the decimal expansion of $\pi$), or bi-infinite. Now, let $k \in$ N; then the shift map

$$S^k : A^\cdot \rightarrow A^\cdot : (a)_i \rightarrow (a)_{i+k}$$

shifts the dot k places, negative values for a shift to the left, positive ones a shift to the right. (For example, if (a)_i is 3.14159, then with k = 2, S²(3.14159) = 314.159.) Analog shift is then defined as the process of first replacing a dotted substring with another dotted substring of equal length according to a function $g : A^\cdot \rightarrow A^\cdot$. This new sequence is then shifted an integer number of places left or right as directed by a function $f : A^\cdot \rightarrow$ Z. Formally, the analog shift is the map

$$\Phi : a \rightarrow S^{f(a)}(a \oplus g(a)),$$

where $\oplus$ replaces the elements of the first dotted sequence with the corresponding element of the second dotted sequence if that element is in the second sequence, or leaves it untouched otherwise. Formally:

$$(a \oplus g)_i = \left\{ \begin{array}{ll} g_i & \mbox{ if $... ...ox{ if $g_i$\space is the empty element}\\ \end{array}\right.$$

Both f and g have ``finite domains of dependence" (DoDs), which is to say that they depend only on a finite dotted substring of the sequence on which they act. The domain of effect (DoE) of g, however, may be finite, one-way infinite, or bi-infinite. Here is an example from [34] (547) which will make things clear, and allow us to see the fatal flaw in Cleland's rationale for doubting CT₂ and CT₁. Assume that the analog shift is defined by (where $\pi^2$ is the left-infinite string $\ldots 51413$ in base 2)

DoD	f	g
0.0	1	$\pi^2$
0.1	1	.10
1.0	0	1.0
1.1	1	.0

and that we have a starting sequence of u = 000001.10110; then the following evolution ensues:

000001.00110

0000010.0110

$$\pi^2.0110$$

$$\pi^20.100$$

$$\pi^20.100$$

$$\pi^201.00$$

$$\pi^21.00$$

$$\pi^201.00$$

At this point the DoD is 1.0 and hence no changes occur; this is a fixed point. Only the evolution from an initial dotted sequence to fixed point counts. In this case the input-output map is defined as the transformation of the initial sequence to the final subsequence to the right of the dot. (Hence in our example u as input leads to 00.) The class of functions determined by the analog shift includes as a proper subset the class of Turing-computable functions. (The proof is straightforward: [34].) Moreover, the analog shift map is a mathematical model of idealized physical phenomena (e.g., the motion of a billiard ball bouncing among parabolic mirrors). From this it follows that we provably have found exactly what Cleland desires, that is, a genuinely continuous device that mirrors a Turing-uncomputable function. So, if Cleland can establish that

(16)

If x mirrors a function, then x computes it.

she will have overthrown both CT₂ and CT₁. Unfortunately, given our analysis of the analog shift map, we can see that Cleland doesn't have a chance; here is how the reasoning runs. Recall, first, the orthodox meaning of `effectively computable function,' with which we started this paper: a function f is effectively computable provided that, an agent having essentially our powers, a computist (or worker), can compute f by following an algorithm. So let's suppose that you are to be the computist in the case of the analog shift map. There is nothing impenetrable about the simple math involved; we'll assume that you have assimilated it just fine. So now we would like you to compute the function $\Phi$ as defined in our example involving $\pi$. To make your job as easy as possible, we will guarantee your immortality, and we will supply you with an endless source of pencils and paper (which is to say, we are ``idealizing" you). Now, please set to work, if you will; we will wait and observe your progress $\ldots$

What happened? Why did you stop? Of course, you stopped because you hit a brick wall: it's rather challenging to write down and manipulate (or imagine and manipulate mentally) strings like $\pi$ in base 2! (Note that the special case where the DoE of g is finite in the analog shift map generates a class of functions identical to the class of Turing-computable ones.) Yet this is precisely what needs to be done in order to attack CT₂ and CT₁ in the way Cleland prescribes.

Cleland sees the informal version of the problem, for she writes:

Is there a difference between mirroring a function and computing a function? From an intuitive standpoint, it seems that there is. Surely, falling rocks don't compute functions, even supposing that they mirror them. That is to say, there seems to be a difference between a mere representation of a function, no matter how detailed, and the computation of a function. [Q:] But what could this difference amount to? ([9], 20)

She then goes on to venture an answer to this question:

A natural suggestion is that computation requires not only the mirroring of a function but, also, the following of a procedure; falling rocks don't compute functions because they don't follow procedures. ([9], 20)

Cleland then tries to show that this answer is unacceptable. The idea is that since the answer doesn't cut it, she is entitled to conclude that (16) is true, that is, that there isn't a difference between mirroring a function and computing a function,³² which then allows the mere existence of (say) an idealized billiard ball bouncing among parabolic mirrors to kill off CT₂ and CT₁.

What, then, is Cleland's argument for the view that the ``natural suggestion" fails in response to Q fails? It runs as follows:

Turing machines are frequently construed as purely mathematical objects. They are defined in terms of the same kinds of basic entity (viz., sets, functions, relations and constants) as other mathematical structures. A Turing machine is said to compute a number-theoretic function if a function can be defined on its mathematical structure which has the same detailed structure as the number-theoretic function concerned; there isn't a distinction, in Turing machine theory, between computing a function and defining a function $\ldots$ If computing a function presupposes following a procedure, then neither Turing machines nor falling rocks can be said to compute functions.

This argument is an enthymeme; its hidden premise is that `compute' is used univocally in the relevant theses, i.e., that `compute' means the same thing on both the left and right sides of CT, CT₁, and CT₂. This premise is false. The locution `f is effectively computable,' on the orthodox conception of Church's Thesis, does imply that there is an idealized agent capable of following an algorithm in order to compute f. But it hardly follows from this that when `compute' is used in the locution `f is Turing-computable' (or in the related locution `TM M computes f'), the term `compute' must have the same meaning as it does in connection with idealized agents. Certainly anyone interested in CT, and in defending it, would hasten to remind Cleland that the term `compute' means one thing when embedded within CT's left side, and another thing when embedded within CT's right side.³³ Having said this, however, and having implicitly conceded the core mathematical point (viz., that at least some definitions of TMs and Turing-computability deploy `compute' in the absence of the concept of ``following"³⁴), I should probably draw Cleland's attention to the formal approach we took above, where in order to characterize information-processing beyond the Turing Limit, we distinguished between a TM as a type of architecture, and a program which this architecture follows in order to compute. This is why we spoke of TM-program pairs.

Cleland never intended to literally refute CT₁ and CT₂. (As we have seen, she did intend to refute the heterodox CT₃, and for the sake of argument we agreed that here she succeeds.) But I conclude that she fails even in her attempt to cast doubt upon these theses, and that therefore CT is unscathed by her discussion. In contrast, my own case against CT targets this thesis with a deductive argument having no hidden premises and presupposing no convenient construal of CT. I have laid my cards on the table for all to see. I'm pretty sure my hand is the best one hitherto revealed, but as to whether it wins, or merely marks another chapter in the -- interesting -- story of Church's Thesis, my readers must judge.