If you have encountered the phrase above, you have probably come to appreciate that the notion of "simple" instructions is not a very well-defined idea. This is partly the case because we fail to distinguish clearly between the instructions themselves, what is written down or depicted in some manner; and, the agent who is to carry out the instructions. If my agent is Picasso, the instruction "Paint a picture" will do; if my agent is Bach, the instruction "Compose a fugue" will do. For agents less experienced and expert in these matters, much more extensive instructions are required; and, it is not clear that we could even come up with a successful set of instructions for every task that we might like to see accomplished.

     In the early part of the 20th century there was a great deal of interest in rigorously analyzing the idea of a set of instructions and the notion of an agent that can carry out the instructions. One of the first things that we can note is that the idea of a set of instructions; and, that of the agent that carries out the instructions, are not separable ideas. The instructions always presume an agent with certain capacities.

     In mathematics, the idea of proof had undergone considerable refinement. Is there a sense in which proving something in an area of mathematics can be thought of as simply following instructions? If so, then how sophisticated must the agent be that can follow these instructions?

     Each area of mathematics had developed a notation for representing the objects of interest; and had usually developed procedures which if followed would yield some new expression in the notation. And, if all was well, it was said that the new expression 'followed from' the starting expressions. For example, in propositional logic we might start with two expressions such as p, p -> q, and then come up with some new expression, q. This rule of inference, modus ponens, is presumably a valid thing to do in the proposition logic.

     Part of the interest in studying instructions was to try to make as explicit as possible the notion of a proof -- what does it mean for one thing to follow from another? One possibility is that stating a proof depends very heavily on the agent's knowledge and capacity. The hope was that the opposite possibility would be true. Namely, that one could find a simple language for stating instructions that presumed only a marginally competent agent but was flexible enough to be used to state how to carry out proofs and compute functions. Note, we are not saying anything at this point about whether the agent could come up with the instructions for doing these things. Only that if someone comes up with the instructions, then the agent can follow the instructions.

     You have probably guessed by now, that this work formed the basis for the field that is now known as the mathematical study of computation. Computation was defined mathematically long before computers were built or Wall Street had the vaguest notion of their future economic importance.

     Now, we will introduce a bit of mathematical notation in describing this field...after all it is mathematics. But the ideas are quite intuitive and the notation is simply to try to guard against reading more into all this than is really there. For some reason, our culture both denigrates and elevates computers and computation. Some dry and boring notation will hopefully help us avoid either of these extremes.

The Intuitive Idea

     An instruction always involves an action that the agent is to carry out....place the medium size widget through the upper hole in the medium gray colored whatzit. The action takes place in some context - in this case a context of widgets and whatzits. In addition to an action, an instruction will often state a condition which must be satisfied if the action is to be carried out. The condition also refers to the context in which the actions take place. Usually, more than one instruction is required to complete the task. Consequently, we also need to worry about how to put instructions together. One simple way to do this is to order them.

     In addition to the set of instructions, we have the stuff that is provided at the start of the task....the widgets and whatzits. And, we also need some way of knowing whether we have successfully completed the instructions.

     Now, let's move from these intuitions to some mathematics to see how whether we can create a set of instructions suitable for a dumb agent.

The Idea of a Machine or Automaton

We introduce three kinds of things.

• We will need a set Q, which we will refer to as a set of control states. q0, ql,..., qf, and the like will be used to refer to elements of Q. Q is a finite set, but that's about all there is to say about this set.
• We will need a set S (usually represented by the capital Greek S and referred to as Sigma). s1, s2, si, and the like will be used to refer to elements of S. We will also include a special element, #, which will be used to refer to a blank. Again, this set is finite. And, you can think of it as the vocabulary used to refer to the domain.
• Finally, we will need a set of actions, A.This set is finite, and we will use R, L or some si to refer to an element of A. When we use si, this is a shorthand for the action of writing down si. We will use ak to refer to some element of A.

Now, we are ready to define the syntax of an instruction. An instruction is a tuple:

qi sj ak qm

The first two elements state a condition and the last two elements are the action portion of the instruction.

     Now, if this is what an instruction looks like, what sort of capacities does the agent who is to carry out these instructions require? Let's take each element in turn. Q is a finite set of control states. Our agent will have to be able to represent or "hold onto" as many different control states or names as are needed for a certain set of instructions. And, additionally, the agent will have to keep track of which of those control states is the current state that the agent is in.

     We also need some way to communicate input to the agent. Let's assume that the agent has a tape divided into squares where we can place an element of S on a square. We will assume that the agent is able to be at and have access to the contents of only one square at any point in time. What will be on the square will be an element of S or # and our agent must be able to recognize each of these elements of S. That is, if a and b are elements of S, then our agent must be able to tell the difference between a and b.

     These capabilities allow our agent to be able to recognize the condition side of the instruction. The agent needs to be able to store all of the instructions for a task and be able to find that instruction that matches the agent's current state and the element from S that is on the square of the tape where the agent's read head is currently located. If no such instruction exists, then the agent "hangs" or fails because there is no instruction that covers this condition. However, if there is an instruction for this condition, then the agent must follow the rest of this instruction. Recall that the third position is where the action is. We only need the agent to be able to execute three types of actions. One is to move one square to the right on the tape, R; another is to move one square to the left on the tape, L; and finally, to write one of the si on to the current square of the tape. The final capability is to change the name of its current control state from the name in position 1 of the instruction to the name of the control state in position 4 of the instruction and remember this as the current state.

     This is a rather simple agent and the instructions certainly seem quite clear. There are a few additional conventions that are needed in order to fully specify the idea of following a set of instructions. First, we need to make sure that our agent always starts in the same control state. We will call this control state, the start state and it is usually denoted as q0. And, we must insure that the agent always starts to the left of the square where the first input element has been placed. With these two conventions we have a well-defined start of a computation. Finally, we need some way for the agent to know that it has finished the instructions and needn't look for any more. This is accomplished by taking some non-empty subset of Q which are used to represent final states. Then, if the agent is in one of these final state, the agent "knows" that the computation is finished.

     The contents of the tape at the beginning of the computation is called the input and a subset of the content on the tape at the end of a computation that has successfully halted may be called the output. Together they are called an input-output pair, or an <I,O> pair. It is this pair then that specifies the result of following instructions to take some initial notation into some new or final notation.