Alan Turing: The Enigma The Centenary Edition

by Andrew Hodges

  After this flight of fancy, very typical of his conversation, he discussed various more serious proposals for storage, and commented that ‘the provision of proper storage is the key to the problem of the digital computer.’

  In my opinion this problem of making a large memory available at reasonably short notice is much more important than that of doing operations such as multiplication at high speed. Speed is necessary if the machine is to work fast enough for the machine to be commercially valuable, but a large storage is necessary if it is to be capable of anything more than rather trivial operations. The storage capacity is therefore the more fundamental requirement.

  He then continued to give a succinct definition of ‘building a brain’:

  Let us now return to the analogy of the theoretical computing machines with an infinite tape. It can be shown that a single special machine of that type can be made to do the work of all. It could in fact be made to work as a model of any other machine. The special machine may be called the universal machine; it works in the following quite simple manner. When we have decided what machine we wish to imitate, we punch a description of it on the tape of the universal machine. This description explains what the machine would do in every configuration in which it might find itself. The universal machine has only to keep looking at this description in order to find out what it should do at each stage. Thus the complexity of the machine to be imitated is concentrated in the tape and does not appear in the universal machine proper in any way.

  If we take the properties of the universal machine in combination with the fact that machine processes and rule of thumb processes are synonymous, we may say that the universal machine is one which, when supplied with the appropriate instructions, can be made to do any rule of thumb process. This feature is parallelled in digital computing machines such as the ACE. They are in fact practical versions of the universal machine. There is a certain central pool of electronic equipment, and a large memory. When any particular problem has to be handled the appropriate instructions for the computing process involved are stored in the memory of the ACE and it is then ‘set up’ for carrying out that process.

  His priorities were a large, fast memory, and then a hardware system that would be as simple as possible. The latter requirement was reminiscent of his ‘desert island’ mentality, doing everything with the least waste. But both features were to exploit the universality of the machine. His idea was always that anything in the way of refinement or convenience for the user, could be performed by thought and not by machinery, by instructions and not by hardware.

  In his philosophy it was almost an extravagance to supply addition and multiplication facilities as hardware, since in principle they could be replaced by instructions applying only the more primitive logical operations of OR, AND, and NOT. Indeed, the Colossus, when it was ‘almost’ programmed to do multiplication, had done just that. Since these primitive logical operations (absent from the EDVAC draft design) were incorporated in his plan for the ACE, he could indeed have omitted adders and multipliers, and still have had a universal machine. In reality, he did include special hardware to perform arithmetical tasks, but even there he decomposed the arithmetical operations into small pieces so that he could economise on hardware at the cost of more stored instructions. The whole conception was very puzzling to his contemporaries, to whom a computer was a machine to do sums, and a multiplier the very essence of its function. To Alan Turing, the multiplier was a rather tiresome technicality; the heart lay in the logical control, which took the instructions from the memory, and put them into operation.

  For similar reasons, his report placed no great emphasis upon the fact that the ACE would use binary arithmetic. He stated the advantage of the binary representation, namely that electronic switches could naturally represent ‘1’ and ‘0’ by ‘on’ and ‘off’. But that was all, apart from a terse statement that the input and output to the machine would be in ordinary decimal notation, and that the conversion process would have ‘virtually no outward and visible form’. In his 1947 talk he would elaborate on this briefest of all possible comments. The point was that the universality of the machine made it possible to encode numbers in any way one wished within the machine – in binary form, if that happened to suit the technology. It would be inappropriate to employ binary numbers in a cash register, because it would be more trouble than it was worth to make the conversions for input and output. On the universal ACE, however, no such conversion was required –

  This last statement sounds quite paradoxical, but it is a simple consequence of the fact that these machines can be made to do any rule of thumb process by remembering suitable instructions. In particular it can be made to do binary decimal conversion. For example in the case of the ACE the provision of the converter involves no more than adding two extra delay lines to the memory. This situation is very typical of what happens with the ACE. There are many fussy little details which have to be taken care of, and which according to normal engineering practice would require special circuits. We are able to deal with these points without modification of the machine itself, by pure paperwork, eventually resulting in feeding in appropriate instructions.

  Logical as this was, and certainly comprehensible to mathematicians, who had been familiar with binary numbers for three hundred years at least, the fact was that ‘fussy little details’ such as this were more of a headache for other people. To an engineer, in particular, it would come as a revelation that the concept of number could be separated from its representation in decimal form. Many people would see the ‘binary’ arithmetic of the ACE as itself a weird and wonderful innovation. Whilst he was perfectly correct in seeing this as a detail, it was a good example of his difficulties in communication with the kind of people who might fund, organise, and build his machine.

  But with such details disposed of, he concentrated his report upon the two really important things: the memory and the control.

  Considering the storage problem, he listed every form of discrete store that he and Don Bayley had thought of, including film, plugboards, wheels, relays, paper tape, punched cards, magnetic tape, and ‘cerebral cortex’, each with an estimate, in some cases obviously fanciful, of access time, and of the number of digits that could be stored per pound sterling. At one extreme, the storage could all be on electronic valves, giving access within a microsecond, but this would be prohibitively expensive. As he put it in his 1947 elaboration, ‘To store the content of an ordinary novel by such means would cost many millions of pounds.’ It was necessary to make a trade-off between cost and speed of access. He agreed with von Neumann, who in the EDVAC report had referred to the future possibility of developing a special ‘Iconoscope’ or television screen,* for storing digits in the form of a pattern of spots. This he described as ‘much the most hopeful scheme, for economy combined with speed.’ But in a prescient paragraph of the ACE report he also suggested an approach more on the home-made, ‘least waste of energy’ line:

  It seems probable that a suitable storage system can be developed without involving any new types of tube, using in fact an ordinary cathode ray tube with tin-foil over the screen to act as a signal plate. It will be necessary to furbish up the charge pattern from time to time, as it will tend to become dissipated. …It will be necessary to stop the beam from scanning in the refurbishing cycle, switch to the point from which the information required is to be taken, do some scanning there, replace the information removed by the scanning, and return to refurbishing from the point left off. Arrangements must also be made to make sure that refurbishing does not get neglected for too long because of more pressing duties. None of this involves any fundamental difficulty, but no doubt it will take time to develop.

  Lacking such cathode ray tube storage, he had to plump for the mercury delay lines, not with any great enthusiasm, but because they were already working. They held the obvious disadvantage, from the point of view of accessibility, of involving a delay. His plan was for a delay line to hold a s
