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

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

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,

Further we have

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.

- Input devices (keyboard, mouse, etc).
- Memory board.
- Central Processing Unit (processor).
- Output devices (video terminal, printer, etc.).

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.

- 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.
- 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.
- The processor is able to move its attention to a new memory location.
- The processor is able to change its internal state. That is, it can change its predilections about what to do next.

A Turing machine [See, among others, PETERSON, 1988,

An

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 **:**

** ...00011101111000... **

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 **:**

** ...00011111110000... **

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).

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.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.

The above action-table can now be written down in a more compact way by coding the details as follows

So we can now write down the above action-table (i.e. the program) more compact

**
**

- 0XR0

- 1XR1

- 2XB stop

- 0BXR1

- 1BL2

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

- a (new) internal state and
- a final settling of the machine on some cell which is BLACK (= X) or WHITE (= B)

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) [

The result is a string of seven consecutive BLACK cells

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 natural numbers 0, 1, 2, 3, ... will be used to describe the internal state of the machine. The total of possible internal states the machine can be in must always be finite. The size of the number of such possible internal states is an indication of the complexity of the machine, i.e. the complexity of the possible behavior of the machine (analogous to the complexity of a digital computer's processor design). Here we will denote the state 0 as a STOP sign, if and when the machine enters state 0, then it will stop moving and turn itself off.
- A BLACK cell will be denoted by X,
- a WHITE cell by B.
- Move (the Head of the machine) to the next cell on the right will be denoted by R.
- Move (the Head of the machine) to the next cell on the left will be denoted by L.

2XB3, which means

Or (a typical instruction) could read

1BL1, which means

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

**
1XL2
2BR1
**

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 = 3^{4}. 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 S^{L}.

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 K

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

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] **:**
**
**

- 1XR1
- 1BX2, 2XR3
- 3BX3, 3XR4
- 4BX0

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

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 :**

A Turing Machine can become aThe 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.

The computation

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

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

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 10^{2} + **5** x 10^{1} + **8** x 10^{0}), the binary notation uses powers of 2 (for example 1101 = **1** x 2^{3} + **1** x 2^{2} + **0** x 2^{1} + **1** x 2^{0} = 13 in denary) [ a number raised to the 0th power always equals 1. Proof **:**

a^{0} = a^{b-b} = a^{b} divided by a^{b} = 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

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 **:**
**
**

- Read or write a BLACK (i.e. marked) cell =
**1**(bold type) - Read or write a WHITE (i.e. unmarked) cell =
**O**(bold type) - Internal State of the machine = a natural number (i.e. one out of the set {0, 1, 2, 3, 4, ... }) written in
**binary**notation, for example 1101 (= 13 in denary notation). - Move one cell to the right = R
- Move one cell to the left = L
- Move one cell to the right and shut down the machine = STOP

0**O** implies 0**O**R

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

11**O** implies 100101**1**L

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 2^{4} + **1** x 2^{3} + **1** x 2^{2} + **0** x 2^{1} + **1** x 2^{0}). 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 **:**

**
**

- 0 becomes 0
- 1 becomes 10
- , becomes 110
- R becomes 1110
- L becomes 11110
- STOP becomes 111110
- Etc.

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) **:**

**...00001001011010100101100110101101011010001100000.... **

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

** ...000110110000... **

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

**...0000100101101010010110110101101011010001100000.... **

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
**11010 O 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

In such a machine we want to externalize the

To see how we can conceptually construct such a universal Turing machine, we need a way of

In this particular Turing machine,

(recall that an instruction such as 110

0**O** implies 0**O**R

0**1** implies 1**1**R

1**O** implies 0**O**R

1**1** implies 10**1**R

10**O** implies 11**O**L

10**1** implies 10**1**R

11**O** implies 0**1**STOP

11**1** implies 100**O**L

100**O** implies 101**1**L

100**1** implies 100**1**L

101**O** implies 110**O**R

101**1** implies 10**1**R

110**1** implies 111**1**R

111**O** implies 11**1**R

111**1** implies 111**O**R

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, 11**O** 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

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

- 0
**O**implies 0**O**R - 0
**1**implies 1**1**R - 1
**O**implies 0**O**R - 1
**1**implies 10**1**R - 10
**O**implies 11**O**L - 10
**1**implies 10**1**R - 11
**O**implies 0**1**STOP - 11
**1**implies 100**O**L - 100
**O**implies 101**1**L - 100
**1**implies 100**1**L - 101
**O**implies 110**O**R - 101
**1**implies 10**1**R - 110
**O**implies 0**O**R (dummie) - 110
**1**implies 111**1**R - 111
**O**implies 11**1**R 111**1**implies 111**O**R

**00**R

**11**R

**00**R

**101**R

**110**L

**101**R

**01**STOP

**1000**L

**1011**L

**1001**L

**1100**R

**101**R

**00**R (dummie)

**1111**R

**111**R

**1110**R

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 ** 00**R, 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 **:**

**
450813704461593958982113775643437908. **

Sometimes one loosely refers to a Turing machine whose number is N as the Nth Turing machine T_{N}**.** 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

as the following binary number **:**

and the number

as the following binary number **:**

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 T_{N} 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 T_{N} with M, then we get P. We can express this as follows **:**

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.**:**

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 T_{N}. 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, T _{11}**. We give this Turing machine T

When we express the number 11 in (ordinary) binary notation, then we get N =

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 **:**

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

**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 T

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 T_{11}) 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 **:**

where,

. . . 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 T_{N} 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 T_{N}), so that the appropriate replacement (the calculation activities) in the digits for M (i.e. T_{N}'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

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.

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