Turing Completeness of the ENIAC

Turing Machine Basics

Formal Definition

There are numerous ways of formulating a Turing machine, and many proofs exist of the equivalence of various ones. For our discussion, we will use the one that is presented in Hopcroft and Ullman's classic work on automata theory. (We note here that in his original paper Turing didn't use quite the same notation.) At a very high level, a Turing machine is a finite state machine and an unbounded tape. The tape is divided into cells, each of which can hold a single symbol. On each transition, the finite state machine reads a symbol from the tape, transitions to a new state, writes a new symbol to the tape, and moves either left or right to an adjacent tape cell. More formally, a Turing machine is defined by:

where
$Q$ is the set of states in the finite state machine,
$\Sigma$ is the input alphabet,
$\Gamma \supseteq \Sigma \cup \left\{B\right\}$ is the tape alphabet,
$\delta :Q\times \Gamma \to Q\times \Gamma \times \{L,R\}$ is the finite state machine's transition function,
$q_0\in Q$ is the initial state,
$B\in \Gamma$ is the blank symbol that is read from any cell not written to, and
$F\subseteq Q$ is the set of final states.

Turing Machine Example

One of the most classic examples of a Turing Machine is one that performs addition on two numbers expressed in unary notation. For this example, we will use the symbols $a$ and $b$ to represent the input numbers, i.e. $\Sigma \{a,b\}$ An input number is represented by that many $a$s and the input will contain one $b$ separating the two numbers to add. So the input for the problem of adding 5 and 7 would look like: $\mathrm{aaaaabaaaaaaa}$. When the machine starts running, the tape head begins pointing to the first symbol on the tape.

The strategy that we will follow will operate in stages. In the first stage, we move the tape head to the right across the $a$s until a $b$ is encountered. At that point, we change the $b$ to an $a$ and continue moving to the right across the remaining $a$s. When we hit the blank after the last symbol, we back up (move left) one spot and change the $a$ there to a $b$ and halt.

We will use four states: $Q=\{q_0,q_1,q_2,q_3\}$. Only $q_3\in F$. The transition function that captures our algorithm is given by the following:

$\delta (q_0,a)=(q_0,a,R)$
$\delta (q_0,b)=(q_1,a,R)$
$\delta (q_1,a)=(q_1,a,R)$
$\delta (q_1,B)=(q_2,b,L)$
$\delta (q_2,a)=(q_3,b,R)$

Universal Machines

The opening paragraph of Section 6 of Turing's paper begins with:

"It is possible to invent a single machine which can be used to compute any computable sequence. If this machine 𝒰 is supplied with a tape on the beginning of which is written the S.D. of some computing machine ℳ, then 𝒰 will compute the same sequence as ℳ."

The fact that this model lends itself to such a universal machine is part of what leads us to think that the sequences that are defined to be computable in the Turing Machine model are all of the sequences that can be computed by any mechanistic procedure. In his proof of the same result regarding the Entscheidungsproblem, Alonzo Church defined another model called the lambda calculus, and Turing proved that the two models are equivalent. The idea that these models describe everything that can be computed is known as the Church-Turing Thesis.

It's important to note that Turing was not attempting to create a computer when he proposed his model. However, today, we recognize that the basic operation of 𝒰 is essentially a computer and the S.D. of the machine ℳ is another way to look at what a program is. It is the study of the phenomena of universality that makes Computer Science an intellectual field that goes beyond applications.

Turing Completeness

With the Church-Turing Thesis essentially setting the bar for computation, we distinguish machines that are equivalent to the most capable machines by determinining whether they are capable of computing the same functions as an arbitrary Turing Machine. Of course, any physical realization is limited to a finite amount of matter and thus can emulate only a finite amount of tape. Likewise, the number of states and the number of tape symbols must be finite in any physical realization. We generally say that any machine that is capable of emulating any arbitrary Turing Machine within the constraints of its finiteness to be Turing Complete. Turing Completeness is shown in a variety of ways, often by showing equivalence with another model that has already been shown to be Turing Complete.

One of the more interesting aspects of the ENIAC is that it was Turing complete. It is worthwhile to note that it was not one of the objectives of the designers of the ENIAC to create a Turing complete machine. In fact at the time, relatively few people were familiar with Turing's paper. However, the ENIAC's creators' intuition about what was necessary for a general purpose machine did result in one that was equivalent to the universal machine of theory. While this has been shown before, we have recently demonstrated this in a direct way. In particular, there is a construction that takes any Turing machine within certain finite limits and configures the ENIAC to emulate it.

