Models of computation

Published: Last Edited:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.


A Model of Computationis the definition of the set of allowable operations used in computation and their respective costs. Only assuming a certain model of computation is it possible to analyze the computational resources required, such as theexecution timeormemory spaceor to discuss the limitations of algorithms or computers.

TheModel of Computationexplains how the behavior of the whole system is the result of the behavior of each of its components.








A logic gate is a physical device that realizes a Boolean function. A logic circuit, as defined is a directed acyclic graph in which all vertices except input vertices carry the labels of gates.


To make ideas concrete, bulbs, and switches. Shown with each of these circuits is a logic symbol for the gate. These symbols are used to draw circuits, such as the circuit of Fig. 1.3(c) for the function (x∨y)∧z. When electrical current flows out of the batteries through a switch or switches in these circuits, The bulbs are lit. In this case we say the value of the circuit is True; otherwise it is False. Shown Below is the truth table for the function mapping the values of the three input variables of the circuit in Fig.1(c) to the value of the one output variable. Here x, y, and z have value 1 When the switch that carries its name is closed; otherwise they have value 0.

Today's computers use transistor circuits instead of the electrical circuits of Fig. 1

Logic circuits execute straight-line programs, programs containing only assignment statements. Thus, they have no loops or branches. (They may have loops if the number of times a loop is executed is fixed.) Each external input and each gate is assigned a unique integer. Each is also assigned a variable whose value is the value of the external input or gate. The ith vertex is assigned the variable xi. If xi is associated with a gate that combines the results produced at the jth and kth gates with the operator ⊙, we write an assignment operation of the form xi := xj ⊙ xk. The sequence of assignment operations for a circuit is a straight-line program. Below is a straight-line program for the circuit of Fig. 2:

x4 := x1 ⊕ x2

x5 := x4 ∧ x3

x6 := x1 ∧ x2

x7 := x4 ⊕ x3

x8 := x5 ∨ x6

The values computed for (x8, x7) are the standard binary representation for the number of 1's among x1, x2, and x3. This can be seen by constructing a table of values for x1, x2, x3, x7, As shown in the truth table for Fig. 2(c), each logic circuit has associated with it a binary function that maps the values of its input variables to the values of its output variables. In the case of the full-adder, since x8 and x7 are its output variables, we associate with it the function f(3,2)

FA : B3 7→ B2, whose value is f(3,2)

FA (x1, x2, x3) = (x8, x7).

Algebraic circuits are similar to logic circuits except they may use operations over nonbinary sets, such as addition and multiplication over a ring and they execute straight-line programs where the operators are non-binary functions. Algebraic circuits also have associated with them functions that map the values of inputs to the values of outputs.

Logic circuits are the basic building blocks of all digital computers today. When such circuits are combined with binary memory cells, machines with memory can be constructed. The models for these machines are called finite-state machines.


The finite-state machine (FSM) is a machine with memory. It executes a series of steps during each of which it takes its current state from the set Q of states and current external input from the set § of input letters and combines them in a logic circuit L to produce a successor state in Q and an output letter. The logic circuit L can be viewed as having two parts, one that computes the next-state function δ : Q - § 7→ Q, whose value is the next state of the FSM, and the other that computes the output function λ : Q 7→ ª,whose value is the output of the FSM in the current state.

(a) The finite-state machine (FSM) model; at each unit of time its logic unit, L, operates on its current state (taken from its memory) and its current external input to compute an external output and a new state that it stores in its memory.

(b) An FSMthat holds in its memory a bit that is the EXCLUSIVE OR of the initial value stored in its memory and the external inputs received to the present time.

A generic finite-state machine is shown in Fig. (a) along with a concrete FSM in Fig. (b) that provides as successor state and output the EXCLUSIVE OR of the current state and the external input. The state diagram of the FSM in Fig. (b) Two (or more) finite-state machines that.

In operate in lockstep can be interconnected to form a single FSM. In this case, some outputs of one FSM serve as inputs to the other.

Finite-state machines are ubiquitous today. They are found in microwave ovens, VCRs and automobiles. They can be simple or complex. One of the most useful FSMs is the general purpose computer modeled by the random-access machine.


