Basic Structure of a Digital Computer
[Part One]

Go to the HOMEPAGE of this site, so that you can navigate through it, and find my e-mail address.

If your browser does NOT support FRAMES (The current page does not have them, but others do), please click HERE . You will arrive at the HOMEPAGE of this site (without FRAMES). From there you can navigate through this website by means of the links in the CONTENTS-section.

                                         to bottom  


This Essay is meant as a preparation for the next Essay, which is about the ontological status of ARTIFICIAL LIFE (a-life), mainly that brand of a-life that is computer-generated. For an assessment of the ontological status of the creations of a-life it is paramount to know something about the general and basic structure of a computer, in our case a digital computer. Only after possessing some insights into the structure of these interesting machines can we rationally speak about the role and nature of the substrate of artificial-life creatures in order to assess the reality-status of those creatures.
For this purpose we do not need a description of all the details and design features of modern computers. Just a general lay-out of the very basics is necessary. I will devote much attention to the general workings of Boolean logic (hardware) circuits (but only a very simple example of them will be treated of here [Part Two of this Essay]). Thereby it is important to realize that the computer-hardware is a physical device that obeys the laws of physics. Further one must realize that a computer can simulate phenomena of the outside world, and although these simulations are not the same as the phenomena which are being simulated, those simulations are something in their own right. What they are (in their own right) depends on their general and detailed structure and/or behavior. In the next Essay (about artificial life) these subjects will be adressed fully.
In Part One of this Essay I will treat of the general CONCEPT of a digital computer, in terms of Turing machines. A concept already worked out in the 19-thirties.
There are two main types of computers, analog computers and digital computers. Digital computers are discrete machines having access to a finite number of internal states only, while analog machines have access, in principle, to an infinite number of internal states and could therefore be expected to outperform digital machines. Examples of this enhanced ability of analog computers would include solving halting-problems (i.e. in principle be able to determine in advance whether any program, fed into the computer, will or will not yield a definite result in a finite number of steps), and generating non-computable numbers. For a digital computer one cannot write a test-program that could determine for any other program, to be run on such a computer, whether that program (to be tested) will, when run, give a definite result after a finite number of steps. Also a digital computer cannot compute certain numbers (so called non-computable numbers).
Further we have serial machines and parallel machines. While a serial machine can only perform one computational step after another, a parallel machine can execute more than one such steps simultaneously. Parallel machines accordingly consist of more than one processor, which operate in harmony. Many processes in Nature are in fact proceeding in a parallel fashion, and can therefore adequately be simulated by such machines. But it is possible to simulate such a parallel machine on a serial machine.
In our discussions and explanations we will confine ourselves mainly to DIGITAL SERIAL COMPUTING MACHINES, but the principle (concept) expounded covers parallel machines as well.

The Digital (serial) Computer

The main components of a digital computer are : Besides these main components we find slow secondary storing divices, such as floppy disks and hard disks. These can contain data and programs that can be used as input. They also can receive output. Further there may be one ore more control units that check and regulates information-flow (information-traffic).

Figure 1. Von Neumann's computer architecture -- the layout of a typical serial machine. Except with respect to input and output devices, the information-flow is in a back-and-forth fashion.

To program such a computer, in order that it will solve a certain problem or generate some desired result, the programmer first writes an algorithm, which is a solution of the problem in the form of a sequence of steps, written in ordinary language. This algorithm is then coded into a suitable programming language that will enable the computer to ' understand ' and successfully execute the corresponding instructions. Usually, this involves one of the ' higher ' programming languages, so called because they are reasonable close to human language. But because the Central Processing Unit (CPU) is composed of a set of Boolean logic circuits, it is capable only of performing elementary arithmetic operations such as addition, subtraction, multiplication, and so on. Thus the original programming language fed into the computer must be first converted by means of an interpreter (translates one line of code and executes it, then translates the next line, etc.), or a compiler (translates the whole program and then executes it) into a machine-readable assembly language (instructions, coded in this assembly language are then directly translated into machine-code, that consists of the electronical equivalents of 0's and 1's) . Only then the machine is able to execute the fed-in instructions.
The input is coded up in memory, which is a grid of electronic on-off switches. The processor, which is a chip of integrated circuitry, alters what is in the memory, resulting in a different on-off pattern of switches, and then the output decodes and displays the new contents of the memory. So the actual computation consists of the processor's activities on the memory. Accordingly the processor and the memory stand in mutual contact with each other.

Turing Machines

Now exactly what is it that the processor has done? [See among other sources, RUCKER, Mind Tools, 1988]
  1. The processor is able to read the symbol stored in whatever location it is looking at. That is, it can tell if the switch is set to ON or OFF.
  2. The processor is able to change the contents of the memeory location it is currently scanning. That is, it can change the position of the switch it is observing.
  3. The processor is able to move its attention to a new memory location.
  4. The processor is able to change its internal state. That is, it can change its predilections about what to do next.
In fact this is a concept of what a computer does, outlined by TURING in 1936. A machine, stripped to the bare bones of this concept is nowadays called a Turing Machine.
A Turing machine [See, among others, PETERSON, 1988, The Mathematical Tourist, pp. 194 ] consists of a Head that can scan a Tape, and that can be in one out of a finite number of internal states. Such a Tape, which can be interpreted as memory, consists of a linear arangement of cells. Each cell can itself be in one of a finite number of cell-states. Because we are aiming at electronic computers which have a memory board consisting of on-off switches, we consider cells which can be in only one out of two states, ON or OFF, which can be represented by the cell being BLACK or WHITE respectively. The Head of the Turing Machine can READ the cell (state) on which it is currently placed (we can conceive of the Head being moved along the Tape, or the Tape being moved over the Head), i.e. it can determine if that cell is BLACK or WHITE. If the cell is BLACK it can erase the black, or leaving it BLACK. If the cell is WHITE it can leave it like that or make it a BLACK cell. After this the Head can move one cell to the left or one cell to the right. When this is accomplished the machine can either stay in the same internal state, or change its state into another. After it has performed a certain number of such tasks, the machine will turn itself off.
An action table stipulates what a Turing Machine will do for each possible and relevant combination of cell-state (BLACK or WHITE) and internal state [ In a real (i.e. physical) computer this table is in fact one or another Boolean function, fed into the machine as a code, and will then be physically represented by an electrical circuit that gives a certain output depending on its input (for example numbers -- ultimately in the form of an on-off pattern of memory elements)]. The first part of the instruction specifies what the machine should write, if anything, depending on which cell-state (BLACK or WHITE) it encounters. The second part specifies whether the machine is to shift one cell to the left or to the right along the tape. The third part determines whether the machine stays in the same internal state or shifts to another state, which usually has a different set of instructions.