Implementation on the ENIAC

As a demonstration of the Turing completeness of the ENIAC, we have implemented a generalized Turing machine on the ENIAC. It is similar in spirit to a universal Turing machine in that the transition function for the Turing machine to simulate is stored as data on the ENIAC's function tables. This work was a collaboration of my student Beamlak Mebrate and myself (Brian Stuart).

As with any physical realization of a Turing complete machine, there are finite limitations on this implementation. Specifically, the set of states is limited to 100, i.e. $Q\subseteq \{0,1,2,\mathrm{...},99\}$. The tape alphabet is limited to 6 symbols: $\Gamma \subseteq \{0,1,2,3,4,5\}$. Finally, the tape is limited to 110 cells.

The wiring for this generalized Turing machine is shown in this set-up diagram. Note that the function tables and adapters are not shown in this diagram. The full simulator programming is given in this file.

Accumulator Assignment

As with other early machines with limited memory, one of the major aspects of programming was assigning roles to each memory location. In the ENIAC, the only volatile memory was the accumulators. In effect, the programmer had 20 variable locations, and how each was used was critical to effectively use the machine. In our generalized Turing machine, the primary use of each accumulator is as follows:

Acc 1-Acc 11

The 110-cell tape

Acc 12

Current tape position.

Acc 13, Acc 15, Acc 16

Ping-pong for shifting the cells of an accumulator's set of cells.

Acc 14

Counter for ping-pong to select cell.

Acc 17

The current state

Acc 18

Staging of the transition function value.

Acc 19

Staging of current symbol for function table selection and new symbol for shifting.

Acc 20

Hold halt/continue indicator.

Overall Algorithm

The Turing machine simulation here is implemented as a cycle with 8 phases. The net effect of each iteration of the cycle is to read a symbol from the tape, look up the transition based on the current symbol and current state, write the new symbol to the tape, record the new state, and increment or decrement the tape pointer.

1. Copy the accumulator holding the current tape cell to Acc 13. The 10s digit of a12 identifies the relevant tape accumulator.
2. Ping-pong among Acc 13, Acc 15, and Acc 16 to shift the current symbol. The number of shifts is specified by the 1s digit of Acc 12.
3. Use the current symbol $x$ to select the correct function table.
4. Use the current state $q$ in a17 as the argument to the selected function table.
5. Read value of $\delta (q,x)$ from the function table and store it in Acc 18, store the new state in Acc 17, and increment or decrement the tape head pointer, Acc 12.
6. Continue the ping-pong among Acc 13, Acc 15, and Acc 16 to shift the new symbol into the group of 10 symbols.
7. Store the 10-digit number into the accumulator identified by the 10s digit of Acc 12.

Phase Details

Phase I

Because each digit of a tape accumulator is a single cell of the Turing machine tape, we must first determine which accumulator contains the symbol under the head, and then which digit within that accumulator is the desired symbol. Phase I of the cycle identifies the appropriate accumulator and copies its value to Acc 13.

The technique that is used here is similar to that illustrated in the ENIAC Technical Manual Part I, Section 10.5.2 by Adele Goldstine. In that discussion, a single digit of Acc 12 is used to select among 11 separate programs. Here we use the 11 programs to transmit from each individual tape accumulator and receive on Acc 13.

The basic idea is that the tape index is offset by 50, i.e. it covers the range 50 to 159, representing cells 0 through 109. For the first 50 cells (indices 50 through 99), the 100s digit of Acc 12 is 0, and for the other 60 cells (100 through 159), the 100s digit is 1. We route this digit to the stepper direct input of Master Programmer Stepper E. As a result, Stepper E will be at stage 1 if the specified cell is on Acc 1 through Acc 5, and will be at stage 2 if the specified cell is on Acc 6 through Acc 11. The stage 1 output is fed to the Stepper F input, and the stage 2 output is fed to the Stepper A input. The 10s digit of Acc 12 is routed to the stepper direct inputs of Steppers A and F. The Stepper A and F stage outputs trigger the output programs on Acc 1 through Acc 11. This is illustrated in the following set-up table fragment.

Phases II and VI

Once we have the set of 10 cells from one accumulator in Acc 13, we need to shift it until we get to the symbol identified by the head pointer. Since that same symbol will be replaced, we set up a full shift of 10 positions, and then on the selected on, we basically do a subroutine that looks up the transition function and pulls the new symbol in.