The finite-state machine (FSM) has a set of states, one of which is its initial state. At each unitof time an FSM is given a letter from its input alphabet. This causes the machine to move from its current state to a potentially new state. While in a state, the FSM produces a letter from its output alphabet. Such a machine computes the function defined by the mapping from its initial state and strings of input letters to strings of outputThe next-state and output functions of an FSM, δ and λ, can be represented as in Fig..We visualize these functions taking a state value from a memory and an input value from an external input and producing next-state and output values. Next-state values are stored in the memory and output values are released to the external world. From this representation an actual machine (a sequential circuit) can be constructed Once circuits are constructed for δ and λ, we need only add memory units and a clock to construct a sequential circuit that emulates an FSM.

The finite-state machine model.

A finite-state machine computing the EXCLUSIVE OR of its inputs.

An example of an FSM is shown in Fig. . Its input and output alphabets and state sets are § = {0, 1}, ª = {0, 1}, and Q = {q0, q1}, respectively. Its next-state and output functions, δ and λ, are given below. The FSM has initial state q0 and final state q1. As a convenience we explicitly identify final states by shading, although in practice they can be associated with states producing a particular output letter.

Each state has a label qj/vj , where qj is the name of the state and vj is the output produced while in this state. The initial state has an arrow labeled with the word "start" pointing to it. Clearly, the set of strings accepted by this FSM are those containing an odd number of instances of 1. Thus it computes the EXCLUSIVE OR function on an arbitrary number of inputs.

While it is conventional to think of the finite-state machine as a severely restricted computational model, it is actually a very powerful one. The random-access machine (RAM) is an FSM when the number of memory locations that it contains is bounded, as is always so in practice. When a program is first placed in the memory of the RAM, the program sets the initial state of the RAM. The RAM, which may or may not read external inputs or produce external outputs, generally will leave its result in its memory; that is, the result of the computation often determines the final state of the random-access machine.


The random-access machine (RAM) models the essential features of the traditional serial computer. The RAM is modeled by two synchronous interconnected FSMs, a central processing unit (CPU) and a random-access memory. The CPU has a small number of storage locations called registers whereas the random-access memory has a large number.All operations performed by the CPU are performed on data stored in its registers. This is done for efficiency; no increase in functionality is obtained by allowing operations on data stored in memory locations as well.


The CPU implements a fetch-and-execute cycle in which it alternately reads an instruction from a program stored in the random-access memory (the stored-program concept) and executes it. Instructions are read and executed from consecutive locations in the random-access memory unless a jump instruction is executed, in which case an instruction from a nonconsecutive location is executed next.

A CPU typically has five basic kinds of instruction: a) arithmetic and logical instructions, b) memory load and store instructions for moving data between memory locations and registers, c) jump instructions for breaking out of the current program sequence, d) input and output (I/O) instructions, and e) a halt instruction.

The basic random-access memory has an output word (out wrd) and three input words, an address (addr), a data word (in wrd), and a command (cmd). The command specifies one of three actions, a) read from a memory location, b) write to a memory location, or c) do nothing. Reading from address addr deposits the value of the word at this location into out wrd whereas writing to addr replaces the word at this address with the value of in wrd.

The random-access machine has a central processing unit (CPU) and a random access memory unit

This memory is called random-access because the time to access a word is the same for all words. The Turing machine introduced has a tape memory in which the time to access a word increases with its distance from the tape head. The random-access memory in the model has m = 2μ storage locations each containing a b-bit word, where μ and b are integers. Each word has a μ-bit address and the addresses are consecutive starting at zero. The combination of this memory and the CPU described above is the bounded-memory RAM. When no limit is placed on the number and size of memory words, this combination defines the unbounded-memory RAM. We use the term RAM for these two machines when context unambiguously determines which is intended.



The CPU and the random-access memory are both finite-state machines. The CPU receives input from the random-access memory as well as from external sources. Its output is to the memory and the output port. Its state is determined by the contents of its registers. The random-access memory receives input from and produces output to the CPU. Its state is represented by an m-tuple (w0,w1, . . . ,wm−1) of b-bit words, one per memory location, as well as by the values of in wrd, out word, and addr. We say that the random-access memory has a storage capacity of S = mb bits. The RAM has input and output registers (not shown in Fig. 3.17) through which it reads external inputs and produces external outputs.

