Notes for B. Jack Copeland, "WHAT IS COMPUTATION?"
Key concepts: algorithm, architecture, axiomatic specification, code, honest model, labeling scheme, model, nonstandard interpretation, von Neumann computer.
Related theorists: Max Newman, John Searle, Alan Turing.
Originally published in 1996. Also a version in 2004 Philosophy of Computing and Information anthology in the first part “Four Concepts” entitled “Computation”.
Turing made clear the historical connection of computing to print, Copeland to tyranny; as I argue, besides being historically representational, computing has also been tyrannical, recalling Solon of Diogenes Laertius. Why does computing have to be like your boss, sometimes a "prick" or an "asshole" when it (computing, like your boss) forces you to do something you don't want to do in order to get the job done?
An algorithm is a 'mechanical' or 'moronic' procedure for achieving a specified result . . . a finite list of machine-executable instructions such that anyone or anything that correctly follows the instructions in the specified order is certain to achieve the result in question.
(335) To compute is to execute an algorithm. More precisely, to say that a device or organ computes is to say that there exists a modeling relationship of a certain kind between it and a formal specification of an algorithm and supporting architecture.
(335) In 1936 Turing published his now famous analysis of the concept of computation. It is true to say that this analysis has become standard in mathematical logic and the sciences. However, there is in the philosophical literature a certain class of problem cases which forms the basis of an objection to Turing's analysis. The thrust of the objection is that although Turing's account may be necessary it is not sufficient. If it is taken to be sufficient then too many entities turn out to be computers. The objection carries an embarrassing implication for computational theories of mind: such theories are devoid of empirical content. If virtually anything meets the requirements for being a computational system then wherein lies the explanatory force of the claim that the brain is such a system?
(335) My intention here is to uphold the sufficiency of Turing's analysis.
(336) [quoting Searle] A more realistic definition of computation will emphasize such features as the causal relations among program states, programmability and controllability of the mechanism, and situatedness in the real world.
(336) I shall argue that Searle is right in his claim that there is some pattern of physical activity in the wall (or bucket, etc.) that is 'isomorphic with the formal structure' of any given instance of computation.
Definition of computing as executing an algorithm, and algorithm as mechanical, moronic procedure that may be specific to an architecture; examples include Turing machine, assembly language, neural net.
An algorithm is a
'mechanical' or 'moronic' procedure for achieving a specified result
(in the case of α,
of course, the specified result is arriving at the values of f).
That is to say, an algorithm is a finite list of machine-executable
instructions such that anyone or anything that correctly follows the
instructions in the specified order is certain to achieve the result
in question. To say that α
an architecture is to say not only that a machine with this
architecture can run α
also that each instruction in α
explicitly for the performance of some sequence of primitive (or
'atomic') operations made available in the architecture.
(337) The primitive operations that are available vary from architecture to architecture. To give some examples: – If the architecture in question is a Turing machine then α will be a Turing machine table. . . . If the architecture in question is that defined by a particular assembly language (an assembly language is an architecture-specific programming language) then α will be a program in that language. . . . Where the architecture in question is a neural net with a particular pattern of connectivity and certain weights on the connections, α consists of step-by-step applications of a certain propagation rule and a certain activation rule. . . . In such an architecture steps are, of course, carried out in parallel: the execution of an algorithm is not necessarily a sequential procedure.
Labeling scheme formalizes architecture specifications to constitute code.
Support one has a formal specification of the architecture in
question and of the algorithms α,
call it SPEC. For definitions, let SPEC take the form of a set of
axioms, although nothing in what follows turns on the use of the
axiomatic method as opposed to some other style of formalization. . .
. How do we bridge the gap and say that e
a machine (at the time in question)? The bridge is effected by means
of a system of labeling
. . . Thus a labeling scheme for an entity consists of two parts: (1)
the designation of certain parts of the entity as label-bearers, and
(2) the method for specifying the label borne by each label-bearing
part at any given time.
(338) The idea, of course, is that the labels constitute a 'code' such that spatial or temporal sequences of labels have semantical interpretations.
(338) When the formal axioms in SPEC are true of an entity e under a labeling scheme L the ordered pair <e, L> will be called a model of SPEC.
(338-339) To gain a feel for what is being said here consider the hoary problem of whether the solar system computes solutions to its own equations of motion (Fodor, 1975, 74). . . . To answer 'yes' is to suppose that the solar system is a register machine. . . . If they want to persist in the claim that the solar system is computing the function f then they must describe for us the solar system's computational architecture and detail the algorithm by which the solar system arrives at values of f.
(339) Despite its naturalness the above account of computation will not do.
(339) Interestingly enough Turing's friend and colleague Max Newman used what is essentially a notational variant of Searle's Theorem as the basis of a devastating objection to Russell's causal theory of perception (Newman 1928).
Provides axiomatic specification of a machine architecture, raising question whether such approaches still possible in massively distributed networks full of shoddy code (Mackenzie).
This section explains by means of an example what is meant by an
specification of a machine architecture.
I will consider a simple machine M
central processor consists of three eight-bit registers: an
instruction register I,
a data buffer D
an accumulator A.
. . . M
(i.e. a particular type of serial processor).
(341) The intended interpretation of a statement of the form 'if X ACTION-IS Y' is that the occurrence of X produces or brings about the action Y.
(342) It is worth emphasizing that 'if X ACTION-IS Y' expresses a notion of consequence or dependency that is stronger than that expressed by the material implication X → Y.
(343) Yet an adequate theory of computation cannot be couched in a purely extensional language.
(342-343) Turing himself gives expression to this strong dependency relationship by means of the phrase 'completely determined by': each action of a Turing machine is completely determined by its configuration. . . . [quoting Turing] If at each stage the motion of a machine . . . is completely determined by the configuration, we shall call the machine an “automatic machine.”
(343) In this section I outline the proof of the theorem toward which Searle gestures in the quotation given in Section 1, viz.: For any entity x (with a sufficiently large number of discriminable parts) and for any architecture-algorithm specification y there exists a labeling scheme L such that <x, L> is a model of y.
(344) We cannot expect a mere wall to have physical properties that change in a way responsive to the sequencing of instructions in whatever program M happens to be running. . . . The solution is to use entities of greater abstraction as referents of the terms 'I', 'A', and 'D'. (I call this procedure 'Searlification'.)
(346) Reflection on the model presented in this section will yield the promised criteria for guarding the analysis given above of the predicate 'is computing the function f' from models of an architecture-algorithm specification that are of the wrong kind to sustain the analysis.
(346) A nonstandard interpretation of a theory is an interpretation that does not respect the intended meanings of the terms of the theory.
(347-348) The interpretation I have described for the axioms of M is a nonstandard one. We may say that the wall “computes” and mean by this nothing more than that the axioms for M, a computer, are true under the interpretation I have described. However, it would be an elementary error to infer from this that the wall computes in any genuine sense. . . . Similarly, under their intended interpretation the axioms for M add up to the proposition that M is a von Neumann computer, but this does not mean that if the axioms are true under a nonstandard interpretation then whatever they are true of under that interpretation is a von Neumann computer.
(348) I suggest the following modification to the analysis: Entity e is computing function f if and only if there exist a labeling scheme L and a formal specification SPEC (of an architecture and an algorithm specific to the architecture that takes arguments of f as inputs and delivers values of f as outputs) such that <e, L> is an honest model of SPEC.
(348) What are the grounds for insisting that the model fails to respect the intended meanings of the terms of the axiomatic theory? These are threefold. First, the axiomatic theory under consideration and those like it – the various dynamic logics, for example – are intended (in a phrase of Segerberg's (1989, 248) as logics of computer action. . . . The axioms of M certainly contain the term 'ACTION-IS' but the fact that the axioms (as interpreted) are true of the wall goes no way toward showing that the wall acted in accordance with the instructions in the algorithm.
(348) Second, the nonstandard interpretation introduces unintended temporal specificity into the theory.
(349) Third, the construction 'if . . . ACTION-IS . . .' is interpreted by means of material implication (the truth-condition assigned to each axiom is a universally quantified material implication).
(350) Only if Turing had made no mention of this strong dependency relationship would Searle's criticism of him in the above quotation be just.
Conditions for honesty of axiomatic computational model: labeling scheme not ex post facto, must secure truth of counterfactuals concerning machine behavior.
(350-351) In summary, I suggest two necessary conditions for honesty. First, the labeling scheme must not be ex post facto. This requirement guards the class of honest models from intruders that fail to respect the intended meanings of the terms of the axiomatic theory in ways of the sort outlined in the first and second of the above three criticisms. Second, the interpretation associated with the model must secure the truth of appropriate counterfactuals concerning the machine's behavior.
(351) These is something else very wrong about Deutsch's analysis: it makes no mention of the notion of an algorithm. In my view this notion should lie at the heart of an account of computation.
(352) [quoting Cummins] Computing reduces to program execution. . . . Program execution reduces to step satisfaction. (Cummins 1989, 91-92)
(353) An analysis of computation in terms of causation is intolerably narrow.
(354) It is the computational theory of mind, and not extant definitions of computation, that is the principal target of Searle and Hinckfuss.
(356) Searle offers the claim that brains are not 'intrinsically digital computers' as a consequence of his claim that 'syntax is not intrinsic to physics' (Searle 1992, 208, 225).
A new know thyself is the extent the brain can be assigned a computational interpretation.
(357) The rock-bottom issue in cognitive science is precisely whether, and to what extent, the brain can be assigned 'a computational interpretation'. If the argument presented here is correct, this is an empirical issue. It is always an empirical question whether or not there exists a labeling of some given naturally occurring system such that the system forms an honest model of some architecture-algorithm specification. And notwithstanding the truism that 'syntax is not intrinsic to physics' the discovery of this architecture-algorithm specification and labeling may be the key to understanding the system's organization and function.
Copeland, B. Jack. "What Is Computation?" Synthese 3 (1996): 335-357. Web. 6 Dec. 2012.