The general idea is that we shift Acc 13 to the left 10 times by copying it to Acc 15, and then copying back with a one-digit shifter. At the same time, we shift Acc 16 to the left 10 times, also using Acc 15 as a staging area. We start with the least significant digit of Acc 12 in Acc 14, specifying which digit of the Acc 13 we need. Each of the 10 iterations begins with a left shift of Acc 16, followed by a left shift of Acc 13. Acc 14 is decremented concurrently with the shift of Acc 13. The sign of Acc 14 is routed to the control line 4-8 (from the A terminal) and 4-9 (from the S terminal), and they are then processed through dummy programs to lines 4-10 and 4-11, respectively. If Acc 14 is non-negative after the decrement (which will occur nine out of the 10 iterations), a control pulse is transmitted on 4-11, which causes a transmission of the least significan digit of Acc 15 to be added to Acc 16.

Phase III

If Acc 14 is negative after the decrement, then the control pulse appears on control line 4-10 which initiates Phase III. Here, we transmit the least significant digit of Acc 15 to Acc 19 and in turn passed on to the stepper direct input of Stepper C. The six stepper outputs of Stepper C each initiate a program on one of the function tables, as illustrated in the following peddling sheet fragment. The net effect is that the symbol under the tape head selects which function table and whether the A or B output of that table.

Phase IV

The function table programs are all the same case of reading the argument value and transmitting once. In all cases, the argument is read from Acc 17. This has the effect of using the current state to select the row of the table that we're reading from. Dummy programs that wait to the end of the function table read cycle are divided into two sets: those that trigger a read from the A side of the function table (control line 5-10) or the B side (5-11).

Phase V

In Phase V, the value read from the selected function table is written to Acc 18. The low-order five digits of that number is the value of $\delta (q,x)$ encoded as HSDQQ. H indicates whether this transition leads to a halting state: 0 for halt and 9 for continue. S is the new symbol to write to the tape. D is the direction to move the tape head: 0 for right and 9 for left. QQ is the new two-digit state number. Acc 18 then transmits that value through a number of shifters and deleters to distribute the digits to the appropriate places. In particular, the two-digit QQ value is written to Acc 17. The H digit is written to Acc 20. The S symbol is written to the low-order digit of Acc 16. At the end of the distribution of the digits, control line 4-1 is pulsed to return to the loop doing the digit shifting. Finally, the D digit is used to choose between incrementing and decrementing Acc 12, and this update takes place in parallel with the next pulse through the master programmer.

Phase VII

After the shifting loop is finished, Stepper B outputs a pulse on line 4-3 to initiate the writing of the shifted value back to the relevant accumulator. In Phase I, we sent the then-current value of Acc 12 to Steppers H, J, and K at the same time as Steppers A, E, and F, effectively priming the control structure for writing the accumulator back. So at this point, all we have to do is trigger the operation. After that's done, we use the value written to Acc 20 to initiate the next cycle. However, if that value is 0, then we don't start a new cycle and instead halt.

Required Adapters

One of the lesser-known parts of ENIAC programming is the use of adapters. These cables allow the programmer to modify values transmitted from an accumulator in a variety of ways, such as shifting the digits to the left or right, deleting a subset of the digits, and breaking the digits out into individual control lines. They are implemented by alternative wiring between connectors and do not involve additional active components. The technical manuals on the ENIAC discuss a number of adapters that were built as part of the initial construction of the machine and furthermore discuss how other adapters can be built as needed. In this Turing machine implemenation, we have made significant use of adapters, both part of the original set and a few custom ones.

Shifters

There are five shifters used here. Two are +1 shifters that shift the number one place to the left (effectively multiplying by 10), and one is a -3 shifter that shifts three places to the right (effectively dividing by 1000). All three of these are ones that were originally constructed and documented in drawings PX-4-104B and PX-4-104C. The fourth and fifth shifters we use would be designated -9 shifters which place the most significant digit coming from the accumulator into the least significant digit of the destination. No such shifter is documented; the maximum amount of shift in the original shifters is five places. However, there could be a custom shifter wired to perform this action. Alternatively, the shifters are all built with a plug on one side and a socket on the other and are wired in such a way that two can be cascaded to create a larger shift amount. Therefore a -5 shifter and a -4 shifter could be connected in series to produce the effect of a -9 shifter.

Digit-Program Adapters

We make use of several digit-program adapters. These adapters plug into a digit tray and provide program cable connections to each of the ten digits and the sign as 11 individual connections. The most common use of these is to extract individual digits from an accumulator and feed them into either dummy programs ro into the master programmer to selectively modify the program flow. They are central to the way conditional branching is implemented on the ENIAC. All uses of the digit-program adapters here are in line with what is documented and can be done with the equipment shipped from UPenn to BRL.