equence of 1024 pulses, so it was like chopping up the ‘tape’ of the Universal Turing Machine into segments each of 1024 squares in length. It would take an average of 512 units of time to reach a given entry. However, this was an improvement upon the ‘papyrus scroll’.

  As for the other most important aspect of the machine, this was the ‘Logical Control’. It corresponded to the ‘scanner’ of the Universal Turing Machine. The principle was simple: ‘The universal machine has only to keep looking at this description’ – that is, at the instructions on its tape – ‘to find out what it should do at each stage.’ So the Logical Control was a piece of electronic hardware which would contain two pieces of information: where it was on the ‘tape’, and what instruction it had read there. The instruction would take up thirty-two ‘squares’ or pulses in a delay line store, and might be of two kinds, in the design that he proposed. It might simply cause the ‘scanner’ to go on to another point of the ‘tape’ for its next instruction. Alternatively, it might prescribe an operation of adding, multiplying, shifting or copying, of numbers stored elsewhere on the ‘tape’. In the latter case, the ‘scanner’ was to move to the next point on the ‘tape’ for its next instruction. None of this involved anything but the reading, writing, erasing, changing of state, and moving to left and right, that was to be done by the theoretical Universal Turing Machine working on the description numbers on its tape – except that there were special facilities added so that addition and multiplication could be achieved in only a few steps, rather than with thousands of more elementary operations.

  Of course, there was to be no physical motion when the ‘scanner’ went to fetch an instruction, or operate upon numbers stored on the ‘tape’; no motion but that of electrons. Instead, the control of the ACE would work by a process rather like that of dialling a telephone number, to reach the right place. Most of the complexity of the electronic circuits arose from the demands of this ‘tree’ system. There was also a complexity in the way that thirty-two half-way houses, ‘temporary storage’ locations consisting of special short delay lines, were provided for the shunting around of pulses. This was quite different from the EDVAC conception, in which all the arithmetic would be done by shunting numbers in and out of a central ‘accumulator’. In the ACE design the arithmetical operations were ‘distributed’ around the thirty-two ‘temporary storage’ delay lines in an ingenious way.

  The point of this complexity was that it increased the speed of operation. Speed took a slightly higher priority than simplicity. This was reflected also in the fact that Alan planned the pulse rate of the ACE to be a million a second, straining electronic technology to the full.* His emphasis on speed was natural enough, granted his Bletchley experience, in which speed was of the very essence, a few hours marking the difference between usefulness and pointlessness. It was also related to the universality of the electronic computer. In 1942 they had tried to get faster Bombes to cope with the fourth rotor; they had been saved by the German slip-up with the weather reporting signal system, but without this stroke of fortune they would have had to wait over a year for the machinery to match the problem. One virtue of a universal machine would lie in its ability to take on any new problem immediately – but this meant that it must be as fast as possible from the start. It would hardly be desirable to re-engineer a universal machine, for the sake of a special problem. The whole point was to get the engineering out of the way once and for all, so that all the work thereafter could go into the devising of instruction tables.

  Although the ACE was based upon the idea of the Universal Turing Machine, in one way it departed from it. The departure lay in the feature, at first sight an extraordinary one, that it had no facility for conditional branching. In this respect it might seem to lack the crucial idea that Babbage had introduced a hundred years earlier. For the ‘scanner’, or Logical Control, of the ACE could only hold one ‘address’, or position on the tape, at a time. It had no way of holding more than one, and then of selecting a next destination according to some criterion.

  The omission, however, was only on the surface. The reason for it was that it was a case where the hardware could be simplified, at the cost of more stored instructions. Alan set out a way in which conditional branching could be done without needing the logical control to hold more than one ‘address’ at a time. It was not the best technical solution, but it had the ment of a brutal simplicity. Suppose that it were wished to execute instruction 50 if some digit D were 1, and to execute instruction 33 if it were 0. His idea was to ‘pretend that the instructions were really numbers and calculate D × (Instruction 50) + (1-D) × (Instruction 33).’ The result of this calculation would be a instruction which would have the effect that was required. The ‘IF’ was effected not by hardware, but by extra programming. It was a device which had led him to mix up data (the digit D) with instructions. This in itself was of great significance, for he had allowed himself to modify the stored program. But this was only the beginning.

  Von Neumann had also seen that it was possible to interfere with the stored instructions, but had done so in only one very particular way. If a stored instruction had the effect of ‘taking the number at address 786’, then he had noticed that it would be convenient to be able to add 1 into the 786, so that it gave the effect of ‘taking the number at address 787’. This was just what was needed for working along a long list of numbers, stored in locations 786, 787, 788, 789 and so forth, as would so frequently occur in large calculations. He had programmed the idea of going to the ‘next’ address, so that it did not have to be spelt out in explicit form. But von Neumann went no further than this. In fact, he actually proposed a way of ensuring that instructions could not be modified in any other way than this.

  The Turing approach was very different. Commenting on this feature of modifying instructions, he wrote in the report: ‘This gives the machine the possiblity of constructing its own orders. …This can be very powerful.’ In 1945 both he and the ENIAC team had hit upon the idea of storing the instructions inside the machine. But this in itself said nothing about the next step, that of exploiting the fact that the instructions could now themselves be changed in the course of running the machine. This was what he now went on to explain.

  It was an idea that had arrived somewhat by chance. On the American side, they had thought of storing instructions internally because it was the only way of supplying instructions quickly enough. On the Turing side, he had simply taken over the single tape of the old Universal Turing Machine. But neither of these reasons for adopting stored instructions said anything about the possibility of interfering with the instructions in the course of a computation. On the American side, it was not pointed out as a feature of the new design until 1947.4 Equally, the Universal Turing Machine, in its paper operation, was not designed to change the ‘description number’ that it worked upon. It was designed to read, decode, and execute the instruction table stored upon its tape. It would never change these instructions. The Universal Turing Machine of 1936 was like the Babbage machine in the way that it would operate with a fixed stock of instructions. (It differed in that that stock was stored in exactly the same medium as the working and the input and output.) And so Alan Turing’s own ‘universality’ argument showed that a Babbage-like machine was enough. In principle there was nothing that could be achieved through modifying the instructions in the course of an operation that could not be achieved by a universal machine without this facility. The faculty of program modification could only economise on instructions, and would not enlarge upon the theoretical scope of operations. But that economy could, as Alan said, be ’Very powerful’.

  This original perception flowed from the very universality of the machine, which might be used for any kind of ‘definite method’, not necessarily arithmetical. That being so, the pulses ‘1101’ stored in a delay line, might well not refer in any way to the number ‘thirteen’, but might represent a chess move or a piece of cipher. Or, even if the machine were engaged upon arithme
