A computing human can do more than follow one algorithm to solve a problem. It can follow any algorithm, which is typically given to her in the form of instructions, and thus she can compute any function for which she has an algorithm. More generally, a human can be instructed to perform the same activity (e.g., knitting or cooking) in many different ways. Any machine, such as a loom, that can be easily modified to yield different output patterns may be called programmable. Being programmable means being modifiable so as to perform one’s activity in a different way depending on the modification. Programmability is an important feature of most computers. Computers’ activity is computing, so a programmable computer is a computer that can be modified to compute different functions.
The simplest kind of programmability involves the performance of specified sequences of operations on an input, without the characteristics of the input making any difference on what operations must be performed. For instance, (ceteris paribus) a loom programmed to weave a certain pattern will weave that pattern regardless of what specific threads it is weaving. The properties of the threads make no difference to the pattern being weaved. In other words, the weaving process is insensitive to the properties of the input. This kind of programmability is insufficient for computing, because computing is an activity that (ceteris paribus) is sensitive to relevant differences in input. This is because a mathematical function yields different values given different arguments, so any mechanism that is computing that function must respond differentially to the different input arguments so as to generate the correct output values. The way to do this is for computing mechanisms to respond differentially to the different types of symbols that make up the input and to the order in which they are concatenated into strings. Accordingly, programming a computer requires specifying how it must respond to different strings of symbols by specifying how it must respond to different types of symbols and different positions within a string.10
What counts as a legitimate modification of a computer depends on the context of use and the means that are available to do the modification. In principle, one could modify a calculator by taking it apart and rewiring it or adding new parts, and then it would compute new functions. But this kind of modification would ordinarily be described as building a new machine rather than programming the old one. So we should relativize the notion of programmability to the way a machine is ordinarily used. This will not make a difference in the end, especially because the kind of programmability that matters for most purposes is soft-programmability (see below), where what counts as a relevant modification is determined unambiguously by the functional organization of the computer.
Programmability comes in two main forms, hard and soft, depending on the type of modification that needs to be made to the machine for it to behave in a different way.
2.1.1 Hard Programmability
Some early computers—including the celebrated ENIAC—had switches, plug-ins, and wires with plugs, which sent signals to and from their computing components.11 Turning the switches or plugging the wires in different configurations had the effect of connecting the computing components of the machine in different ways, to the effect that the machine would perform different series of operations. I call any computer whose modification involves the rewiring of the machine hard programmable. Hard programming requires that users change the way the computing components of a computer are spatially joined together, which changes the number of operations that are performed or the order in which they are performed, so that different functions are computed as a result. Hard programming requires technical skills and is relatively slow. Programming is easier and faster if a machine is soft programmable.
2.1.2 Soft Programmability
Modern computers contain computing components that are designed to respond differentially to different sequences of symbols, so that different operations are performed. These sequences of symbols, then, act as instructions to the computer, and lists of instructions are called programs. In order to program these machines, it is enough to supply the appropriate arrangement of symbols, without manually rewiring any of the components. I call any computer whose modification involves the supply of appropriately arranged symbols (instructions) to the relevant components of the machine soft programmable.
Soft programmability allows the use of programs of unbounded size, which are given to the machine as part of its input. Since in this case the whole program is written down as a list of instructions, in principle a soft programmable machine is not bound to execute the instructions in the order in which they are written down in the program but can execute arbitrary instructions in the list at any particular time. This introduces the possibility of conditional branch instructions, which require the machine to jump from one instruction to an arbitrary instruction in the program based on whether a certain condition (which can be checked by the processing unit(s)) obtains. Conditional branch instructions are the most useful and versatile way of using intermediate results of the computation to influence control, which is a necessary condition for computing all computable functions.12 Since soft programmable computers can execute programs of unbounded size and use intermediate results to influence control, they can be computationally universal (see below).
There are two kinds of soft programmability: external and internal. A machine that is soft programmable externally requires the programs to be inserted into the machine through an input device, and does not have components that copy and store the program inside the machine. For example, universal Turing Machines and some early punched cards computers—such as the famous Harvard Mark I—are soft programmable externally.13
A machine that is soft programmable internally contains components whose function is to copy and store programs inside the machine and to supply instructions to the machine’s processing units. Internal soft programmability is by far the most flexible and efficient form of programmability. It even allows the computer to modify its own instructions based on its own processes, which introduces a final and most sophisticated level of computational control.14
A seldom-appreciated feature of internal soft programmability is that in principle, a soft-programmable computer can generate (but not compute) non-computable outputs, that is, outputs that are not computable by Turing Machines.15 If an internally soft programmable computer has the ability to modify its program in a non-computable way (e.g., at random), then in principle the execution of that (changing) program may yield an uncomputable sequence, and a computer that is executing that program may generate such a sequence. I say that the sequence is generated, not computed, because the relevant kind of program modification, which is responsible for the uncomputability of the output, is not itself the result of a computation—it’s not itself a process of transformation of input strings into output strings in accordance with a general rule that depends on the properties of the input string and applies to all strings.
Internal soft programmability has become so standard that other forms of programmability are all but forgotten or ignored. One common name for machines that are soft programmable internally, which include all of today’s desktops and laptops, is stored-program computers. For present purposes, however, it is better to use the term “stored-program” to refer to the presence of programs inside a mechanism, whether or not those programs can be changed.