Deleters

There are two deleters used here, neither of which exactly matches the "off the shelf" adapters. Both of these deletes all but the least significant digit. Such an adapter would have pins 1 and 12 of the socket and plug connected as usual and pins 2-11 of the plug connected to ground (pin 12). The first is used when copying from Acc 12 to Acc 14 to initialize a counter with the 1s digit of the tape position. The same function could be achieved with original adapters by combining a +4 shifter, the 5A adapter from PX-4-117, and a -4 shifter on the Acc 14 input. Similarly, the second deleter is used in combination with a -3 shifter to pass along only the least significant digit when transferring the new symbol to Acc 16. Connecting a +1 shifter, the 5A adapter from PX-4-117, and a -4 shifter would perform the same function.

Semi-Formal Construction

Given a Turing Machine $M=⟨Q,\Sigma ,\Gamma ,\delta ,q_0,B,F⟩$ where $\left|Q\right|\le 100$ and $\left|\Gamma \right|\le 6$:

1. Let $B$ be represented by 0.
2. Let $q_0$ be represented by 0.
3. For $Q=\{q_0,q_1,...,q_n\}$, let $q_i$ be represented by the number $i$.
4. For $\Sigma =\{{\sigma }_1,{\sigma }_2,...,{\sigma }_m\}$, let ${\sigma }_i$ be represented by the number $i$.
5. For $\Gamma =\{{\gamma }_0,{\gamma }_1,...,{\gamma }_m\}$, let ${\gamma }_0=B$ and ${\gamma }_i={\sigma }_i$, for $i\ge 1$.
6. For each element of the function, $\delta (q_j,{\gamma }_x)=(q_k,{\gamma }_y,d)$, set the function table entry as follows:

   	$q_k\in F$, $d=R$	$q_k\in F$, $d=L$	$q_k\notin F$, $d=R$	$q_k\notin F$, $d=L$
   $x=0$	$\mathrm{FT1A}\left(j\right)=1000y+k$	$\mathrm{FT1A}\left(j\right)=900+1000y+k$	$\mathrm{FT1A}\left(j\right)=90000+1000y+k$	$\mathrm{FT1A}\left(j\right)=90900+1000y+k$
   $x=1$	$\mathrm{FT1B}\left(j\right)=1000y+k$	$\mathrm{FT1B}\left(j\right)=900+1000y+k$	$\mathrm{FT1B}\left(j\right)=90000+1000y+k$	$\mathrm{FT1B}\left(j\right)=90900+1000y+k$
   $x=2$	$\mathrm{FT2A}\left(j\right)=1000y+k$	$\mathrm{FT2A}\left(j\right)=900+1000y+k$	$\mathrm{FT2A}\left(j\right)=90000+1000y+k$	$\mathrm{FT2A}\left(j\right)=90900+1000y+k$
   $x=3$	$\mathrm{FT2B}\left(j\right)=1000y+k$	$\mathrm{FT2B}\left(j\right)=900+1000y+k$	$\mathrm{FT2B}\left(j\right)=90000+1000y+k$	$\mathrm{FT2B}\left(j\right)=90900+1000y+k$
   $x=4$	$\mathrm{FT3A}\left(j\right)=1000y+k$	$\mathrm{FT3A}\left(j\right)=900+1000y+k$	$\mathrm{FT3A}\left(j\right)=90000+1000y+k$	$\mathrm{FT3A}\left(j\right)=90900+1000y+k$
   $x=5$	$\mathrm{FT3B}\left(j\right)=1000y+k$	$\mathrm{FT3B}\left(j\right)=900+1000y+k$	$\mathrm{FT3B}\left(j\right)=90000+1000y+k$	$\mathrm{FT3B}\left(j\right)=90900+1000y+k$

Example Revisited

Applying this construction to the example from above, $B$ is 0, $a$ is 1, and $b$ is 2. The function table values are:

$\mathrm{FT1B}\left(0\right)=91000$
$\mathrm{FT2A}\left(0\right)=91001$
$\mathrm{FT1B}\left(1\right)=91001$
$\mathrm{FT1A}\left(1\right)=92902$
$\mathrm{FT1B}\left(2\right)=02003$

These switch settings and the initialization can be found in this file. Following the earlier example, to add 5 to 7, we set the first 13 tape cells to 1111121111111, and can be read from the punched card in this file. The left-hand image here shows the first two tape accumulators before running the Turing machine performing the addition. Acc 1 and 2 after the addition is complete is shown in the right-hand image.