As the RAM example illustrates, some FSMs are programmable. In fact, a program stored in the RAM memory selects one of very many state sequences that the RAM may execute. The number of states of a RAM can be very large; just the random-access memory alone has more than 2S states. The programmability of the unbounded-memory RAM makes it universal for FSMs, Before taking up this subject, we pause to introduce an assembly language program for the unbounded-memory RAM.


We now introduce assembly-language programs to make concrete the use of the RAM. An assembly language contains one instruction for each machine-level instruction of a CPU. However, instead of bit patterns, it uses mnemonics for opcodes and labels as symbolic addresses. Labels are used in jump instructions.

CPU defined in Section 1and vice versa if the CPU has a sufficiently long word length. Our new assembly language treats all memory locations as equivalent and calls them registers. Thus, no distinction is made between the memory locations in the CPU and those in the random-access memory. Such a distinction is made on real machines for efficiency: it is much quicker to access registers internal to a CPU than memory locations in an external random-access memory. Registers are used for data storage and contain integers. Register names are drawn from the set {R0, R1, R2, . . .}. The address of register Ri is i. Thus, both the number of registers and their size are potentially unlimited. All registers are initialized with the value zero. Registers used as input registers to a program are initialized to input values. Results of a computation are placed in output registers. Such registers may also serve as input registers. Each instruction may be given a label drawn from the set {N0,N1,N2, . . .}. Labels are used by jump instructions, as explained below. The meaning of each instruction should be clear except possibly for the CONTINUE and JUMP. If the program reaches a CONTINUE statement other than the last CONTINUE, it executes the following instruction. If it reaches the last CONTINUE statement, the program halts.

The jump instructions Rj JMP+ Ni, Rj JMP− Ni, JMP+ Ni, and JMP− Ni cause a break in the program sequence. Instead of executing the next instruction in sequence, they cause jumps to instructions with labels Ni. In the first two cases these jumps occur only when the content of register Rj is zero. In the last two cases, these jumps occur unconditionally. The instructions with JMP+ (JMP−) cause a jump to the closest instruction with label Ni above (below) the current instruction. The use of the suffixes + and − permit the insertion of program fragments into an existing program without relabeling instructions.

A RAM program is a finite sequence of assembly language instructions terminated with CONTINUE. A valid program is one for which each jump is to an existing label. A halting program is one that halts.


In this section we model the random-access memory described as an FSM