tic, the ‘1101’ might be representing not ‘thirteen’, but indicating perhaps a possible error of thirteen units, or a thirteen in the floating-point representation* of numbers, or something else altogether, at the choice of the user of the machine. As he saw it from the start, there would be far more to adding and multiplying than putting pulses through the hardware adder and multiplier. The pulses would have to be organised, interpreted, chopped up, and put together again, according to the particular way in which they were being used. He dwelt in particular upon the question of doing arithmetic in floating-point form, and showed how the mere addition of two floating-point numbers required a whole instruction table. He wrote some tables of this kind. MULTIP, for instance, would have the effect of multiplying two numbers which had been encoded and stored in floating-point form, encoding and storing the result. His tables made use of the ‘very powerful’ feature of the machine, for he had it assemble bits of the necessary instructions for itself, and then execute them.

  But if a simple operation like multiplying floating-point numbers would require a set of instructions, then a procedure of any useful scale would involve putting many such sets of instructions together. He envisaged this not as a stringing together of tables, but as a hierarchy, in which subsidiary tables like MULTIP would serve a ‘master’ table. He gave a specific example of a master table called CALPOL which was to calculate the value of a fifteenth-order poly nominal in floating-point. Every time a multiplication or addition was required, it had to call upon the services of a subsidiary table. The business of doing this calling up and sending back of subsidiary tables was something which itself required instructions, as he saw:

  When we wish to start on a subsidiary operation we need only make a note of where we left off the major operation and then apply the first instruction of the subsidiary. When the subsidiary is over we look up the note and continue with the major operation. Each subsidiary operation can end with instructions for the recovery of the note. How is the burying and disinterring of the note to be done? There are of course many ways. One is to keep a list of these notes in one or more standard size delay lines …with the most recent last. The position of the most recent of these will be kept in a fixed TS [short delay line] and this reference will be modified every time a subsidiary is started or finished. The burying and disinterring processes are fairly elaborate, but there is fortunately no need to repeat the instructions involved each time, the burying being done through a standard instruction table BURY, and the disinterring by the table UNBURY.