Suppose [PETERSON, pp. 195] a Turing Machine must add two integers (this accordingly is a special Turing Machine -- out of many possible -- that specializes in executing this particualer task, the adding of any two whole numbers). We can represent such a whole number by a consecutive series of BLACK cells, for example the number 3 can be represented by three consecutive BLACK cells on the tape, and the number 4 can be represented by four such cells.
If we now want to ADD these two numbers, we write them both on the tape, with a WHITE cell in between. When we think of the cell-states as being either OFF (= WHITE) or ON (= BLACK), then our INPUT will be written on the tape as follows :


In order to ADD these numbers the machine fills in the blank cell, giving :

...00011111111000... ,

and then goes to the end of the string (of 1's) and erases the last 1 in the row, which results in the correct answer, namely a consecutive series of seven 1's :


An action table is needed to instruct the machine how to perform this addition (The foregoing was just an algorithm, a recipe, that still must be translated into an executable program). The table's first column gives the machine's possible internal states, and the first row lists all the cell-states being used (in our case the cell-states BLACK and WHITE).

                                     Cell-state encountered

                               BLACK                            WHITE

(Internal) State 0     move right, get in state 0.    put BLACK, move right, get in state 1. 

(Internal) State 1     move right, get in state 1.    move left, get in state 2.

(Internal) State 2     erase, stop.

Each combination of (internal) State and Cell-state specifies what, if anything, needs to be done to a cell, in which direction to move after the action, and the (internal) state of the machine, that is, which set of instructions it will follow for its next move.
The above action-table can now be written down in a more compact way by coding the details as follows : BLACK = X, WHITE = B, move right = R, move left = L, for example 1XR2 means :
IF the internal state of the machine is 1, and the cell encounered is BLACK, THEN the Head of the machine must move to the next cell on the right, and the machine must enter internal state 2. Two other examples of instructions are, say, 2BX2, or 2BL3, they signify the following :
2BX2 : IF the internal state is 2, and the encountered cell is WHITE, THEN the Head must make that cell BLACK, remain in state 2.
2BL3 : IF the internal state is 2, and the encountered cell is WHITE, THEN the machine must move to the next cell to the left, and go into (internal) state 3.
So we can now write down the above action-table (i.e. the program) more compact :

  1. 0XR0
  2. 1XR1
  3. 2XB stop
  4. 0BXR1
  5. 1BL2

Each one of these five instructions implies, among other things,

If this (new) internal state is, say, 1, and the machine has settled on a, say, BLACK (= X) cell, then, in the action-table, an instruction must be looked-up that begins with 1X. This is instruction (2) of the action-table : 1XR1. If no such entry is to be found in the action-table, or if there are more than one such entries, then (it is stipulated that) the machine will turn itself off, (it is so stipulated) because no definite course could then be follwed. The input pattern (in our example) is BLACK, BLACK, BLACK, WHITE, BLACK, BLACK, BLACK, BLACK, or, equivalently,
X X X B X X X X. With the above action-table we can now compute the sum, i.e. 3 + 4 = 7.
To begin with, the machine is set in state 0 and is placed at the BLACK (= X) cell farthest to the left. After execution of (1) [ See the above table ] it finds itself in state 0 and has moved one cell to the right, this new cell is again BLACK (= X). So it must execute (1) once more, resulting in having shifted one more cell to the right which is also BLACK (= X). Again it must execute (1), and this results in encountering the WHITE (= B) cell and still being in internal state 0. So next it must execute (4), which means it must make that cell BLACK, move one cell to the right and go into internal state 1. By doing so it encounters a BLACK cell, so it must execute (2), resulting in moving one cell to the right and remaining in state 1. It thereby finds again a BLACK cell, so it must again execute (2), resulting in finding another BLACK cell to the right. Again it must execute (2), resulting in encountering the last BLACK cell to the right. Once again it must execute (2), now resulting in finding a WHITE cell to the right. This implies that the machine must now execute (5). According to that instruction it must go one cell to the left and go into internal state 2. There it finds a BLACK cell. This implies that it must now execute (3), which means that the Head must make the encountered cell WHITE, and then turn itself off.
The result is a string of seven consecutive BLACK cells : X X X X X X X. With this the calculation is completed.
The figure below pictures the computational steps of this calculation :

Figure 2. At each step, a Turing Machine may move one space to the left or right. By following a simple set of rules, this particular machine can add two whole numbers. The strategy of this particular machine is : Starting with separate groups of -- as in the example -- three and four BLACK cells, and ending up with one group of -- as in the example -- seven BLACK cells.

The same action-table can generate the sum of any two whole numbers, no matter what their size, as long as it is finite. But adding two numbers such as 49985 and 51664, by itself, would require a tape with at least 100000 cells. To be capable of adding any two numbers, the tape would have to be infinitely long, which does however not mean an actually infinite tape, but only a potentially infinite tape, which means that what ever the length of the tape already is, we can always add some tape if necessary.
Similar tables can be worked out for subtraction and for practically any other mathematical operation. The sole condition is that the number of internal states of the machine, and the number of different cell-states listed in the action-table, is finite, which ensures that a routine, mechanical process can do the job.

For every calculation a digital computer can perform there is a corresponding Turing machine which can do that same calculation. Let us consider some more of such Turing Machines. In expounding them we will use the above notation :

The input is one or more BLACK cells. At the start (i.e. when the machine is switched on) the machine is placed at the left-most BLACK cell, and enters (internal) state 1. Further we will describe the instructions using only strings of four of the above defined symbols, so a typical instruction could read :
2XB3, which means : IF the machine is currently in state 2 and reads a BLACK cell, THEN it must erase this black, i.e. it must make the cell WHITE, and must enter state 3.
Or (a typical instruction) could read :
1BL1, which means : IF the machine is currently in state 1, and reads a WHITE cell, THEN it must move one cell to the left, and remain in state 1. So the first two symbols together constitute a condition to be satisfied, and the last two symbols together constitute an action, that must be taken if and when that condition is indeed satisfied.
If and when the machine reaches an instruction that tells it to enter state 0, it turns itself off. Not every machine (i.e. not every program or action-table) reaches an instruction that leads to 0. Some machines go into various sorts of endless behavior loops, and so do not yield a definite result. It is not at all unusual for a Turing machine to run forever. TURING's theorem says that there is NO general method that could determine in advance whether a particular machine (i.e. a particular program for such a machine) will run forever -- and consequently not yielding any definite result in a finite amount of time -- or that it will calculate a result and turn itself off. Here is an example of a Turing machine's action table that results into a loop and never gives any output at all :


At the start the machine enters state 1 and reads a left-most BLACK cell. So it must execute the first instruction, which means it must go one cell to the left and enter state 2. There it encounters a WHITE cell, so it must now follow the second instruction, which means that it must move one cell to the right and enter state 1. There it finds a BLACK cell, so it must follow the first rule, i.e. it has returned to the original situation, and from now on these actions will be repeated ad infinitum.

If we denote the number of the (particular) machine's non-zero (internal) states with K, then the machine's total program contains at most 2K instructions, each of which begins with one of the 2K possible prefixes 1B--, 1X--, 2B--, 2X--, ..., KB--, KX--. This follows from the fact that any time the machine is on, its state is one of the numbers 1, 2, ..., K, and the cell it is examining is either a B or an X. Each " -- " can be filled in 4(K + 1) ways, because, for to fill in the last entry of " -- " we have K + 1 possible internal states (now including the 0-state), and for to fill in the first entry of " -- " we have four possible symbol-types : X, B, L and R.
This makes for [4(K + 1)]2K possible programs (action-tables) in all, i.e. 4(K + 1), multiplied with itself 2K times.
Let me explain this last assessment.
When we have, say, three symbol-types, a, b, c, and when we want to make strings, each consisting of four such symbols, then we can ask how many such strings are posible.
For the first entry of such a four-symbol string we have three possibilities, a, b, or c.
For the second entry we also have three possibilities, a, b, and c.
So each of the possible three first-entries has three possibilities with respect to the second entry. That makes 3 x 3 = 9 possibilities.
For the third entry of the four-symbol string we again have three possibilities, a, b, and c.
So each of the nine possibilies regarding the first two entries has three possibilities regarding the third entry, so that makes 3 x 9 = 27 possibilities.
For the fourth (and last) entry of the string we again have three possibilities, a, b, and c.
So each of the twenty-seven possibilities regarding the first, second and third entries has three possibilities regarding the choice of the fourth entry of the string, and that makes 3 x 27 = 81 possibilities in total four a four-symbol string using three different kinds of symbol.
81 equals 3 x 3 x 3 x 3 = 34. It is easy to generalize on that :
The number of possible strings, consisting of S different types of symbols, and with a length of L symbols equals SL.
Applying this to the assessment of the number of possible Turing Machine programs (action-tables) in dependence on the number of non-zero internal states, we can say the following :
A Turing Machine program can be considered as a string of instructions. Each instruction, like for instance 2XR1, can be interpreted as a conditional statement of the form IF .... THEN. The first half represents the condition to be satisfied, the second halve represents the instruction proper. In the above example 2X is the condition, and R1 is the action to be taken (go one cell to the right and enter internal state 1). We have 4(K + 1) different kinds of instruction proper, which we can call ' symbols'. These symbols must be carried by at most 2K instructions. So the length of the symbol-string is 2K. It follows that the number of strings with length 2K, consisting of 4(K + 1) different symbol-types equals
[4(K + 1)]2K, and this is thus the number of possible Turing Machine programs.
This is quite a large number even for small K's : for K = 2 it is already about twenty thousand, but the number of possible K-state Turing Machines is finite, and for large K, the value is roughly the same size as K2K. Of course an instruction (in a program),like for instance 3XB2, can be used more than one time during the running of the program.
Turing Machines can just do about anything. It can perform the same numerical tasks as any digital computer, but in general it is extremely slow. The importance therefore of the Turing machine is its being the fundamental concept of any digital computer.

We are now ready to describe a few Turing machines. A Turing machine computes a function
T(X) = Y, where X is some input and Y the output. We shall confine ourselves to the manipulation of non-zero natural numbers, thus the numbers 1, 2, 3, 4, ... .
Such a function could be : T(N) = N + 3.
This means that we can give any such natural number N as input, and the Turing Machine will compute the addition of 3, i.e. it will compute N + 3. This can be done with a five-state Turing Machine, that adds three BLACK cells to the right end of the starting string (of BLACK cells) [See RUCKER, 1988, Mind Tools, p. 232] :

Let us execute this program, for N = 2. Thus we will compute T(2) = 2 + 3. [said in a more elegant way : We will compute the function T(N) = N + 3, for N = 3].
The input is XX, two BLACK cells on the tape.
To start with, the machine is placed on the left-most BLACK cell and set in internal state 1.
So the first instruction to execute is one (from the list) beginning with 1X, thus 1XR1. This will cause the machine to move one cell to the right while the machine remains in state 1. It encounters a BLACK cell, so again the instruction beginning with 1X, thus 1XR1, must be executed. The machine goes one cell to the right, encounters a WHITE cell, and remains in state 1. Now the machine must look for an instruction that begins with, 1B, hence 1BX2. This tells the machine to make that cell BLACK and to enter state 2. Now the machine must look in the list for an instruction that begins with 2X, it finds it : 2XR3. According to this instruction the machine must move one cell to the right and enter state 3. It encounters a WHITE cell, so the machine must look for an instruction beginning with 3B, this is instruction 3BX3. So it must make this cell BLACK and remain in state 3. Now it must look up an instruction beginning with 3X, and that is 3XR4. Again it must move one cell to the right and enter state 4. It encounters a WHITE cell, so it must find an instruction beginning with 4B, that is 4BX0, so the machine must make this cell BLACK and turn itself off. The calculation is completed, we started with two consecutive BLACK cells and ended up with five consecutive BLACK cells.

A next example of a Turing machine is a machine with a program that computes the function
T(N) = N + N. This programm uses the original number of BLACK cells (i.e. the input, the value of N) as a counter : it erases them one by one and replaces each of them with two new BLACK cells. When the original BLACK cells are all erased then the program will halt, and the computation is done. This can be performed with an 8-state Turing machine, one 0-state (the STOP sign) and 7 non-zero states, so K = 7.
Let us calculate the above function for N = 3, thus the calculation
T(3) = 3 + 3 :


The program now starts all over again, beginning (again) with the first instruction.
This repetition will go on until all the original N's are erased and replaced --
at the end of the string -- by two N's each :

As can be seen, when we anticipate to need more tape, we just add more tape.
In this way the memory (capacity) of the Turing Machine is potentially infinite.

Again the program will revert to the first instruction.

The program now sees that all the original N's are erased.

The machine will now turn itself off, and the calculation is completed.
We started off with X X X (input), and ended up with X X X X X X (output).
It took 47 steps for this machine to accomplish this, i.e. to calculate
the function T(N) = N + N for N = 3.

A Turing Machine can become a universal Turing Machine, U, because it can (be made to) accept any program P and data D.
The computation U(P,D) starts when we give U a tape with a pattern of BLACK cells representing P, followed by a WHITE cell, followed by a pattern of BLACK cells representing D. In computing U(P,D), U simulates the computation
T(D), where T is the machine with program code P.
This is in fact also the case with ordinary digital computers. When we apply a word-processor program to such a computer, then this computer simulates an advanced typewriter.
In the following I will describe the construction of a universal Turing Machine, fully based on the expositions given in PENROSE, 1990, The Emperor's New Mind, chapter 2.

The Universal Turing Machine

For constructing a universal Turing Machine it is necessary to make new coding agreements, which will however -- in the process of the exposition -- successively be replaced by more suitable and efficient ones.
We start with a coding that looks like the one we used in the beginning, but with a slightly different notation. Further we will employ the binary number system .

The binary number system is just a different notation for numbers. Whereas the conventional (denary) notation uses powers of 10 (for example 358 = 3 x 102 + 5 x 101 + 8 x 100), the binary notation uses powers of 2 (for example 1101 = 1 x 23 + 1 x 22 + 0 x 21 + 1 x 20 = 13 in denary) [ a number raised to the 0th power always equals 1. Proof :
a0 = ab-b = ab divided by ab = 1 ].
Because a computer-design always consists of a pattern of switches that are either ON or OFF, the binary number system of notation is very convenient for coding data and instructions.

Each Turing machine characterizes itself by its set of instructions. It will start to operate when we feed in some data. The data will consist of a number (or numbers) on which a certain operation will be carried out by the machine according to its set of instructions.

Figure 3. A twelve-state Turing machine. The horizontal bar symbolizes the possible different internal states the machine can be in. The program is the set of instructions (here applying a notation we used earlier). The machine can move along the tape one cell at a time. It can read its current state and the state of the cell it is visiting.
( After RUCKER, 1988, Mind Tools.)

Since a Turing Machine has only a finite number of distinct internal states it cannot be expected to ' internalize ' all the external data nor all the results of its own calculations. Instead it must examine only those parts of the data or (parts of results of) previous calculations that it is immediately dealing with (i.e. which it locally encounters), and then perform whatever operation it is required to perform on them. It can note down, perhaps in the external storage space, the relevant results of that operation, and then proceed in a precisely determined way to the next stage of operation. Let us give a first coding scheme (that will later be altered, in order to be suitable for the construction of a universal Turing machine) for these instructions :

A typical instruction could then be

0O implies 0OR

This instruction means :
If the machine finds itself in state 0, and if it reads an unmarked cell, then it must remain in state 0, and put a O, i.e. leave that cell unmarked.

Another typical instruction could be

11O implies 1001011L

This instruction means :
If the machine finds itself in state 11, and reads an unmarked cell, then it must enter state 100101, and put a 1, i.e. it must mark that cell.

After the machine has executed such an instruction, it will read its new state, and it will read the cell on which it is now placed, namely whether this cell is marked or unmarked. These two readings together determine which instruction is to be executed next.

Our aim is finally to code the instruction list using only the symbols 0 and 1, because that will be convenient for a computer (of which the Turing machine is the bare concept) that operates with swiches that can either be ON or OFF. So we must code the symbols L, R, STOP and punctuation marks (like commas, or marks that indicate the termination of, say, an instruction) with the aid of the symbols 0 and 1. Also any kind of other mathematical symbols must be coded by means of only these two symbols. But how is it possible, using only strings of 0's and 1's, to distinguish instructions and all kinds of other marks from just numbers? Where does the string of 0's and 1's representing not a number end, in a for the machine recognizable way, and then followed by a string of 0's and 1's which represents a number, and where does this string in turn end, to be followed by yet another string of 0's and 1's representing again not a number? Further there will be Turing Machines that need as input two or more numbers, for example a Turing Machine that should calculate the highest common factor of two given numbers. Also, there will be operations that will output a pair of numbers, for example division with a remainder. All these numbers must be separated somehow from each other, for example by means of a comma. So we must find a way how to code items like a comma, an instruction, a mathematical symbol, by means of the symbols 0 and 1.
This can indeed be done by the following method :
Because representing a number N just by N 1's will be very inefficient for large numbers, we first of all are going to use the binary number notation (thus not just using two symbols instead of ten, but a complete notational scheme). This notation uses only 0's and 1's, but the position of them in the string indicates their value as has been explaned above. So for example the number 29 is 11101 (1 x 24 + 1 x 23 + 1 x 22 + 0 x 21 + 1 x 20). In order to code numbers (in binary notation) as well as instructions, commas, etcetera into strings of 0's and 1's we could apply the following transformations :

Later on we will change this coding a little (they are of course optional, but once settled we must stick to it). We call this : coding by expansion [PENROSE, 1990, The Emperor's New Mind ].
First of all we shall concentrate on the first three transformations, that garantee the unambiguous coding of a sequence of more then one number. Let us take as an example the number-sequence

5, 13, 0, 1, 1, 4,

The last comma serves to mark the end of the sequence, that otherwise would not be clear when this sequence is transformed into a sequence of 0's and 1's, because the tape of the Turing Machine must be potentially infinite in both directions and thus looks like this :

.................000000000 any number coded with 0's and 1's 00000000.................

The Machine must know for sure that the number sequence has ended, and that there will not appear any 1 further down the (potentially) infinite series of 0's on the right.

Let us first change the denary notation of the numbers above into binary. We get the sequence

101, 1101, 0, 1, 1, 100,

Now we will code this sequence by expansion according to the above transformations. This will generate the following string (for convenience we color the coded commas) :


It is clear that by this method of coding the actual NUMBERS appear as sequences of 0's and 1's in such a way that there will never appear more than one 1 directly after each other (because 0 is coded as 0, and 1 is coded as 10). So we can now use sequences-of-more-than-one-1-directly-after-each-other -- and terminated with a 0 ( as can be seen in the above transformation list), to code all kinds of non-numbers, like we just did concerning the comma (that separates numbers) which was coded as 110. Other sequences, like 1110, 11110, etc. can now be used for other symbols, for instance instructions, the STOP sign, mathematical symbols, etc.
One more final point should be made about this coding. In the binary notation (as in the denary notation) one or more 0's in front of a number is redundant, resulting in the fact that for example
0001101 is equal to 1101, and also 000 (or 00 or 0000, etc.) is equal to 0. In not-expanded (but binary) notation this could lead to confusions as to whether a 0 separates two numbers or whether it belongs to one or the other number or whether it is a part of one number. With the expanded binary notation such confusions cannot occur, because of the possibility to use a coding for commas. But then we even do not need to explicitly write down a 0 between two commas, like we see in the above sequence, where the third number is a 0. We can simply code ,0, as two commas directly next to one another (,,). In expanded notation this would give


Thus the above set of six numbers can finally be coded as :


This string has accordingly one 0 missing in comparison with the string we had before.
By means of this coding by expansion we can conveniently code DATA (and output) for a Turing machine, also when they consist of more than one number.

Besides the natural numbers [the numbers 0, 1, 2, 3, ... ] on which we have concentrated so far, there are other numbers, like negative numbers (like -34), fractions (like 23/5), numbers as finite decimal expressions (like 3. 54789), and numbers as infinite decimal expressions (like pi, 3.14159265358979...). When we must code for negative numbers, then we must have a code for the minus-sign, and such a code can easily be provided (using expanded binary notation) by sequences of consecutive 1's, terminated by a 0, like 1111110. The same can be said for fractions. There we need a code for the / sign. Also a finite decimal expression can be coded as a division, using the (coding for the) / sign again.
For example 3. 476 = 3476/1000. So all these numbers can be handled by Turing Machines.
However numbers that must be represented by infinite decimal expressions can present difficulties. We can conceive of a Turing machine churning out all the successive digits of the number pi (that must be represented by an infinite string of symbols, decimal or otherwise), and consequently running forever. But this is not allowed for a Turing Machine, because when the machine does not halt we don't know whether the result will be changed during further calculation (the machine can visit previous outputs and rework these). Only after the machine has halted we can trust the result.
But there is a way to conceive of a legitimately specified Turing machine that can generate one digit of pi after another : It must produce the 1st digit by acting on the number 1, then it must produce the 2nd digit by acting on the number 2, then it must produce the 3rd digit by acting on the number 3, etcetera. So when the machine starts to act on a next number we know that the calculation of the previous digit was wholly completed.

Until now we have described the general construction of one or another specific Turing Machine. With " specific " we mean a Turing Machine supplied with a special program, i.e. supplied with a special set of instructions (instructions like for instance 11010O implies 10011R ) in order to perform a special task, for example multiplying any given number with 25. Such a machine has this set of instructions internalized (see figure 3., but in fact more so than the figure suggests) -- this set of instructions are part of its hardware, while the data is fed in by the tape as input, and the result will be placed on the tape as output.
We will now try to describe a Universal Turing Machine.
In such a machine we want to externalize the program, so that it becomes software for a universal hardware machine. We can do this by coding the set of instructions for an arbitrary Turing machine T into a string of 0's and 1's that can be represented on a tape, and becomes as such externalized, and so part of the input for the machine. As such it then is not a part of the machine anymore, but an optional input -- a program, instructing the universal machine (how) to execute a certain task. This tape, i.e. this program, is accordingly used as the initial part of the input for the universal machine U which then acts on the remainder of the input (the data) just as T would have done. This universal Turing Machine is a universal mimic. The initial part of the tape provides the full information for the universal machine U that it needs for it to imitate any given machine T exactly. This universal Turing machine must be instructed how and when to read the initial part of the tape and how and when to shift the reading-activity to the second part (the data part) of the tape. The relevant instructions for performing these activities form the instruction-set of the machine U itself, i.e. its own instruction-set, that we can interpret as its hardware (its wiring-circuit).
To see how we can conceptually construct such a universal Turing machine, we need a way of numbering Turing Machines. To accomplish this we must start with a general way of coding the instruction-set of an arbitrary Turing machine. Let us, to understand the procedure, take the Turing machine that will add ONE to any given input. Let us call this Turing machine
XN + 1. This Turing machine acceps a number, written in expanded binary notation (where, as we learned above, 0 becomes 0, and 1 becomes 10) and acts on this number leading to an output that must also be considered as expanded binary, and this number has ONE added to the original number (whether we interprete input and output as ordinary binary or expanded binary).
In this particular Turing machine, XN + 1, the instruction-set still figures as its hardware and is (interpreted as) ' soldered ' into the machine (such a machine can only perform one task, in this case ADDING ONE to a given number). Therefore the instruction-set is not coded using only 0's and 1's. The tape only consists of the data, in this case one number, written in expanded binary. The instruction-set for the machine XN + 1 is as follows [See PENROSE, 1990, p. 60]
(recall that an instruction such as 110O implies 0OR means : If the machine is in state 110 (binary notation) and reads a O, then it must enter state 0 and move one cell to the right ) :

0O implies 0OR
01 implies 11R
1O implies 0OR
11 implies 101R
10O implies 11OL
101 implies 101R
11O implies 01STOP
111 implies 100OL
100O implies 1011L
1001 implies 1001L
101O implies 110OR
1011 implies 101R
1101 implies 1111R
111O implies 111R
1111 implies 111OR

When this machine is fed with a number N (in expanded binary notation) it will output a number (in expanded binary notation) N + 1.
When we now want this instruction-set to become just a program for the universal Turing machine, we must code this program into a sequence of 0's and 1's so that we can put it as marks on a tape (BLACK cells, or WHITE cells), and in this way externalize the instruction-set. To begin with, we do not have to distinguish between ordinary 0's and 1's and boldface O's and 1's as we see them in the above instruction-set, because those boldface figures occur only once in each condition of an instruction (i.e. the sequence of symbols before IMPLIES), and also only once in each action-term of an instruction (i.e. the sequence of symbols coming after IMPLIES) Thus for, say, 11O we can write just 110. We can further economize considerably by omitting the IMPLIES-term and also omitting all that comes before that term, relying instead upon the numerical ordering of instructions to specify what those instructions must be. Let me explain this.
The list of instructions can be ordered according to their conditions (the part of the instruction that precedes the IMPLIES-term) when we read them as binary numbers. When we want to use this ordering (i.e. the place of each instruction in an ordered list) then this ordering must not contain gaps, because in that case the specification, saying which instruction must be followed next, will be spoiled. So when there is such a gap then we must insert a dummie-instruction. Indeed in the list of instructions for the machine XN + 1 we miss (in the conditions) 110O, so we will insert a dummie-instruction : 110O implies 0OR . This results in a complete ordering of the list (the dummie-instruction will not be visited by this machine so it does not make a difference in its calculation-procedure). Let us give this list (including the dummie-instruction) and indicate its ordering by a series of consecutive indexes:

  1. 0O implies 0OR
  2. 01 implies 11R
  3. 1O implies 0OR
  4. 11 implies 101R
  5. 10O implies 11OL
  6. 101 implies 101R
  7. 11O implies 01STOP
  8. 111 implies 100OL
  9. 100O implies 1011L
  10. 1001 implies 1001L
  11. 101O implies 110OR
  12. 1011 implies 101R
  13. 110O implies 0OR (dummie)
  14. 1101 implies 1111R
  15. 111O implies 111R 1111 implies 111OR
We see that the binary numbers, composed of the ordinary 0's and 1's (of the sequence before IMPLIES) together with the boldface O's and 1's (of the sequence before IMPLIES), indeed form a numerically successive series. Well, when an instruction is executed by the machine, it will find itself in a certain internal state (i.e. it reads its new state, in the form of a binary number), and reads an unmarked (0) or marked (1) cell. These two readings together form a binary number that directly specifies the sequential number of the next instruction to be executed. So in this way we now can omit the term IMPLIES and everything preceding it. Moreover, as has been said, we do not have to distinguish between normal 1's and 0's and boldface 1's and O's anymore, we can write them either all as normal 1's and 0's or as boldface 1's and 0's. Further, in the process of coding we do not need to code for commas, (for example) at the end of each instruction, since the symbols R, L and STOP suffice to separate the instructions from one another. Having done all this we get the following instruction-list for Turing machine XN + 1 :

00R (dummie)

Now we are ready to code these instructions into expanded binary according to the following list of transformations (recall that by coding in this way we are able to distinguish between numbers and non-numbers -- non-numbers are things like R, L, STOP, etc.) :

0 becomes 0
1 becomes 10
R becomes 110
L becomes 1110
STOP becomes 11110

Because these instructions are well separated by R, L and STOP, and correspondingly well separated by 110, 1110 and 11110 (because apart from them we can never encounter more then one 1's directly after each other) we can omit any 00 when this is all there is between two such signs (for example between R and L). So ... R 0 0 L ... -- where R is the last part of an instruction, and 0 0 L is the next instruction meaning : enter state 0, write a 0, and move one cell to the left -- can be written as . . . R L . . . , and thus coded as . . . 1 1 0 1 1 1 0 . . . .
It is also clear that 01, when that is all there is between two (separating) signs like R, L or STOP, can be replaced by 1, because then we see this 1 between two separating signs (like R, L or STOP) and the fact that before it stands nothing, can be interpreted as a 0 , so, for example
. . . R 0 1 L . . . can be replaced by . . . R 1 L . . . , and coded as . . . 1 1 0 1 1 1 1 0 . . . . In reading . . . 1 1 0 1 1 1 1 0 . . . the machine cannot be confused by the fact that it encounters . . . 1 1 1 1 0 . . . and interprets this (falsely) as " STOP", because then it reads . . . R STOP . . . , and because STOP itself already means R STOP, the machine would read R R STOP, which cannot be a proper instruction because in one and the same individual instruction the movement of the machine is only one cell (to the right or left), and not two times to the right, nor two times to the left, nor to the left and (then) to the right (because this latter is no movement at all and should not be coded).

The above already abbreviated instruction-list (including the dummie-instruction) for Turing Machine XN + 1 will accordingly look like this (written horizontally) :

R 1 1 R R 1 0 1 R 1 1 0 L 1 0 1 R 1 S T O P 1 0 0 0 L 1 0 1 1 L 1 0 0 1 L 1 1 0 0 R 1 0 1 R R 1 1 1 1 R 1 1 1 R 1 1 1 0 R

This is coded as the tape sequence :

11010101101101001011010100111010010110101 11101000011101001010111010001011101010001 1010010110110101010101101010101101010100110

To the left and to the right of this sequence we must think of a potentially infinite string of 0's. We see that the sequence begins with 110 and ends with 110. We can leave out the initial 110, because this means 00R, representing the initial instruction
00 implies 00R that we assume (i.e. stipulate) common to all Turing machines, so that the device can start arbitrarily far to the left of the marks on the tape and run to the right until it comes up to the first mark (1).
Also we may delete the final 110, since all Turing Machines must have their descriptions ending this way, because they all end with R ( 110 ), L ( 1110 ) or STOP ( 11110 ). The machine will always start with reading an 110 in front of this economized sequence, and always read an 110 after this sequence.
When we moreover imagine to leave out the infinite strings of 0's to the left and to the right, then the resulting BINARY NUMBER (i.e. the resulting sequence interpreted as an ordinary binary number) is THE NUMBER OF THE TURING MACHINE, which in our case of the Turing machine XN + 1 is :

10101101101001011010100111010010110101 11101000011101001010111010001011101010001 1010010110110101010101101010101101010100

In standard denary notation, this particular number is :


Sometimes one loosely refers to a Turing machine whose number is N as the Nth Turing machine TN. Thus XN + 1 is the
450813704461593958982113775643437908th Turing machine.

In principle with each binary number should correspond a certain Turing Machine, which could perform a certain task. But many of them are not really genuine Turing machines at all because many of them turn out not to be defined unambiguously or run forever without giving a final output [See PENROSE, 1990, p.70/1].

So we have now succeeded in coding the instruction-set of any Turing machine into a string of 0's and 1's, and this string can be represented on a tape and serve as a program for a universal Turing machine. The machine reads this string by adding 110 at the beginning and at the end, and by interpreting this whole string as expanded binary it reads in fact its instruction-set. But of course this is not enough. Every Turing machine needs DATA, so also our universal Turing machine.
The DATA must be coded on the tape after the coding (sequence) of the instruction-set (the program), separated by the sign 111110. This coding of DATA must also be done by means of expanded binary, because sometimes we need more than one number as input, and these numbers must be separated by signs themselves also consisting of 0's and 1's only. Moreover one can have Turing Machines which operate directly on mathematical formulae, such as algebraic or trigonometric expressions. In these expressions all kinds of signs occur that are themselves not numbers, such as integrals sines and cosines. They all must be coded using only 0's and 1's. And this can be done conveniently by the method of expansion. And the Machine must accordingly read such a string as a result of this expansion. So far so good.
Besides the fact that the machine interprets such a string in such and such a way (in this case as the result of expansion), WE ourselves can (also) interprete (i.e. read) such a string in another way (namely for the purpose of generating a concept for a universal Turing Machine) :
Because the data-string always consists of 0's and 1's only, we can always (also) interpret it as just the representation of ONE binary number (We did this already with the string, representing the instructions, and in that way obtained the number of the Turing Machine). But because the series of 0's and 1's always ends up with an potentially infinite series of 0's it can as such not be interpreted as a definite binary number (the value of this number would be indefinitely large), so we must terminate it somewhere. Because now we interpret that string NOT as the result of expansion (which the machine does), we cannot interpret sequences as, say, 110, as commas, one of them terminating the data-string. One way of reading the string as an ordinary binary number could be by only reading this string till the last 1 appears, and including this last 1. But then our reading would result in odd numbers only. To remedy this problem we, in our effort to read the data-string as ONE number (the machine reads it another way), will NOT read the last 1, and then readings of both odd and even numbers are indeed possible. For example we can read the input-string

1 1 0 1 1 1 0 0 1 0 0 0 0 0 . . .

as the following binary number :

1 1 0 1 1 1 0 0,

and the number

1 1 0 1 1 1 0 0 1 1 0 0 0 0 0 . . .

as the following binary number :

1 1 0 1 1 1 0 0 1

And this interpretation of the input-string can be used to generate the concept of the universal Turing machine, as follows :
Our discussion will first of all use only valid Turing Machines, i.e. correctly specified machines, which means that the machine, when turned on will come to a halt after a finite number of steps, and delivers an output. We call the data-string, interpreted as a single binary number, the number M. When the Nth Turing Machine TN is fed with the number M, then it will, provided that this Turing machine is correctly specified, generate an output after a finite number of steps. This output can in fact be a complex expression containing all kinds of signs coded in expanded binary. But, just as was the case with the data-string, we can (also) interpret this output-string as representing ONE (ordinary) binary number. Let us call this number P.
So when we feed TN with M, then we get P. We can express this as follows :

TN (M) = P

But we can look at this relation in a slightly different way also. When we know the numbers N and M, then we can work out what P is, by seeing what the Nth Turing machine does to M. This particular operation is entirely algorithmic and can therefore be carried out by a Turing machine U. This machine U works on the pair (N,M) and outputs P.:

U (N,M) = TN (M) = P

Since the machine U has to act on both N and M, and since we want to put both N and M on a tape, we need some way of separating the two. We can do this by the same type of sign we already use in N to specify things like R (110, L 1110, STOP 11110, etc.). So if we use a not yet used sign, say, 111110, to code for this separation-mark, then we can separate N and M easily. When the Machine is working after this mark, then it is working on the data, and here we can use for example 110 for coding a comma, and other such marks for other signs and symbols.
So it is now possible to code both N and M on the tape of U. When we start U it will work on M according to N, i.e. it simulates the Turing Machine TN. So this Machine U can simulate any Turing Machine, and thus is a Universal Turing Machine.
Let us quote an example, adapted from PENROSE, p. 73, for U simulating the eleventh Turing Machine, T11. We give this Turing machine T11 the number 722 as input. So we then have a Universal Turing Machine working on the numbers N and M, where N = 11 (denary notation) and M = 722.
When we express the number 11 in (ordinary) binary notation, then we get N = 1011. We know that the machine reads this sequence as being preceded by 110, and also terminated by 110. So it reads (we space the digits for clarity) :

1 1 0 1 0 1 1 1 1 0

This represents the action-parts of the instruction (i.e. the instruction-set, represented by the sequence of the -- ordered -- action-parts of the instructions) :

1 1 0 = R,
1 1 1 1 0 = STOP
Between these we find 1 0, that must be interpreted (read) as 1, because the expanded form of 1 is 1 0. So we have :


Before R we see nothing. This means that we must read this " nothing " as 0 0, because before signs like STOP, R, L, etc. we expect TWO symbols. Likewise we must interpret the 1 . Because before STOP we expect TWO symbols, we must interprete this 1 as 0 1. So we accordingly have :

0 0 R 0 1 STOP

This corresponds to the action-parts of two instructions, namely

00R and 01STOP

00R means : enter internal state 0, write 0, and move one cell to the right.
01STOP means : enter internal state 0, write 1, move one cell to the right and stop (recall that STOP means RSTOP).

We know that each action-part (00R and 01STOP) must be connected with the term IMPLIES, and before that term the conditional-part of the instruction must be conceived present : the FIRST action-part must relate to the numerical FIRST conditional-part ( 00 ), the SECOND action-part must relate to the numerical SECOND conditional-part ( 01 )
[Recall that the full instructions are ORDERED according to the numerical value of the conditional-parts, which means that the machine, after having executed a complete instruction, knows which instruction to execute next. For example when, after having executed a complete instruction, it reads its internal state as 1101 (binary notation for 13), and it reads a marked (1) cell, then it must look for the 11011th instruction (in denary notation this is the 27th instruction). This next instruction to be executed can be found in the ordered list of action-parts, and the machine knows that the corresponding conditional-part is 11011, which means : IF the machine finds itself in state 1101, and reads a marked cell, then it must ..... ].
For our example we found that the conditional part of 00R is 00, and the conditional part of 01STOP is 01. So the complete instruction-set for T11, and consequently (the complete instructon-set, i.e. its program) for U (11, 722), is :

00 implies 00R, 01 implies 01STOP

This instruction set means :

IF the machine is in internal state 0, and finds itself on a blank cell (it is stipulated that every Turing mache starts this way), THEN it must remain in state 0, write a 0, and moves one cell to the right. IF the machine is in internal state 0, and reads a marked cell, THEN it must move one cell to the right and switch itself off (recall again that STOP = RSTOP).

This instruction-set will now become the program (that could easily be replaced by another such program) of the Universal Turing machine U. This program (the instruction-set of T11) will be represented on the tape of U by the binary representation of the number 11 (N = 11) : 1 0 1 1. This number will be separated from the number M (M = 722) representing the data, by the sign 1 1 1 1 1 0 , and after this termination-sign should come the binary representation of 722, that is 1 0 1 1 0 1 0 0 1 0 , but this must be represented on the tape as 1 0 1 1 0 1 0 0 1 0 1 where the last 1 is readed as a termination-mark. So we feed U with the following string :

. . . 0 0 0 1 0 1 1 1 1 1 1 1 0 1 0 1 1 0 1 0 0 1 0 1 0 0 0 . . .

. . . 0 0 0 is the initial blank tape,
1 0 1 1 is the binary representation of 11,
1 1 1 1 1 0 is the termination mark of N,
1 0 1 1 0 1 0 0 1 0 is the binary representation of 722,
1 0 0 0 . . . is the remainder of the tape.

What the Turing machine U would have to do, at each successive step of the operation of TN on M, would be to examine the structure of the succession of digits in the expression for N (i.e. reading the successive instructions for TN), so that the appropriate replacement (the calculation activities) in the digits for M (i.e. TN's ' tape ') can be made.

U's own list of instructions would simply be providing a means of reading the appropriate entry in that list (which is encoded in the number N) at each stage of application to the digits of the data-string as given by M.

There would admittedly be a lot of dodging backwards and forwards between the digits of M and those of N, and the procedure would tend to be exceedingly slow. Nevertheless a list of instructions for such a machine can certainly be provided [PENROSE, p. 73], and we call such a machine a universal Turing Machine. The machine U, when first fed with the number N, precisely imitates the Nth Turing machine.
Since U is a Turing Machine, it will itself have a number, i.e. we have

U = Tu,

for some number u.

At last we have described one of the possible versions of a UNIVERAL TURING MACHINE.
We can feed this machine with any correctly specified program (the number N), and then it will execute the task that the program dictates. We can perhaps interpret its own instruction-set (described with the number u ) as the hardware of the machine, i.e. the totally internalized specification, that should be realized by means of electrical circuits inside the machine [See PART TWO of this Essay].
All modern (serial and parallel) general purpose computers are in effect universal Turing machines, but of course their logical design needs not to be identical with the machine just described. What we have done here is to describe the general CONCEPT of a general purpose digital computer, by means of the description of a universal Turing machine.

For the continuation (Part Two ) of this Essay, treating of electrical circuits that can compute, please click HERE .

back to top
