In an appendix to his book *Representation and Reality* (Putnam
1988, pp. 120-125), Hilary Putnam argues for a conclusion that would destroy
these ambitions. Specifically, he claims that *every ordinary open system
realizes every abstract finite automaton.* He puts this forward as a
theorem, and offers a detailed proof. If this is right, a simple system
such as a rock implements any automaton one might imagine. Together with
the thesis of computational sufficiency, this would imply that a rock has
a mind, and possesses many properties characteristic of human mentality.
If Putnam's result is correct, then, we must either embrace an extreme
form of panpsychism or reject the principle on which the hopes of artificial
intelligence rest. Putnam himself takes the result to show that computational
functionalism cannot provide a foundation for a theory of mind. [[Searle
(1990) argues for a similar conclusion, although his argument is much less
detailed than Putnam's. I comment on it briefly toward the end of the paper.]]

In what follows I will argue that Putnam's argument does not establish such a conclusion, and that the foundations of artificial intelligence are not in danger. His argument nevertheless points to the need for a better understanding of implementation, the relation that connects the theory of computation with the theory of physical systems. (Putnam calls this relation `realization'.) An analysis of Putnam's argument leads us to a better understanding of implementation, as well as to insights into the class of automata that are relevant in computational theories of cognition. As objections are raised and modifications are made, the discussion that follows will touch on a number of formalisms in the theory of computation and various constraints on implementation, before settling on a formalism and an account of implementation that avoid the most serious problems.

Putnam is centrally concerned with finite-state automata, or FSAs, and
in particular FSAs without input or output, or *inputless FSAs*. (He
extends his results to FSAs with inputs and outputs later.) Such an FSA
is specified by a set of formal states *{S_1, ..., S_n}*, and by a
set of state-transition relations which specify for each state the state
that must follow. He does not offer an explicit account of the conditions
under which a physical system implements an FSA, but from his discussion
it is clear that he requires something like the following.

A physical system implements an inputless FSA in a given time-period if there is a mappingI will later argue that this account is not quite right, but it captures the central facet of the notion of implementation: the requirement that in order for a physical system to implement a formal automaton, causal relations among states of a physical system must mirror formal relations among states of the automaton.ffrom physical states of the system to formal states of the FSA such that: if the system is in physical statepduring the time-period, this causes it to transit into a stateqsuch that formal statef(p)transits to formal statef(q)in the specification of the FSA.

Putnam considers an arbitrary system *S* - say, a rock - over an
arbitrary time period, such as from 12:00 to 12:07. Using the expression
*St(S,t)* to denote the maximal state of *S* at *t*, he
defines states of *S* in the following way.

Let the beginnings of the intervals during whichThe states are defined, then, so that the system goes through statesSis to be in one of its stages [...] bet_1, t_2, ..., t_n(in the example given,n=7, and the times in question aret_1 = 12:00,t_2 = 12:01,t_3 = 12:02,t_4 = 12:03,t_5 = 12:04,t_6 = 12:05,t_7 = 12:06). The end of the real-time interval during which we wishSto "obey" this table we callt_{n+1}(= t_8 = 12:07, in our example). For each of the statest_itot_{i+1}, i = 1, 2, ..., n, define a (nonmaximal)interval states_iwhich is the "region" in phase space consisting of all the maximal statesSt(S,t)witht_i <= t < t_{i+1}. (I.e.,Sis ins_ijust in caseSis in one of the maximal states in this "region". Note that the systemSis ins_1fromt_1tot_2, ins_2fromt_2tot_3, ..., ins_nfromt_ntot_{n+1}. (Left endpoint included in all cases but not the right - this is a convention to ensure the "machine" is in exactly one of thes_iat a given time.) The disjointness of the statess_iis guaranteed by the Principle of Noncyclical Behavior. (pp. 122-123.)

We can choose an arbitrary (inputless) FSA for the purposes of the argument.
Putnam chooses (claiming no loss of generality) an FSA that transits back-and-forth
between two states *A* and *B*, which is therefore required to
go through the sequence *ABABABA* in the time-period in question.

The argument that the system implements the FSA is straightforward.
We simply define physical state *a* to be the disjunction *s_1 v
s_3 v s_5 v s_7*, and state *b* to be *s_2 v s_4 v s_6*, and
we define the mapping *f* so that *f(a)=A* and *f(b)=B*.
(Putnam's presentation does not distinguish between physical states *a*
and *b* and formal states *A* and *B*; I introduce the distinction
for clarity.) It is easy to see that during the period in question, the
physical system cycles through the states *abababa*, corresponding
to formal states *ABABABA* as required.

Putnam further argues that the system's being in state *a* *causes*
it to transit into state *b* and vice versa, using the Principle of
Continuity to show that given that the system was in state *a* at
a time *t* with *t_{n-1} <= t < t_n* (and given boundary
conditions at *t*), it was *determined* that the system would
be in state *b* at times t with *t_n <= t < t_{n+1}*. I
will postpone discussion of this part of the argument.

The argument is general. Given any inputless FSA and any noncyclic physical system, we can map physical states of the system over an arbitrarily long period of time to formal states of the FSA by the same method. We associate the initial physical state of the system with an initial state of the FSA and associate subsequent physical states of the system with subsequent states of the FSA, where the FSA state-evolution is determined by its state-transition rules. The implementation mapping is determined by taking the disjunction of associated physical states for each state of the FSA, and mapping that disjunctive state to the FSA state in question. Under this mapping, it is easy to see that the evolution of the physical states precisely mirrors evolution of the FSA states. Therefore every noncyclic physical system implements every (inputless) FSA.

The problem, I think, is that Putnam's system does not satisfy the right
kind of state-transition conditionals. The conditionals involved in the
definition of implementation are not ordinary material conditionals, saying
that on all those occasions in which the system happens to be in state
*p* in the given time period, state *q* follows. Rather, these
conditionals have modal force, and in particular are required to support
counterfactuals: *if* the system were to be in state *p*, *then*
it would transit into state *q*. This expresses the requirement that
the connection between connected states must be *reliable* or *lawful*,
and not simply a matter of happenstance. It is required that *however*
the system comes to be in state *p*, it transits into state *q*
(perhaps with some restriction ruling out extraordinary environmental circumstances;
perhaps not). We can call this sort of conditional a *strong* conditional.

It is not quite clear whether Putnam intends his conditionals to have
this sort of modal force. He requires that the relation be a *causal*
relation, and goes to some lengths to argue that his construction indeed
satisfies the causal relation by arguing that its being in state *a*
fully determines its transition into state B, so he may have some such
requirement in mind. In any case, I will argue that his system does not
satisfy the strong conditionals in the way that implementation of an automaton
requires. There are two ways in which Putnam's system fails to satisfy
the strong conditionals. The first concerns the state-transitions that
are actually exhibited. The second concerns unexhibited state-transitions.

To see the first point, consider the transition from state *a*
to state *b* that the system actually exhibits. For the system to
be a true implementation, this transition must be reliable. But Putnam's
system is open to all sorts of environmental influences by its very definition
as an open system (indeed, Putnam exploits this fact to establish his Principle
of Noncyclical Behavior). It follows that if environmental circumstances
had been slightly different, the system's behavior would have been quite
different. Putnam's construction establishes nothing about the system's
behavior under such circumstances. The construction is entirely specific
to the environmental conditions as they were during the time-period in
question. It follows that his construction does not satisfy the relevant
strong conditionals. Although on this particular run the system happened
to transit from state *a* to state *b*, if conditions had been
slightly different it might have transited from state *a* to state
*c*, or done something different again.

In particular, it is quite possible for Putnam's system to be in state
*a* at all times between *t_{n-1}* and *t_n*, while failing
to be in state *b* at all times between *t_n* and *t_{n-1}*.
If environmental conditions had been slightly different at and after time
*t_n*, the system might have been buffeted into an entirely different
state well before *t_{n+1}*. The relevant strong conditionals are
therefore not satisfied. It will not do to argue that the system counts
as being in state *b* if it is in that state at the *beginning*
of the relevant time-interval. If so, then the same goes for state *a*,
and a similar argument can be given. We only need to note the possibility
of environmental buffeting soon after *t_{n-1}*, so that although
the system counts as being in state *a* in the given interval, it
is never in state *b* in the following interval.

Putnam argues (p. 123) that the system's being in state *a* throughout
the first interval *determines* the transition into state *b*
in the next interval, but his argument falls short of establishing what
is required. In particular, he only establishes that:

...given the information that the system was in stateWhat is important here is the clause "given boundary conditions at subsequent times". This is illegitimate information for the omniscient being in question to use. What is required is that together with the laws of nature, the state (and perhaps boundary conditions)Aatt, and given that the boundary condition attwasB_t, a mathematically omniscient being can determine from the Principle of Continuity that the systemSmust have been inSt(S,t), and can further determine, given the boundary conditions at subsequent times and the other laws of nature, howSevolves in the whole time interval under consideration. (p. 123)

The second failure of the conditionals is perhaps more interesting.
To qualify as an implementation, it is not only required that the formal
state-transitions that are manifested *on this run* (say, the transitions
from *A* to *B* and back) are mirrored in the structure of the
physical system. It is required that *every* state-transition be so
mirrored, including the many that many not be manifested on a particular
run. It may be, for instance, that the FSA in question is specified by
the state-transitions *A -> B*, *B -> A*, *C -> D*, *D
-> E*, and so on. In this case, we require that the unmanifested features
of the machine-table are reflected in the physical structure of the system,
so that it will be the case that *if* the system had been in state
*C*, it would have transited to state *D*, and so on.

Perhaps it might be objected that there is little point having such extra states when the machine eternally cycles between two states and will never reach the other states. However, an FSA will often specify the machine's behavior for more than one initial state; and more importantly the fact that there is a cycle in the state-space is a contingent feature of Putnam's example, and his argument is supposed to be perfectly general. Generally, a finite-state machine that is of practical interest will not exhaust all its states in a given run, nor will it cycle.

The requirement that unmanifested state-transitions also be reflected in the physical structure of the machine requires a slight change to our definition of implementation. It should read:

A physical system implements an inputless FSA in a given time-period if there is a mappingThe changes are (1) the requirement that the mapping map physical states ontoffrom physical states of the system onto formal states of the FSA such that: for every formal state-transitionP -> Qin the specification of the FSA, if the physical system is in a statepsuch thatf(p)=P, this causes it to transit into a stateqsuch thatf(q)=Q.

It is clear that Putnam's construction does not satisfy this stronger
condition. In fact, for any formal state *P* that does not appear
in the sequence manifested in a given run, his construction leaves undefined
the physical states that map onto *P*. Even if we pick arbitrary uninstantiated
physical states to map onto *P*, there is no reason to believe that
these will satisfy the requisite state-transition conditionals. (If the
conditional in the definition of implementation is read as a *material*
conditional, then it turns out that these conditionals are satisfied vacuously
- every instance of *p* transits to *q*, because there are no
instances of *p*. Again, the conditional needs to be read modally.)

To put the point slightly differently: from the fact that any system
that implements a given FSA must go through a sequence *abababa* in
real time, the converse does not follow. We cannot infer that any system
that goes through the sequence *abababa* implements the FSA. In effect,
Putnam has failed to ensure that his system reflects the structure of the
FSA. All he has done is ensure that a particular *trace* of the FSA
- that is, the states it goes through on a particular run - is reflected
by the system's behavior.[*] But much more is required. There are all sorts
of inherent possibilities in an FSA that are not reflected in a given trace.

*[[[I owe this observation to Joseph O'Rourke.]]]

In the body of his book (pp. 96-98), Putnam responds briefly to the
charge that his construction does not satisfy a certain kind of counterfactual:
in particular, the requirement that if the system *had not* been in
state *a*, it would not have transited into state *b* (this is
a requirement on causation according to the analysis in Lewis 1973). His
response is that these counterfactuals are dependent on the vague notion
of a similarity metric over possible worlds (at least on Lewis' analysis),
and that the notions of similarity and possible worlds are even vaguer
than what we are trying to explicate.

The counterfactuals that I require do not have this problem. All that
my account of implementation requires is that *if* the system is in
state *a*, it will transit into state *b*, however it finds itself
in the first state. This is in no way a similarity-based counterfactual.
It requires that in *all* (or perhaps most) situations in which the
system is in state *a*, it will transit into state *b*, no matter
how similar or dissimilar that situation is from the actual one. This class
of counterfactuals is much less vague than the other kind, and is therefore
not open to a similar objection. It simply corresponds to the requirement
that the transition be lawful. What makes the law of gravity a law is that
under *any* circumstances, if two bodies have an appropriate mass,
there will be such-and-such a force exerted. If it only happens between
12:00 and 12:07 today, due to unusual environmental conditions, it does
not count.

To overcome the first objection, it is sufficient to require that the
system *reliably* transits through a sequence of states *s_1, s_2,
...*, irrespective of environmental conditions. (To simplify, I will
hereafter assume that time is discrete. Nothing will depend on this.) This
is not a difficult requirement: most clocks satisfy it, for instance. Probably
most physical systems satisfy such a requirement; perhaps we might find
reliable sequences like this in patterns of radiation decay. In any case,
let us say a physical system contains a *clock* if it has a subsystem
that reliably transits through a sequence like this.

A system containing a clock will circumvent the first objection. If
we define the states *s_1, s_2, ...* of the system as those states
containing the relevant states of the clock, then the transition from *s_n*
to *s_{n+1}* will be reliable. If disjunctive states *a*, *b*,
and so on are defined appropriately, then the transitions between these
will satisfy the appropriate strong conditionals.

To reply to the second objection we need to make sure that the system
has sufficient extra states to map onto formal states that are not manifested
on a given run. We can do this by ensuring that the system contains a *dial*:
that is, a subsystem with an arbitrary number of different states, such
that when it is put into one of those states it stays in that state come
what may. Most physical systems will contain a dial - think of states corresponding
to marks on rocks, for instance.

*Claim*: Every physical system containing a clock and a dial will
implement every inputless FSA.

*Proof*: Label physical states of the system *[i,j]*, where
*i* corresponds to a clock state and *j* to a dial state. If
the system starts in state *[1,j]* it will reliably transit through
states *[2,j], [3,j]* and so on.

Assume the physical system on the actual run has dial state 1. The initial
state of the system will be *[1,1]*; we associate this state with
an initial state of the FSA. We associate states *[2,1], [3,1]* and
so on with subsequent states of the FSA in the obvious way. If at the end
of this process some FSA states have not come up, choose an unmanifested
state *P*, and associate state *[1,2]* with it. We associate
states *[2,2], [3,2]* and so on with the states that follow *P*
in the evolution of the FSA. If this does not exhaust the states of the
FSA, choose an unmanifested state and associate state *[3,1]* with
it, and so on. Eventually all the states of the FSA will be exhausted.
For each state of the FSA, there will be a non-empty set of associated
physical states *[i,j]*. To obtain the implementation mapping, the
disjunction of these states is mapped to the FSA state.

It is easy to see that this system satisfies all the strong conditionals in the strengthened definition of implementation. For every state of the FSA, if the system is (or were to be) in a state that maps onto that formal state, the system will (or would) transit into a state that maps onto the appropriate succeeding formal state. So the result is demonstrated.

There are minor problems with the states *[n,i]* that come up at
the end of the run, where *t_n* is the final time-step. We need to
satisfy conditionals of the form "if it were in state *[n,i]*, it
would transit appropriately" - that is, *[n,i]* would transit to a
physical state that maps onto a successor of *f([n,i])* - but we have
established nothing about the physical successors to *[n,i]*. We can
get around this problem by assuming the clock has an infinite sequence
of states, mapping all the states in each sequence, and mapping an infinite
disjunction onto each formal state. This is not an especially unrealistic
assumption; there are probably such infinite clocks in most continuous
systems.

Thus Putnam's result is preserved in only a slightly weakened form. But there is still no problem for the computationalist about the mind. All this has demonstrated is that inputless FSAs are an inappropriate formalism. The structure of an inputless FSA is quite trivial, and it is entirely the wrong sort of thing to describe or specify a mind. Inputless FSAs are almost never invoked in the theory of computation, precisely because of this triviality.

To see the triviality, note that the state-space of an inputless FSA will consist in a single unbranching sequence of states ending in a cycle, or at best in a finite number of such sequences. The latter possibility arises if there is no state from which every state is reachable. It is possible that the various sequences will join at some point, but this is as far as the "structure" of the state-space goes. This is an completely uninteresting kind of structure, as indeed is witnessed by the fact that it is satisfied by a simple combination of a dial and a clock.

This suggests that we need a more interesting formalism than inputless
FSAs. In particular, to put stronger constraints on structure we need to
move to FSAs with *input* and perhaps with output. The addition of
input changes the formalism from trivial to non-trivial. Where there is
input, there can be branching behavior. A formal state can be succeeded
by various different formal states, depending on the input. Furthermore,
the presence of input gives the formalism a kind of combinatorial structure.
Later states depend not just on a single state, but on a combination of
state and input.

This formalism is much more appropriate for capturing the dynamics of
cognitive systems. Humans do not have a single path of states along which
their lives are determined. Even if they do, as some fatalistic views might
suggest, this path does not exhaust their description. For any given sequence
of states that a human goes through, it remains the case that *if*
things in the world had gone slightly differently, they would have functioned
in an interestingly different way. Omitting this potentiality leaves out
a vital part of the description of human functioning.[*] A wind-up toy
or perhaps a videotape of my life could go through the same sequence of
states, but it would not be a cognitive system. Cognition requires at least
the possibility of functioning in more than one way.

*[[[Maudlin (1989) raises some very interesting questions about along these lines, questioning the relevance of counterfactual-involving conditionals to conscious experience. For instance, if one blocks the connection that supports some counterfactual conditional in a currently static part of the system, is it plausible that this could change or remove the system's conscious experience? Maudlin suggests that it could not. We have seen, however, that such conditionals are constitutive of computational organization. Using an elaborate construction, Maudlin makes an argument along these lines to the conclusion that cognition is not based in computation. This argument requires an in-depth treatment in its own right.]]]

It might be objected that there are or might be people who have effectively
*no* capacity for input and outputs - blind, deaf paralytics for instance
-- who nevertheless have minds, and are cognitive systems in a quite reasonable
sense. According to this objection, such people cannot be cognitive in
virtue of implementing an automaton with input or output, for they have
no such input or output themselves.

I think this would be to misdescribe the situation, however. These people
can be seen to implement an automaton with input and output. It remains
the case when they are in a given state that *if* they were to receive
a given input, *then* their state would transit appropriately. It
is just that they are currently not receiving any inputs (at best they
are receiving a single "null" input) due to the malfunctioning of their
sensory apparatus. Of course this means that the inputs in question have
to be understood as stimulations of the optic nerve, or of the visual cortex
or some other internal system, rather than as patterns of photons (mutatis
mutandis for other sensory modalities), but this is no problem. It simply
moves the boundary inward. The malfunctioning of their sensory system means
that their visual cortex does not often get stimulated, but *if* it
were to be stimulated, their internal state would change in interesting
ways. We can deal with outputs in a similar way.

It is this very sensitivity or potentiality that demonstrates that there
is a cognitive system present. If there were only one sequence of states
along which a system could "work", it would not be a person but a wind-up
toy. The sensitivity to change shows that real cognitive *mechanisms*
are present.

An alternative way to handle this sort of case will be outlined later, in terms of automata with internal combinatorial structure. Either way, it turns out that structureless FSAs without input or output are inadequate for the specification of a cognitive system.

Instead, Putnam puts forward a more limited result that is still significant. He argues that a finite-state automaton with input and output is realized by every physical system with the right input/output dependencies. That is, if the physical system gets the input and output right, it gets the FSA right.

To see that this is still significant, note that there are vastly different
FSAs with the same input/output pattern. Think of an FSA that outputs zero
on every input, for instance, and an FSA that upon receiving an input *n*
goes into an exhaustive calculation to determine whether the number is
prime, outputs zero if it is prime, and zero if it is not (it also outputs
zero on each step during its calculation). These FSAs have precisely the
same input/output dependencies. Nevertheless, one would think that most
simple systems that implement the first machine certainly do not implement
the second, with its vastly more complex internal structure.

Putnam also notes that if this result is correct, then (computational)
*functionalism* about mentality will imply *behaviorism* about
mentality. If mentality is dependent on implementing the right automaton,
and if an automaton is implemented by any system with the right input and
output, then mentality is dependent only on input/output patterns. But
functionalism is generally taken to stand in contrast to behaviorism, and
to lack many of behaviorism's problems. If Putnam's result is correct,
functionalism is no better off. As he summarizes:

Thus we obtain that the assumption that something is a "realization" of a given automaton description (possesses a specified "functional organization") is equivalent to the statement that it behaves as if it had that description. In short, "functionalism", if it were correct, would imply behaviorism! If it is true that to possess mental states is simply to possess a certain "functional organization", then it is also true that to possess mental states is simply to possess certain behavior dispositions! (pp. 124-125)Putnam's argument for this conclusion is a straightforward variation of his earlier argument. Given an arbitrary FSA, take a system

To evaluate this claim, we need to spell out conditions of implementation
for an FSA with inputs and outputs. An FSA with input and output is specified
by a a set of states, a set of inputs, a set of outputs, and a set of state-transitions
*(I,S) -> (S',O)* for each input/state pair *(I,S)*, specifying
the next state *S'* and the output *O* that will be produced
by that state and input. (Perhaps the output should depend only on the
previous state and not on the input, but the generalization does not hurt.)
We can then straightforwardly extend our previous account of implementation
as follows. Of course, we require that the relevant strong conditionals
are satisfied.

A physical system implements an FSA (with input and output) in a given time-period if there is a mapping(There will generally be some further restrictions on the mapping from inputs to inputs and outputs to outputs, but I will not go into this here.)ffrom physical states of the system onto formal states of the FSA and from inputs and outputs to the system onto inputs and outputs of the FSA such that: for every formal state-transition(I,S) -> (S',O)in the specification of the FSA, if the physical system is in a statesand receiving inputisuch thatf(s) = Sandf(i) = I, this causes it to transit into a states'such thatf(s')=S'and to produce outputosuch thatf(o) = O.

Does Putnam's construction satisfy this definition? It will have trouble
with reliability and with uninstantiated formal states, of course, but
as before we can stipulate that it contains a clock and a dial to avoid
that problem. There is still a serious problem. We have established that
the system transits appropriately in response to the inputs and outputs
that it receives. However, we have no guarantee of its transition behavior
if the inputs and outputs had been different. Again, in order to satisfy
the strong conditionals, it is necessary that *if* it had been in
a state/input pair that did not come up in the given run, then it would
have transited appropriately.

Nothing in Putnam's construction ensures that this condition is satisfied.
In fact there is every reason to believe that it will not be. If the sequence
of internal states *s_1, s_2, ...* is deterministic or reliable in
itself, as it will be in the clock/dial case and as nothing in Putnam's
stipulation rules out, then the system will produce precisely the *same*
transition behavior for *any* inputs. There is none of the sensitivity
that an FSA with input and output is required to have.

Once again, the strong conditionals go unsatisfied. Once again, this is because the structure of the FSA is not fully reflected in the structure of the physical system. All that is represented are a few state-transitions, those that come up on the run in question. If a state-transition in the machine table is not play a role in that run, then it will correspond to nothing in the structure of the physical system. The system therefore fails to implement the FSA.

Because of the combinatorial nature of these state-transitions, it is
not as easy to get around this failure as it was before. We cannot simply
disjoin states to our heart's content. For every state that takes part
in such a disjunction, it is required that for *every* input, it transits
appropriately. We cannot simply map the new physical state that follows
a given state and input onto the requisite formal state, as it will often
be the case that the same physical state can be produced as the result
of two distinct state/input pairs. Because of this, the iterative mapping
procedure described above will not be well-defined.

Still, this suggests yet another maneuver that might salvage something
of Putnam's argument. If we require that for every initial physical state
and every sequence of inputs, the system goes into a distinct physical
state, the mapping above will be well-defined. Furthermore, this condition
is not *too* hard to satisfy. It is satisfied by a system that keeps
a record of all its inputs, for instance.

Let us say a physical system contains a *input memory* if it has
a subsystem that goes into a distinct state for every possible sequence
of inputs (think of it as keeping a list of the inputs so far, perhaps).
It then turns out that every physical system with an input memory and a
dial implements every FSA with the right input/output dependencies.

To see this, denote states of the physical system by labels *[j,i_1,...,i_n]*
(where *n* can take any value from zero up). The dial state is represented
by *j*, and the sequence of inputs in the recorder is represented
by the sequence *i_1, ..., i_n*. To construct the mapping, assume
the dial is in fact set to 1, and associate state [1] with the appropriate
state *S* of the FSA. For every possible input sequence *i_1, ...,
i_n*, we associate physical state *[1, i_1, ..., i_n]* with the
FSA state that we get by starting at state *S* and feeding inputs
*i_1, ..., i_n* (or the formal correlates of these) to the FSA. If
there are FSA states that are not reached anywhere in this "tree", we pick
such a state, associate it with physical state [2], and start the process
again, and repeat until FSA states are exhausted. We map disjunctions of
physical states to formal states in the obvious way, and the construction
is complete.

It is easy to see that under this mapping, all the relevant strong conditionals
are satisfied. If the system is in a physical correlate of a given formal
state, and receives some input, it will always transit appropriately. As
long as we require that the system has the right input/output *dependencies*
(and not just the right input/output patterns in a particular run), then
the system will also satisfy the right strong conditionals concerning outputs.
It follows that the system implements the automaton.

By requiring the addition of an input memory, we have moved well beyond universal realization, but the result is still troubling. Input memories are not difficult to instantiate. A system that retains a separate mark for every input will achieve it, for instance. It follows for instance that any implementation of a simple zero-outputting FSA, supplemented with a dial and a input memory, will implement the complex primality-testing FSA. This result is quite counterintuitive, but it seems that we are stuck with it.

It also means that if AI is dependent on this FSA formalism, then functionalism
still *almost* reduces to behaviorism. We know that everybody with
the right behavior will realize a given automaton as long as they carry
a videocamera to record inputs and a dial in their pocket. If so, the functionalist
premise implies that any two behaviorally equivalent people will be mentally
equivalent, as long as they are carrying input memories and dials. The
caveat is not much help for non-behavioristic functionalism.

(There is an interesting alternative argument for the reduction of functionalism to behaviorism that Putnam does not mention. There is a plausible general principle about the computational basis of cognition:

(++) If a cognitive system implements two FSAsHowever, by the minimization principle for finite-state automata (Hopcroft and Ullman 1979, p. 67), any two FSAs with the same input/output dependencies implement a common simpler FSA with the same dependencies. Take any two behaviorally equivalent cognitive systems whose cognitive properties arise by virtue of implementing an FSA. By the reduction theorem and (++), these will have the same cognitive properties. It follows that if functionalism is not to reduce to behaviorism, we must either reject (++) or reject FSAs as the basis for cognition.)FandGboth of which are sufficient to produce the system's behavioral function, andGimplementsF, then the cognitive properties of the system arise in virtue of its implementingF(as the added structure ofGis just irrelevant implementational detail).

It is true that we are no longer in danger of panpsychism, as most systems will not even have the right behavior. However, the result may imply that every FSA will be implemented by a "giant lookup table" (see Block 1981) consisting of a tree with an output listed for each series of inputs. The matter is slightly unclear, as any such tree in our world will be finite; whether a finite tree implements the FSA depends on whether we allow the state-transition conditionals to fail for states at the end of a given time-period (that is, at the outer edge of the tree). But is a human being with a finite lifetime any better off? In any case, even the result that an infinite lookup-table would be as conscious as you and me is troubling.

The real moral of the above discussion is that even simple FSAs with
inputs and outputs are not constrained enough to capture the kind of complex
structure that computation and cognition involve. The trouble is that the
internal states of these FSAs are *monadic*, lacking any internal
structure, whereas the internal states of most computational and cognitive
systems have all sorts of complex structure. Generally these states are
divisible into components which interact locally and globally according
to complex principles. Just as the structure of the system is not captured
by a monadic state description, neither are the state-transitions captured
by a monadic state-change. There may be all sorts of local dependencies
that go into the functioning of such a system.

Turing machines and cellular automata are good examples of computational devices whose states have internal structure. In cognition, it is obvious that the brain has a highly complex structure, with its functioning consisting in a complex pattern of interaction among billions of neurons and other parts. There is also plausibly complex structure in cognitive processing at coarser levels, structure that is central to the explanation of human thought and behavior.

To capture all this, I will introduce the notion of a *combinatorial
state automaton*, or CSA. A CSA is much like an FSA, except that its
states have combinatorial structure. An internal state of a CSA is a *vector*
*[S^1, S^2, ..., S^n]*, where the *i*th component of the vector
can take on a finite number of different values, or *substates*. The
components of the vectors can be thought of by analogy with squares in
a Turing machine or cells in a cellular automaton. The substates correspond
to symbols in those squares or particular values for the cells. Inputs
and outputs can also have a complex structure if this is desired. State-transition
rules are determined by specifying for each component of the state vector
a function by which its new substate depends on the old overall state vector
and input vector (it will frequently depend on only a few "nearby" components
of these vectors), and the same for each element of the output vector.
The vectors involved may be finite or infinite, but I will stick to the
finite case.

The conditions for implementation of a CSA are analogous to those for an FSA, with appropriate modifications. The main change is that internal states of the physical system must be specified as vectors, where each element of the vector corresponds to an independent element of the physical system. I will stipulate that each element in such a decomposition corresponds to a distinct physical region in the system, although there are other alternatives. The same goes for the complex structure of inputs and outputs, if required. The definition of implementation is as follows:

A physical system implements a given CSA if there is a decomposition of its internal states into substatesOften the state-transitions of a CSA will be defined in terms of[s^1, s^2, ..., s^n], and a mappingffrom these substates onto corresponding substatesS^jof the CSA, along with similar mappings for inputs and outputs, such that: for every formal state transition([I^1,...,I^k],[S^1,...,S^n]) -> ([S'^1,...,S'^n],[O^1,...,O^l])of the CSA, if the system is in internal state[s^1,...,s^n]and receiving input[i^1,...,i^n]such that the physical states and inputs map to the formal states and inputs, this causes it to enter an internal state and produce an output that map appropriately to the required formal state and output.

It will be observed that (finite) CSAs are no more powerful that FSAs. For every CSA, there is an FSA that can simulate it. However, the implementation conditions for CSAs are much more constrained than those for the corresponding FSA. A implementation of a CSA is required to consist in a complex causal interaction among a number of separate parts. Not only do states have to be subdivisible, but the many state-transition conditionals imply that the system must have fine-grained causal structure than an implementation of the corresponding FSA might well lack.

Because of these constrained implementation conditions, CSAs are much less vulnerable to Putnam-style objections that FSAs. Unlike FSA implementations, CSA implementations are required to have complex internal structure and complex dependencies among their parts. For a complex CSA, the right sort of complex structure will be found in very few physical systems. What does the work is precisely the combinatorial nature of the states, through the requirement that the parts of an internal state are independently variable. This imposes a constrained structure of dependencies on the system that arbitrary systems have no hope of passing.

The CSA formalism also provides another solution to the problem of the
blind and deaf paralytic mentioned earlier. A non-trivial computational
basis for cognition in this case may be specified by a CSA description,
where the CSA need not have inputs and outputs. Even if a CSA lacks inputs
and outputs, its combinatorial structure enables it to evade Putnam's objections.
We can therefore argue that it is in virtue of implementing this CSA that
the person possesses mentality. Certainly such a person will still have
complex combinatorial structure in their brain, and there will be all sorts
of dependencies such as "*if* this neuron were in a different state,
then...". The complexity and sensitivity implied by this formalism can
therefore go a long way toward capturing the complex inner life of such
a person.

CSAs are a plausible candidate for principles of computational sufficiency,
then, due to the fine-grained causal structure they impose on an implementation.
They are also much more appropriate for the purposes of cognitive *explanation*
than FSAs. Where an FSA description of a process will consist in an unenlightening
sequence of monadic states, a CSA description of the same process will
provide detailed information about the internal structure and about patterns
of interaction between various parts, giving the potential for a much better
understanding of the process in question.

CSAs, more than many other computational formalisms, directly reflect certain properties of cognitive dynamics that such a formalism must handle, in order to provide a foundation for a theory of mind. Unlike monadic FSAs but like natural cognitive systems, their internal states have complex structure. Unlike Turing machines and cellular automata (at least as these are most commonly understood), these can take in input and produce output at every time-step, and area therefor quite suitable for the modeling of ongoing situated cognitive function. Nevertheless, the CSA framework is perfectly general. An FSA, a Turing machine, or a cellular automaton can be straightforwardly described as a CSA.

Given an account of implementation for CSAs, it is easy to derive an account of implementation for Turing machines, cellular automata, and so on. We simply have to translate one of these machines into the CSA formalism, which is straightforward. For an implementation of the machine in question, we simply require implementation of the corresponding CSAs. We can derive implementation conditions for programs in languages such as LISP and C by similar methods. Here the translation into the CSA formalism is more complex, but there is no problem in principle.

1. It turns out that even the CSA framework lets in some Putnam-style false implementations - of a sort. The false implementations here include no systems that we are ever likely to encounter, but they include certain astronomically large systems. Thus we still have counterexamples within the realm of logical possibility, if not within the realm of practical possibility. I give details in what follows.

In attempting to construct Putnam-style counterexamples, one might first
try an extension of the "input memory" strategy, by building in an input
memory into every component state. For a three-component FSA, for example,
one might try an implementation that sends state *[a,b,c]* with input
*I* into state *[aI, bI, cI]* (where *a*, *b*, *c*
are strings, and *aI* is a concatenation of *a* and *I*);
then, we map the strings *aI*, *bI*, *cI* onto the appropriate
CSA substates, depending on the substates that *a*, *b*, and
*c* mapped to. But it is easy to see that this "implementation" fails
to have the requisite combinatorial structure. When we recombine component
states here with other component states, we will get the wrong results.
For example, *any* state of the form *[a,-,-]* will transit into
one of the form *[aI,-,-]*, but the CSA state-transitions will almost
certainly require a different first component in the resulting state depending
on the other components in the original state.

For a Putnam-style counterexample to be possible, every component state
must be sensitive to every previous component state. The most straightforwad
way to do this is as follows: build an implementation in which state *[a,b,c]*
with input *I* transits into state *[abcI,abcI,abcI]* (where
*abcI* is a concatenation of *a*, *b*, *c*, and *I*).
Now, we are assured that for every resultant component state, there is
a unique candidate for the preceding state and input. Then we can construct
the natural mapping from strings *abcI* (in various positions) onto
substates of the CSA, without fear of troubles with recombination. A recombined
state such as *[a,b',c']* will transit into a new state with unique
component states in every position, each of which can be mapped to the
appropriate CSA substate.

But this sensitivity comes at a price. A system like this will suffer
from an enormous combinatorial explosion, getting three times bigger at
every time-step. If the strings that make up each component have length
*L* at one point, within 100 time-steps they will have length *3^{100}L*,
which is about *5.10^{47}* times larger. In a very short time, the
system will be larger than the known universe! CSAs that are candidates
to be bases for cognition will have many more than three components, so
the situation there will only be worse. Here, the "implementing" system
will reach the boundaries of the universe in number of steps corresponding
to a fraction of a second in the life of a brain. So there is no chance
that any realistic system could ever qualify as an implementation in this
manner.

It is easy to see that any Putnam-style implementation will suffer from
such an explosion. To achieve the requisite sensitivity "blindly", every
component state must be sensitive to the value of every preceding component
state. If a system had step *t* has *n* components each with
*k* possible values, then at *t+1* each component must be able
to carry *k^n* possible values, at *t+2* each component must
be able to carry *k^{n^2}* possible values, and so on. Given that
encoding *k^m* values takes a system whose size is proportional to
*m*, we can see that the size of the system must increase by a factor
of *n* at every time step.

No practically possible system has this structure, and it is likely that no physically possible system has it either, as this sort of unbounded explosion is probably incompatible with the physical structure of the universe. It follows that the threat of vacuity and of panpsychism have long since disappeared; the only physically possible systems that implement a non-trivial CSA will do so in virtue of having the right sort of fine-grained causal structure among their components. If the CSA is complex enough to be a plausible basis for mentality, the implementations will themselves be complex enough to be plausible candidates for mentality.

Still, the mere logical possibility of these false implementations is troubling. Intuitively, it seems that the exponentially-increasing system, for all its size, lacks the right sort of specific structure to count as really implementing the corresponding computation. Of course, one might bite the bullet and say that in a system that large, there is enough going on that we can truly find all computations implemented, just as one can find all possible books in Borges' Library of Babel. It might or might not follow that the corresponding minds could be found there too, depending on whether one takes the sufficiency of computational structure for mentality to hold with logical necessity or natural necessity. If it is only a natural necessity, then no conclusions follow from the consideration of a mere logical possibility, but if it is a logical necessity, the stronger conclusion would follow.

On reflection, I think that these systems should be ruled out as implementations, on grounds of lacking the right sort of causal structure. But this means that the account I have given of implementing a CSA is imperfect as it stands. It needs some sort of revision or addition, specifying an additional constraint on causal structure. To find this constraint, we need to reflect upon and analyse the features that the false implementations intuitively lack. One way to cash out the intuitions might be to add a "uniformity" clause, specifying that underlying each formal state-transition of a CSA there needs to be a uniform causal mechanism, as opposed to the highly disjunctive causal mechanism found in the false implementations. Another might be to add a causal relevance clause along the lines suggested before. But it is not obvious just how these suggestions should be spelled out in detail, so I leave the project as a challenge for the future.

In the meantime, we can rest reasonably content with the knowledge that the account as it stands provides satisfactory results within the class of physically possible systems. If a physically possible system implements a CSA on this account, it will do so by virtue of having the right sort of systematic, non-trivial causal dependencies between its component states. But the difficulties in the realm of logical possibility remain something of a challenge.

2. The second worry concerns an area in which the implementation conditions seem not too weak, but too strong. I refer to the constraint that each component in a CSA's state-vector must correspond to a distinct region in the physical system. (This constraint arises from the stipulated definition of a decomposition of a physical system.) One might think that the constraint is somewhat arbitrary. Why cannot components of a CSA be implemented by overlapping physical states, for example?

Some such independence condition on components is required, however.
Otherwise, the conditions for implementing a CSA would collapse into the
conditions for implementing the corresponding FSA, and the structure of
the CSA would be lost. To see this, consider an arbitrary CSA with an *n*-element
state vector, and the corresponding FSA obtained by collapsing each complex
state into a single monadic state, with appropriate state-transitions.
Let *T* be a system that implements the FSA under a mapping *f*.
To see that it implements the CSA under the unrestricted condition: let
*T^i_j* be the substate of the CSA where the *i*th element takes
on its *j*th value. Let *t^i_j* be the disjunction of states
of *T* such that *f(t^i_j)* is an FSA state corresponding to
CSA state *T^i_j* (there will be many such FSA states, of course).
Then *t^i_1, t^i_2, ...* will be the states of the physical system
corresponding to substates *T^i_1, T^i_2, ...* of the CSA, and the
implementation will hold under the appropriate mapping.

To see what is going on here, note that when the independence condition
is left aside, a decomposition of internal states of a physical system
into substates is just a set of non-maximal states *t^i_j* such that
the states *t^i_1, t^i_2, ...* (representing the various substates
of the *i*th element) are mutually disjoint and together exhaustive
of maximal states of the system, for each *i*. We can think of these
as states wherein a parameter has a particular value, with a separate parameter
for each element of the vector. If we allow each value of each parameter
to be determined by an arbitrary global mapping, we lose the sense that
the system is functioning by interaction between independent components,
and we therefore lose the extra structure that is vital to the nature of
a CSA.

In order to have a true implementation of a CSA, we must require that
the various parameters are in some strong sense *independent*, corresponding
to separable components of a system. The easiest way to do this is to require
that for a system to implement a CSA, the physical differences relevant
to the variation in a given parameter - must be restricted to a limited
physical region, with different physical regions for each element. That
is, the values of a "parameter" supervene on a distinct region for each
parameter.

It is possible, however, that a weaker "independence" condition could suffice. After all, not all existing computational systems have disjoint regions for each computational component. Witness systems with virtual memory, where the value of a given CSA "component" can be represented in various parts of the system depending on where there is free space, simply by using a pointer to the correct memory location. Cases such as this one might be handled in terms of more flexible independence conditions on components. An alternative would be to handle such cases by a two-stage definition of implementation, noting that the system implements some more complex CSA under the usual conditions, and the complex CSA bears an appropriate relation to the original CSA. The burden here would rest on the latter relation, but that could be analyzed purely mathematically (in terms of pointer values and the like), avoiding the problems with physical systems and causation.

In any case, the conditions that we have outlined provide at the very
least *sufficient* conditions for the implementation of an automaton,
admitting a wide class of devices that are appropriate, and excluding counterintuitive
"implementations" such as Putnam's. The question of how far these conditions
can be loosened without letting in inappropriate systems remains open.

From what we have seen here, this argument fails. Whether or not computational properties are intrinsic to physics, the implementation relation between abstract automata and physical systems is perfectly objective. Even if there is a correspondence between states of the wall and states of the Wordstar program, and even if we do not worry about inputs and outputs, it is almost certain that the wall states will not satisfy the relevant strong state-transition conditionals, as the wall will not possess the requisite causal organization. Implementation is a determinate matter, as we have seen, and it puts a very strong constraint on the relevant class of physical systems.

There is a weak sense in which computational descriptions are "observer-relative",
however. This reflects the fact that most physical systems will implement
more than one abstract automaton. Every system will implement a trivial
1-state CSA, for instance, most systems will implement a 2-state CSA, and
so on. So an observer is free to choose between a number of different computational
"descriptions" of a system. This poses no problems of vacuity, however.
The question of whether or not a given system is accurately "described"
by a given computational description remains an objective one. The vacuity
problem would arise only if every system impleented *every* CSA, and
that is not the case. A given complex CSA will only be implemented by a
small fraction of physical systems.

Indeed, it is a commonplace idea that a given physical system can implement more than one abstract computation. A single computer can simultaneously implement a number of programs, for example. One can even have a situation where a program is indirectly implemented, by implementing one program that implements another in turn (where the implementation relation between programs is cashed out in the natural way). It is natural to expect that the brain implements a large number of different automata, depending on what part of the brain we are focusing on and on the level of detail we are concerned with. Descriptions of brain processes in terms of implementations of these automata remain both objective and informative, although which description we appeal to at a given time may depend on our purposes.

There may even be instances in which a single system implements two independent automata, both of which fall into the class sufficient for the embodiment of a mind. A sufficiently powerful future computer running two complex AI programs simultaneously might do this, for example. In this case, we would naturally expect two minds to arise, not one. This suggests that if minds arise in virtue of implementing CSAs, then mental properties should be ascribed to the (system, CSA) pair, rather than to the system alone. Alternatively, it might be more in line with AI terminology to redefine the term "system" to denote the pair in question, in order that a single object can support more than one system. Either way, a given physical hunk of matter can be associated with more than one mind.

This suggests a natural response to Searle's (1980) "Chinese Room" argument. In the Chinese room, where a human is simulating a computer program, there are two distinct CSAs being implemented. The causal organization of the human's brain supports one CSA, and the causal organization between the marks on paper supports another one. We should not let the fact that the human is facilitating the causal dynamics of the second implementation blind ourselves to the fact that the causal structure is there - there are counterfactual-supporting state-transition relations between the marks on paper, just as there are between silicon chips or neurons - and that this structure is quite distinct from the structure in the first CSA implementation. We therefore have a situation analogous to that in which a computer implements two independent programs. There are two distinct causal and computational systems here, and we should expect two distinct minds to be associated with them.

This is only half the story, of course, and the easy half. The harder part is to take advantage of this bridge, showing that the physical properties that a computational description fixes are the properties in virtue of which minds arise. It is not implausible that minds arise in virtue of causal organization, but neither is it obvious. It is also plausible but not obvious that the discrete CSA framework can capture the precise causal organization (perhaps continuous, perhaps even non-computable) on which mentality depends. This second half is likely to be a long story, although see Chalmers (1994b) for my own attempt at putting things together. In any case, an account of computation and implementation clears the way.[*]

*[[[The ideas in this paper arose out of discussion and argument with a number of others, largely over the Internet. Thanks are due to David Joslin, Daryl McCullough, Joseph O'Rourke, Calvin Ostrum, and Jerry Seligman.]]]

Chalmers, D.J. 1994a. On implementing a computation. *Minds and Machines*
4.

Chalmers, D.J. 1994b. A computational foundation for the study of cognition. Philosophy-Neuroscience-Psychology Technical Report 94-03, Washington University.

Hopcroft, J.E., and Ullman, J.D. 1979. *Introduction to Automata Theory,
Languages, and Computation.* Addison-Wesley.

Lewis, D. 1973. Causation. *Journal of Philosophy* 70:556-67.

Maudlin, T. 1989. Computation and consciousness. *Journal of Philosophy*
86:407-32.

Putnam, H. 1988. *Representation and Reality*. MIT Press.

Searle, J.R. 1980. Minds, brains and programs. *Behavioral and Brain
Sciences* 3:417-57.

Searle, J.R. 1990. Is the brain a digital computer? *Proceedings and
Addresses of the American Philosophical Association* 64:21-37.