We now begin a study of chapter 8 in the textbook on the theory of computing (or the theory of computation, as in the title of this chapter). The theory of computing addresses questions at the heart of computing science, such as
Some answers to the first two of these three questions are discussed in chapter 8.
We will rephrase the first question above, "what is computing?", as "what is a computer program?". However, we will need to think of computer programs in a general or abstract way, i.e. we do not want to tie our concept of computer programs to a particular computing technology, since computing technologies may change; we want our concept to transcend the time and place in which we live. We will use the term abstract program to refer to this general concept of a computer program. (The textbook sometimes uses the term abstract machine to describe the same concept, but it seems to use the term inconsistently.)
We need a definition of abstract program that captures, in some sense, the idea of an algorithm. A brief definition of algorithm was given at the beginning of topic 11, but a fuller definition is given below:
An algorithm (also known as an effective procedure or a mechanical process) is a set of instructions or rules for accomplishing a particular task in a finite amount of time.
Two definitions of an abstract program are given in section 8.2 of the textbook. The first of these is called a black box definition in that it ignores what is going on inside the program (i.e. it ignores the instructions or rules used by the program, placing them inside a metaphorical black box so that they are invisible from the outside) and focusses instead on the relationship between the program's inputs and outputs. The second is called a clear box definition in that the rules by which the program operates are clearly described.
These definitions require some explanation. In the black box definition, we avoid having to consider the many different types of input and output data and their possible meanings by representing this data using binary strings. A program that takes binary input strings and produces binary output strings is (possibly) only a partial function in the sense that it may run forever for some binary input strings and, therefore, produce an undefined result (instead of a binary output string) for some inputs. Furthermore, the black box definition claims only that a program is an input/output matching; it does not claim that every input/output matching is a program (and, in fact, it is shown in section 8.3 of the textbook that at least one input/output matching is not a program in the Turing machine sense). Therefore, the black box definition is far less useful to us than the clear box definition.
To understand the clear box definition, we need to define exactly what a Turing machine is and how it works. This is done below.
A diagram of a Turing machine (TM) is given in figure 8.3 of the textbook. A TM basically consists of a tape (with a left end, but unlimited length to the right), and a control device with a read/write (r/w) head capable of reading and writing symbols on the tape. The operation of the control device is determined by a set of rules based on the possible states of the machine and the symbols read from the tape. Each rule is of the form
(C, R, N, W, M)
where
C = the current state of the TM
R = the symbol currently being read by the TM
N = the new state to be adopted by the TM
W = the symbol to be written by the TM (on top of the symbol read)
M = the move, L or R (left or right), to be made by the r/w head
We will assume that the initial state of a TM is always 1, and that all other states are positive integers. The symbols that may appear on the tape are arbitrary, but usually they belong to a small alphabet such as {0, 1, b}, where b represents a blank. The action of a Turing machine at any time is completely determined by its current state and the symbol currently being read; these two items determine the new state of the machine, the symbol written on the tape, and the move made by its read/write head. Note also that a Turing machine may run forever (i.e. it might not halt for some or all of its possible initial input tape contents). In this sense, it is unlike an algorithm (which must accomplish its task in a finite time) and like a computer program (since a program, owing to an infinite loop, may also run forever, or at least until the computer operator terminates it).
Let's consider a simple TM for performing the addition of two positive integers. For convenience, the integers to be added will be represented in unary format, whereby a positive integer n is represented by a string of n consecutive 1s. The TM's tape initially contains the two integers separated by an exclamation mark (!), e.g. to perform the addition 3+5, the initial contents of the tape are
111!11111
The TM for adding these numbers need only write a blank (b) over the first 1 on the input tape and a 1 over the exclamation mark (!), giving
b11111111
as the final contents of the tape, representing (in unary format) the sum 8. A TM with the following three rules performs this addition:
(1, 1, 2, b, R) (2, 1, 2, 1, R) (2, !, 3, 1, R)
Since the initial state of the a TM is 1, the first rule above causes the TM to go to state 2 and to write a blank (b) over the first 1 on the input tape. The second rule causes the TM to move right, in state 2, over any sequence of 1s. The final rule causes the TM (still in state 2) to go to state 3 and write a 1 over the exclamation mark (!) when it is read. The TM will halt in state 3 since there are no rules telling it what to do in this state. Note that the behaviour of a TM is not affected by the order in which its rules are presented. Each rule of a TM is like an if statement, telling it what to do in a particular situation.
The AEOnline materials provide a Turing machine simulator named ITM (a pun on IBM). You can run the adding TM discussed above by opening the file add.dat, located in the
Z:\courses\csc110\chapter8 folder, using the
ITM applet.