In some previous blog posts I spoke about two definitions of the word "function". Loosely, the first definition described functions as descriptions of why you might need to use a thing. The second definition described functions purely as descriptions of what the thing does. Both posts conclude by reflecting that there is another way we use the word "function" - namely to describe how a thing is done.
As an aside. I want to note that the purpose of these posts is not to find the "correct" analysis of the term "function", just to talk through the different meanings it can have.
I plan to pick up the question of what it means to use the word "function" to describe how a thing is done. I'll do this by listing out some ways in which two things could be said to function in the same way, in the sense of carrying out the same process. I assume that this meaning is best explained by applying a mechanistic perspective, that is, one which describes things in terms of what kind of machine they are. I'm open to other perspectives but have struggled to find any other reasonable candidates.
It turns out that even you take this perspective there are a series of ambiguities about what you might mean.
In this post I list some different approaches you might take to describing the process something carries out in terms of what kind of machine it is. In each case I give a brief description.
This is intended to be an evolving post, where I will add more detail and references as I learn more about this topic.
State machines
These are the basic structures you study in an undergraduate computer science course on computability or automata. Examples include Finite State Machines, Pushdown Automata, and Turing Machines The Wikipedia article on finite state machines contains this cute diagram of a vending machine.
Broadly, state machines are described as a set of states and a transition function, which describes when and how the machine moves from one state to the next. The transition function may be deterministic or nondeterministic. Often state machines will also read some input or produce some output while undergoing their transitions.
Machine parts and linkages
The pure state machine account is quite abstract. One challenge to it is discussed in Chalmers' paper "does a rock implement every finite state automaton?". The issue here is that under a purely state machine account, there are some semantic tricks you can carry out to argue that a rock is performing every possible computation all at once.
Chalmers' solution is as follows:
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.
This amounts to seeing a machine as more than just a series of states, but rather as a linkage, or a series of parts - each of which has to play the right kind of causal role.
Symbolic machines
Some philosophers, notably Jerry Fodor, but also Douglas Hofstadter, argue that accounts that take place at the physical, mechanistic level take place at the wrong level of description for making sense of some machines. This account then argues that for some kinds of machine what matters is not the physical states of the machine, but the symbols that those states are able to encode.
What about continuous and physical machines?
All of the definitions described so far rely on abstract, digital machines. Some machines are only able to carry out their computations in virtue of being analogue, or making use of other physical effects that cannot be described purely using the formalisms above. Even if the strong version of the Church-Turing thesis is true, and for every possible physical computer there is an equivalent purely digital computer, it would not imply that the digital computer is doing the computation in the same way as the physical computer.