Examples of programmes on the reduced machine.

1) As a first example we will take the case of a programme for the calculation of a product by repeated addition. The numbers to be multiplied are held in lines /C and @C and the product eventually appears in :C. The line /C gets altered in the process. The instructions to effect this multiplication are in tube 0, as shown below. Lines DS and JS also have special contents as shown.

MULREP listing

[A typographical error has been corrected -- the instruction in line S/ was given in the original as /CT/, which disagrees with the check sheets given further below, and also simply doesn't work in context. Similar errors are endemic to the machine-code listings and commentary further on, and will be corrected without further comment. There is, however, yet another error which is duplicated on the check sheets, which I note below in square braces as usual.]

// /CT/            It is assumed that we have
E/ DSTI            the following fixed contents:
@/ D//H
A/ R//P                     DS ££££
MULREP        :/ /C/S                     RS ££££
S/ :CT/                     JS ////
I/ @CTI
U/ :C/S
¼/ JS/P            [should be DS/P?]
D/ A/
R/ @/

The names of the lines have been shown on the left of their contents.

In order that a routine may be of some use it is necessary that a statement of what it will do should be written down in an unambiguous form. For the above routine this might read

MULREP. The routine is entered at // and left at A/. Its effects are described by the equation $[\tp{:C}]'=[\tp{/C}][\tp{@C}]+[\tp{:C}]$

Here MULREP is just a code name for the routine. The above description of the properties of MULREP are to be understood to mean ``suppose that at some moment the machine contains the instructions of MULREP (i.e. lines // to R/ as above also DS, JS) and that control contains ££. The contents of the long lines at this moment will be described by writing their names in square brackets. Then the machine will afterwards eventually contain @/ in control. We denote the contents of lines at the first such moment by their names in square brackets with dashes. The equation $[\tp{:C}]'=[\tp{/C}][\tp{@C}]+[\tp{:C}]$ then holds, and also $[\nu]'=[\nu]$ unless $\nu$ is :C, /C, or one of the lines GK, MK, VK or on page 0 or 1."

We may make a number of remarks about this statement and the routine.

(a)

The contents of control which are mentioned are less by 1 than the values given for the entry and exit points of the routine. The reason for this should become clear to the reader if he refers to the method of obtaining I from C. The first step was to add 1 to the content of control.

(b)

We use the `dash notation' as we did with single instructions. In either case undashed expressions describe the state before the operation, dashed expressions values after.

(c)

The equation $[\tp{:C}]'=[\tp{/C}][\tp{@C}]+[\tp{:C}]$ should read rather
$[\tp{:C}]'=[\tp{/C}][\tp{@C}]+[\tp{:C}] ({\rm mod} 2^{40})$.

(d)

In squares where the character is irrelevant we leave blanks.

(e)

We have in this case arranged that after the operation is over the machine goes into a `loop' in which its states are repeated. This is called a `loop stop'.

(f)

The conditions concerning GK, MK, VK, and pages 0, 1 are regular conventions. None of these are actually altered in this case, but it is convenient to be able to alter pages 0, 1 (which contain the instructions in normal cases) and the other three lines, without being obliged to mention the fact in the official report on the routine.

We sometimes also use the notation $[\nu]_s$ to mean the content of the short line $\nu$.

It is of course important that some efforts be made to verify the correctness of the assertions that are made about a routine. There are essentially two types of method available, the theoretical and the experimental. In the extreme form of the theoretical method a watertight mathematical proof is provided for the assertion. In the extreme form of the experimental method the routine is tried out on the machine with a variety of initial conditions and is pronounced fit if the assertions hold in each case. Both methods have their weaknesses. This whole question is taken up in greater detail on pp. -. For the present let us just mention one form of verification which is described as `check sheets'. It is quite easy to follow out in detail, on paper, the behaviour of the machine for a few steps, or even a few hundred steps. If it were necessary to record the complete state of the machine after each instruction has been obeyed it would be a heavy undertaking. However it is quite sufficient to record the content of the accumulator and control, with the last instruction obeyed and any alterations that may be made in any lines of the store. This has been done on an accompanying sheet for the routine MULREP, taking the case of a multiplicand 27 and a multiplier 2. It is necessary to take a very small multiplier if the process is to come to an end in an reasonable time. It will of course be recognized that the process in question is not a practically suitable one for multiplication, and is only given as an example.

Check sheets

/ C   @///////
MULREP                      @ C   "///////
: C   @///////
/ /   / C T /     @///////
E /   D S T I     E///////
@ /   D / / H     E///////
: /   / C / S     E///////        / C   E///////
S /   : C T /     ////////
I /   @ C T I     "///////
U /   : C / S     "///////        : C   "///////
¼ /   J S / P     "///////
/ /   / C T /     E///////
D /   D S T I     ////////
@ /   D / / H     ////////
: /   / C / S     ////////        / C   ////////
S /   : C T /     "///////
I /   @ C T I     PE//////
¼ /   J S / P     PE//////        : C   PE//////
/ /   / C T /     ////////
E /   D S T I     ££££££££
@ /   D / / H     ££££££££
A /   R / / P
A /   R / / P

[Note a bug: The line at JS contains ////, i.e. zero, so the instruction JS/P should transfer control to E/, not // as shown here; this follows both from Turing's description and the behavior of the other two branches, D//H and R//P in the example.]

In the making of check sheets and such matters detail of procedure is of great importance. The work should be done on paper with quarter inch squares on which vertical lines are ruled in ink or printed. (However if forms are printed they should be such as suit the full machine.) All other writing should be in pencil. Each line refers to one state of the machine. In the first column is found the instruction number, and in the second the corresponding instruction. In the third is the content of the accumulator. In the fourth the line named in the instruction is repeated if that instruction results in the changing of that line, and in the fifth is the new content of that (long) line. These of course do not describe the state of the machine completely, but if one wishes to know the content of an other line one may glance up the fourth column until one finds the name of the line in question. If the recommendation to use only such long lines as have even numbers has been respected this glance will be sufficient. If however the recommendation has been ignored it will be necessary to take note also of the occurrence of the two lines whose numbers differ by one from that of the line in question. In the content of control, the instruction and the name of the altered line one complete quarter inch square is allowed for each teleprint character. For the contents of the accumulator and the store lines however two teleprint characters should be written in each square. This does not cause excessive crowding, and this economy of space becomes important with the full machine. The convention in check sheets about the content of control needs some explanation. If each line is regarded as corresponding to a prepulse the contents of the accumulator and of the store lines agree, and the instruction column gives the corresponding content for the P.I. line of the control tube. The first column however is not the content of control but the name of the line from which the instruction was taken. This will be a distinction without a difference in the majority of cases. The true value of C for each line is to be obtained by adding 1 to the value in the first column of the immediately previous line of the check sheets [unless the previous line was a taken branch].

Certain abbreviations may be permitted to reduce the amount of writing involved. When the content of the accumulator is unaltered it is sufficient to leave the entry in the accumulator column blank. When this content consists of the same character repeated eight times one may write the character once and large. When the content of control is increasing steadily by 1 one may leave it blank.

It will be noticed that blocks of consecutive lines may be copied direct from the routine to the check sheets.

As a second example we give the routine SUMPGA. All abbreviations are applied in its check sheets. The routine also has been set out in the standard manner. The first character of the line name is given in a narrow column between the two columns representing the store, and the second character, which is common to all the lines of the column, is given at the side of the column at its head. The manner of entering and leaving the routine has been satisfactorily described in the `official account' given with the routine. The manners chosen are quite appropriate for the reduced machine but not for the full machine. The methods used with the full machine are described on p. .

[SUMPGA listing]

SUMPGA
Enter at // leave R/
$[\tp{/C}]' = [\tp{/C}] + \Sigma_{r=0}^{31}[\tp{/+}+2r] (mod 2^{40})$
Method. Note. When about to obey VET/
with $2n$ in M/ we have
$[\tp{/C}]' = [\tp{/C}] + \Sigma_{r=n+1}^{31}[\tp{/+}+2r] (mod 2^{40})$
It is assumed that $[\tp{DS}]=\tp{!!!!!!!!}$
$[$Further note on operation: note that ://S at
/@ stores a long line, and therefore writes
instructions into both short lines :/ and S/$]$

[SUMPGA check sheet]

/ ¼   E   /
@ ¼   @   /
V D      /   T
/ C      /
/ /   V E T /    /¼TI/C/S
M E T I    VDTI/C/S
: / / S                     : /   VDTI/C/S
/ C T /       /
: /   V D T I       /   T
S /   / C / S                     / C      /   T
M E T /    VE  /
G E T N    ME  /
M E / S                     M E   ME  /
D S / H
/ /   V E T /    /¼TI/C/S
M E T I    MDTI/C/S
: / / S                     : /   MDTI/C/S
/ C T /       /   T
: /   M D T I       /   O
S /   / C / S                     / C      /   O
M E T /    ME  /
G E T N    GE  /
M E / S                     M E   GE  /
D S / H
/ /
.
.
.
M E / S                     M E   £
D S / H
R /

Exercise

[In the original, given before the listing and check sheet of SUMPGA; I presume this was an error on the part of the typist.] Provide a routine, with check sheets and official account, for the purpose of putting a number into `standard form', by multiplying it by a power of 2. A number $X$ is in standard form if $2^{39} \le X < 2^{40}$.