What is Computation?

(In this post I will be presenting two dominant models for understanding what computation is. My understandings of these models has been heavily informed by a draft of Ian Horswill's paper, "What is Computation? (PDF)".

It is a first in a series that will be exploring relationships between computation and mind. Comments, questions, considerations, etc are moer than welcome.)

What is computation?

Horswill says that computation is an “idea in flux.” Meaning that while having some rough sketches in our shared cultural understanding regarding what computation means, we have yet not yet come to a definition (or definitions) that encompasses everything that we colloquially and technically call computing. Given this, he presents us with two dominant models of computation: functional and imperative.

The primary difference between functional and imperative models of computation is that functional models define computation as a transformation of a set of input values into a set of output values, whereas imperative models define computation a series of sequential commands (imperatives) that involve modifying computer memory or taking some action in the world. Imperative models don't require specified outputs in the sense that functional ones do.

Functional Computation:

Functions are consistent and specific transformations of a set of input values into a set of output values. They are specific in that, by definition to be considered a function, each combination of allowed input values only has one set of output values that the inputs can transform into. Or, putting it less formally: for each question a function is given it has specific answer.

Describing functions abstractly as relations between input and output values makes them independent of the particular way the output values are determined given the input values. The way this is done can be considered the function’s procedure. The function is also not dependent on the substrate that the procedure is constituted from and manipulates in order to make the necessary transformations. For the purposes of this essay, I will consider the function’s structure to be procedure and the substrate as a whole. Decoupling a function’s input/output transformational relations, the “what,” from “how” the “what” is produced allows for different procedures, including their substrates, which produce the same set of output values from the same set of input values to be considered behaviorally equivalent. In other words, procedures such as this can be considered to be computing the same function. The functional model of computing, then, is one in which different behaviorally equivalent procedures reliably produce (compute) the same output given some input. Computation, in a functional sense, is understood as these reliable transformations.

To make these ideas more concrete, let’s take the function of addition. Addition functionally can be defined as: uniting two or more numbers into one summed number. (For this example, I will be assuming only two numbers are be inputted at a time.) Note, nowhere in the definition is the function’s structure specified. It doesn’t matter if plastic buttons are being pushed on a calculator setting into a process a series of electrical voltage manipulations that then “write” Arabic numerals on a screen in e-ink on a screen, or if one is combining sets of rocks in buckets and then counting the sum. As long as the output values are the same given a set of input values then the processes can be considered to be doing addition. Also, how the symbols used to represent the output values are encoded – a bucket of rocks and Arabic numerals – is irrelevant. The same goes for the inputs. It is not the representations form, but what is being represented, it’s content, that matters for functional computation. For our purposes, we will consider the representational content to be information. Making what happens during computation, from a functional perspective, information processing. So, in a similar way that a function’s input/output relations are independent from how they are produced (its procedure), the input and output values are independent from how they are represented.

While, for familiarity’s & simplicity’s sake, I have been using addition as my example function, this should not give the impression that functions are necessarily transformations of numbers. For example, different cars given a set of inputs (pedal presses, geospatial location & orientation, wheel turns) that gave the same set of outputs (arriving at a specified location) could be considered functionally (behaviorally) equivalent. Again, notice functions are completely dependent on the inputs and outputs measured. The function’s structure can have many unmeasured inputs and outputs that are irrelevant to a function as defined. For example, notice that given how the above, let’s call it “get there”, function is defined that the details of whether or not the car uses an electric or gasoline engine is irrelevant.  A different function, “get there: fuel relevant”, that included fuel as an input and emissions as an output would potentially make this structural detail relevant.

The functional model’s focus on abstract input/output transformations alone, while ignoring the internal structures, can sometimes make it difficult to tell if different procedures are computing the same function, and thereby are behaviorally (functionally) equivalent. Returning to addition, because the set of input values include the set of all real numbers then, without examining a specific instantiation of a function structure, it is impossible to tell, using output alone, whether a function is actually addition or not.

To illustrate this, imagine a function, written by a deviant with a wicked sense of humor, in which a set of instructions (i.e. procedure) says to output the sum of every two numbers inputted except 843,728,2117 & 23.5483. In this case output: “Hah, gotcha, this isn’t the function ‘addition.’” The function, “hah, gotcha”, wouldn’t be addition because the output in the specified case isn’t the sum of the two numbers. It is not behaviorally equivalent to addition. Trying to determine this using input/output relations alone would be near impossible, however it could be determined quickly by glancing at its procedure. Potential cases such as this are innumerable and could vary in their degree of weirdness & sneakiness.

These considerations suggest, if not obvious, that while functions are defined by sets of inputs and outputs, not structure, there are bounds on the structures that can compute particular behaviorally equivalent functions. However, we shouldn’t yet lose hope for a functional understanding of computing. While, in many cases absolute certainty about whether or not a procedure is representative of a particular function can elude us, we can often get a working degree of certainty. Our prankster, with the “hah, gotcha” function, even if using an indecipherable encryption to encode his procedures to prevent us from examining their structure, is close enough to addition to work in almost all cases.

Imperative Computation:

Many of the considerations of the functional model of computation can be cross-applied to the imperative model. In the functional model when a computation is made an input is read in, transformed (assumedly using some structure), and then and output is written out. After the output is written the computation is finished. The focus is on the input/output relationship. The main difference between the imperative model and the functional model is that the imperative model doesn’t require computation to be of a function. That is, there doesn’t have to be a specified output which after it is written the computation stops.

Imperatives, or commands, are steps in a procedure that involve, according to Horswill, modifying memory or taking some action in the world. These imperatives, when strung together in a procedure, can be used to compute functions, but they can also be used to manipulate memory, non-functionally, in ways that we consider useful. The imperative model then would consider computation to be any sequence of commands (procedure) that mechanistically manipulates information. The strings that tie the functional model and imperative models of computation together are: a) they measure some behavior; b) use procedures to produce the behavior; c) the behavior is produced a deterministic fashion; d) different procedures can be thought of as behaviorally equivalent if the behavior is the same. If procedures are universally considered sequences of imperatives the functional model, using procedures to compute their outputs given a set of inputs, could be considered a sub-model of the imperative one.

The imperative notion of computing, therefore, is broader than the functional one. This broadness can account for its strengths and weakness. It is strong because it covers a greater ground of what we, in an everyday sense, think of as computing. For example, a video game that keeps running as long as it is loaded would count as computing under the imperative umbrella, but may not under the functional one. It could, theoretically, run forever with no specified output. (Note: This may not be doing the functional model justice. One could consider each time interval an output that was produced by the inputs during the initiation of, and further along into, the program. This given, the distinction may still be pragmatically useful.) However, this same broadness is a source of a shortcoming. Unlike the functional, where the behavior (the transformation from input to output) is clearly defined, it can be difficult in the imperative model to specify exactly what behavior we are supposed to be measuring. This can also make determining behavioral equivalence difficult.