MRMEM(μ, b) that has m = 2μ b-bit data words, w0,w1, . . . ,wm−1, as well as an input data word d (in wrd), an input address a (addr), and an output data word z (out wrd). (See output words, input address, and the command word. We construct an efficient logic circuit for its next-state and transition function.

To simplify the design of the FSM MRMEM we use the following encodings of the three input commands:

An input to MRMEM is a binary (μ + b + 2)-bit binary tuple, two bits to represent a command, μ bits to specify an address, and b bits to specify a data word. The output function of MRMEM, λRMEM, is a simple projection operator and is realized by a circuit without any gates. Applied to the state vector, it produces the output word.

We now describe a circuit for δRMEM, the next-state function ofMRMEM. Memory words remain unchanged if either no-op or read commands are executed. In these cases the value of the command bit s1 is 0. One memory word changes if s1 = 1, namely, the one whose address is a. Thus, the memory words w0,w1, . . . ,wm−1 change only when s1 = 1.

A random-access memory unit MRMEM that holds m b-bit words. Its inputs consist of a command (cmd), an input word (in wrd), and an address (addr). It has one output word (out wrd).


The Turing machine model is the classical model introduced by Alan Turing in his famous 1936 paper [337]. No other model of computation has been found that can compute functions that a Turing machine cannot compute. The Turing machine is a canonical model of computation used by theoreticians to understand the limits on serial computation, a topic that is explored in Chapter 5. The Turing machine also serves as the primary vehicle for the classification of problems by their use of space and time. The (deterministic) one-tape, bounded-memory Turing machine (TM) consists of two interconnected FSMs, a control unit and a tape unit of potentially unlimited storage capacity. (It is shown schematically in Fig.At each unit of time the control unit accepts input from the tape unit and supplies output to it. The tape unit produces the value in the cell under the head, a b-bit word, and accepts and writes a b-bit word to that cell. It also accepts commands to move the head one cell to the left or right or not at all. The bounded-memory tape unit is an array of m b-bit cells and has a storage capacity of S = mb bits.

A formal definition of the one-tape deterministic Turing machine is below:

The multi-tape Turing machine is a generalization of this model that has multiple tape units. (These models and limits on their ability to solve problems are examined where it is shown that the multi-tape TM is no more powerful than the one-tape TM.) Although in practice a TM uses a bounded number of memory locations, the full power of TMs is realized only when they have access to an unbounded number of tape cells.


A pushdown automaton (PDA) is a six-tuple M = (§, ¡,Q,¢, s, F), where § is the tape alphabet containing the blank symbol β, ¡ is the stack alphabet containing the blank symbol γ, Qis the finite set of states,¢ ⊆ (Q-(§∪{Ç«})-(¡∪{Ç«})-Q-(¡∪{Ç«})) is the set of transitions, s is the initial state, and F is the set of final states. We now describe transitions.

If for state p, tape symbol x, and stack symbol y the transition (p, x, y; q, z) ∈ ¢, then if M is in state p, x ∈ § is under its tape head, and y ∈ ¡ is at the top of its stack, M may pop y from its stack, enter state q ∈ Q, and push z ∈ ¡ onto its stack. However, if x = Ç«, y = Ç« or z = Ç«, then M does not read its tape, pop its stack or push onto its stack, respectively. The head on the tape either remains stationary if x = Ç« or advances one cell to the right if x 6= Ç«. If at each point in time a unique transition (p, x, y; q, z) may be applied, the PDA is deterministic. Otherwise it is nondeterministic.

The PDA M accepts the input string w ∈ § if when started in state s with an empty stack (its cells contain the blank stack symbol γ) andw placed left-adjusted on its otherwise blank tape (its blank cells contain the blank tape symbol β), the last state entered by M after reading components of w and no other tape cells is a member of the set F. M accepts the language (M) consisting of all such strings.

The pushdown automaton (PDA) has a one-way, read-only, potentially infinite input tape on which an input string is written ; its head either advances to the right from the leftmost cell or remains stationary. It also has a stack, a storage medium analogous to the stack of trays in a cafeteria. The stack is a potentially infinite ordered collection of initially blank cells with the property that data can be pushed onto it or popped from it. Data is pushed onto the top of the stack by moving all existing entries down one cell and inserting the new element in the top location. Data is popped by removing the top element and moving all other entries up one cell. The control unit of a pushdown automaton is a finite-state machine. The full power of the PDA is realized only when its control unit is nondeterministic. Some of the special cases for the action of the PDA M on empty tape or stack symbols are the following: if (p, x, Ç«; q, z), x is read, state q is entered, and z is pushed onto the stack; if (p, x, y; q, Ç«), x is read, state q is entered, and y is popped from the stack; if (p, Ç«, y; q, z), no input is read, y is popped, z is pushed and state q is entered. Also, if (p, Ç«, Ç«; q, Ç«), M moves from state p to q without reading input, or pushing or popping the stack.

Observe that if every transition is of the form (p, x, Ç«; q, Ç«), the PDA ignores the stack and simulates an FSM. Thus, the languages accepted by PDAs include the regular languages. We emphasize that a PDA is nondeterministic if for some state q, tape symbol x, and top stack item y there is more than one transition that M can make. For example, if ¢ contains (s, a, Ç«; s, a) and (s, a, a; r, Ç«), M has the choice of ignoring or popping the top of the stack and of moving to state s or r. If after reading all symbols of w M enters a state in F, thenM accepts w.

We now give two examples of PDAs and the languages they accept. The first accepts palindromes of the form {wcwR}, where wR is the reverse of w and w ∈ {a, b}. The state diagram of its control unit The second PDA accepts those strings over {a, b} of the form anbm for which n ≥ m. The control unit, one-way input tape, and stack of a pushdown automaton.