BE Computer Engineering (Pokhara University) Theory of Computation (PU, CMP 264) Question Paper 2078 Nepal

(a) DFA vs NFA (5 marks)

Role of the transition function: In a DFA, $\delta$ is a total function returning a single state, so the run is deterministic. In an NFA, $\delta$ returns a set of states, so from one configuration the machine may proceed along many branches in parallel. Both recognise exactly the regular languages (Rabin–Scott theorem), and every NFA can be converted to an equivalent DFA by subset construction.

(b) NFA → DFA by subset construction (10 marks)

We want strings over $\{0,1\}$ that contain 01 OR end in 00. An NFA $N$ for this (states for the two patterns merged) has the following $\epsilon$-free transitions. Let the start state be $A$. We design $N$ directly:

• $A$: looking for either pattern
• $B$: just saw a 0 (potential start of 01 or 00)
• $C$: substring 01 found — accept (and stay accepting)
• $D$: saw 00 so far — accept, but pattern may be broken by later input unless string ends here

NFA transition relation $\delta_N$:

Final states of $N$: $C, D$ (note $D$ accepts only when the string ends right after 00).

Subset construction. Start = $\{A\}$.

Final (accepting) DFA states: every subset containing $C$ or $D$, i.e. $S_2$ (contains $D$), $S_3, S_4, S_5$ (contain $C$). $S_2$ is accepting because reaching it means 00 was just read.

Transition diagram (described):

• Start arrow into $S_0$.
• $S_0 \xrightarrow{0} S_1$, $S_0 \xrightarrow{1} S_0$.
• $S_1 \xrightarrow{0} S_2$, $S_1 \xrightarrow{1} S_3$.
• $S_2 \xrightarrow{0} S_2$, $S_2 \xrightarrow{1} S_3$.
• $S_3 \xrightarrow{0} S_4$, $S_3 \xrightarrow{1} S_3$ (self-loop).
• $S_4 \xrightarrow{0} S_5$, $S_4 \xrightarrow{1} S_3$.
• $S_5 \xrightarrow{0} S_5$ (self-loop), $S_5 \xrightarrow{1} S_3$.
• Double circles (final): $S_2, S_3, S_4, S_5$.

Once the DFA enters $S_3$ (substring 01 seen) it can never leave the accepting region, exactly capturing the "contains 01" condition, while $S_2/S_4/S_5$ capture "ends in 00".

(a) CFG definition and design (7 marks)

A Context-Free Grammar is a 4-tuple $G = (V, T, P, S)$ where:

• $V$ = finite set of variables (non-terminals),
• $T$ = finite set of terminals, $V \cap T = \emptyset$,
• $P$ = finite set of productions of the form $A \to \alpha$, with $A \in V$ and $\alpha \in (V \cup T)^{*}$,
• $S \in V$ = start symbol.

Grammar for $L = \{a^{n} b^{m} c^{m} d^{n} \mid n \ge 1, m \ge 0\}$:

$$S \to a\,S\,d \mid a\,B\,d, \qquad B \to b\,B\,c \mid \epsilon$$

Here the $S$-rules generate matching outer $a\ldots d$ pairs ($n \ge 1$), and $B$ generates the matched inner $b\ldots c$ pairs ($m \ge 0$).

Is aabccbb in $L$? A string of $L$ must have the strict order $a^{n}b^{m}c^{m}d^{n}$: all $a$'s, then $b$'s, then $c$'s, then $d$'s, with $\#a = \#d$ and $\#b = \#c$. The string aabccbb has letters in the order $a,a,b,c,c,b,b$ — a b appears after c, and there is no d. So the order is violated and $\#d = 0 \ne \#a = 2$. Hence aabccbb $\notin L$, and no derivation exists.

(For completeness, a valid string such as aabccd has the leftmost derivation: $S \Rightarrow aSd \Rightarrow aaBdd$? — note $\#a$ must equal $\#d$. Take aabccd is invalid too since $\#a=2,\#d=1$. A correct member is aabbccdd:*

$$S \Rightarrow aSd \Rightarrow aaBdd \Rightarrow aabBcdd \Rightarrow aabbBccdd \Rightarrow aabb\,\epsilon\,ccdd = aabbccdd.)*$$

(b) Conversion to Chomsky Normal Form (8 marks)

Given $S \to ASB \mid \epsilon, \;\; A \to aAS \mid a, \;\; B \to SbS \mid A \mid bb$.

Step 1 — Add new start symbol. $S_0 \to S$ (so the start symbol never appears on a RHS).

Step 2 — Remove $\epsilon$-productions. Nullable variables: $S$ (from $S\to\epsilon$). $B \to SbS$ does not become nullable (the $b$ stays). Substitute nullable $S$ in all RHSs and drop $S\to\epsilon$:

• $S_0 \to S$
• $S \to ASB \mid AB$ (drop one or both $S$… here only outer/inner $S$ in $ASB$ is the middle $S$): $ASB$ with the $S$ removed gives $AB$. So $S \to ASB \mid AB$.
• $A \to aAS \mid aA \mid a$ (remove $S$ from $aAS$ gives $aA$)
• $B \to SbS \mid Sb \mid bS \mid b \mid A \mid bb$ (delete each nullable $S$)

Step 3 — Remove unit productions. Units: $S_0 \to S$, $B \to A$.

• $S_0$ inherits $S$'s rules: $S_0 \to ASB \mid AB$.
• $B \to A$ ⇒ $B$ inherits $A$'s rules: $B \to aAS \mid aA \mid a$. Now $B \to SbS \mid Sb \mid bS \mid b \mid bb \mid aAS \mid aA \mid a$.

Step 4 — Remove useless symbols. All of $S_0,S,A,B$ are reachable and generate terminal strings, so none are removed.

Step 5 — Make all bodies length-2 of variables, or a single terminal. Introduce terminal variables $X_a \to a$, $X_b \to b$, and break long bodies with helper variables.

Final CNF grammar:

S0 -> A C1 | A B          (C1 -> S B)
S  -> A C1 | A B
A  -> X_a C2 | X_a A | a   (C2 -> A S)
B  -> S C3 | S X_b | X_b S | b | X_b X_b
       | X_a C2 | X_a A | a
       (C3 -> X_b S)
C1 -> S B
C2 -> A S
C3 -> X_b S
X_a -> a
X_b -> b

Every production now has the form $A \to BC$ (two variables) or $A \to a$ (single terminal), so the grammar is in Chomsky Normal Form.

(a) Formal model of a single-tape Turing Machine (5 marks)

A standard Turing Machine is a 7-tuple $M = (Q, \Sigma, \Gamma, \delta, q_0, q_{accept}, q_{reject})$ where:

• $Q$ = finite set of states,
• $\Sigma$ = input alphabet (blank $\sqcup \notin \Sigma$),
• $\Gamma$ = tape alphabet, $\Sigma \subseteq \Gamma$ and $\sqcup \in \Gamma$,
• $\delta : Q \times \Gamma \to Q \times \Gamma \times \{L, R\}$ = transition function (read symbol, write symbol, move head Left/Right),
• $q_0 \in Q$ = start state,
• $q_{accept}, q_{reject} \in Q$ = accepting and rejecting (halting) states, $q_{accept} \ne q_{reject}$.

Behaviour on input $w$: $M$ starts in $q_0$ with $w$ on the tape and head on the first symbol. At each step it reads the current cell, writes a symbol, moves L or R, and changes state per $\delta$. There are three outcomes:

• Accept — it reaches $q_{accept}$ (halts, $w \in L(M)$);
• Reject — it reaches $q_{reject}$ (halts, $w \notin L(M)$);
• Loop — it never halts.

A language is recursively enumerable if some TM accepts it; it is recursive (decidable) if some TM halts on every input (never loops).

(b) TM for $L = \{w c w^{R} \mid w \in \{a,b\}^{*}\}$ (10 marks)

Idea: Match the outermost symbols against the innermost, working from both ends toward the centre c. Read and erase (mark) the first unmarked symbol, then move right to the corresponding last unmarked symbol and check it equals the one remembered. The single center c must remain when all of $w,w^R$ are matched.

Let $X$ mark a consumed cell. States: $q_0$ (start/find left symbol), $q_a,q_b$ (carry remembered symbol rightward), $q_{a'},q_{b'}$ (after matching, return left), $q_c$ (check center), $q_{acc}$, $q_{rej}$.

Transition table (entry = write, move, next state):

(In words: $q_a/q_b$ scan right to the rightmost unmarked symbol; states $q_{a'}/q_{b'}$ verify that symbol matches the remembered one and mark it; $q_{ret}$ rewinds to the left end; $q_c$ checks that only the single c remains, then accepts.)

Trace on abcba (tape shown, head position underlined conceptually; $X$ = matched):

1. a b c b a, $q_0$: read a → mark, remember a, go right: X b c b a, $q_a$.
2. $q_a$ scans right over b,c,b to last a; matches remembered a → mark: X b c b X, return left.
3. Back at left, $q_0$ reads b → mark, remember b: X X c b X, $q_b$.
4. $q_b$ scans right to last unmarked b; matches → mark: X X c X X, return left.
5. $q_0$ reads c → enter center-check $q_c$: tape X X c X X, only the single c is unmatched, surrounding all $X$ → accept.

Since every $a$/$b$ on the left matched its mirror on the right and exactly one c separates them, abcba ($w=ab$, $w^R=ba$) is accepted.

(a) PDA definition; final state vs empty stack (5 marks)

A Pushdown Automaton is a 7-tuple $M = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$ where:

• $Q$ = finite set of states,
• $\Sigma$ = input alphabet,
• $\Gamma$ = stack alphabet,
• $\delta : Q \times (\Sigma \cup \{\epsilon\}) \times \Gamma \to$ finite subsets of $Q \times \Gamma^{*}$ (transition function),
• $q_0 \in Q$ = start state,
• $Z_0 \in \Gamma$ = initial stack symbol,
• $F \subseteq Q$ = set of final states.

A PDA augments a finite control with an unbounded stack (LIFO), giving it the extra memory needed to recognise context-free languages.

Acceptance by final state: the input is accepted if, after reading all input, the PDA is in some state of $F$ (stack contents irrelevant):

$$L(M) = \{ w \mid (q_0, w, Z_0) \vdash^{*} (q, \epsilon, \gamma),\ q \in F \}.$$

Acceptance by empty stack: the input is accepted if, after reading all input, the stack is empty (final state irrelevant):

$$N(M) = \{ w \mid (q_0, w, Z_0) \vdash^{*} (q, \epsilon, \epsilon) \}.$$

The two modes recognise the same class (context-free languages); each can be converted to the other.

(b) PDA for $L = \{a^{n} b^{2n} \mid n \ge 1\}$ by empty stack (10 marks)

Idea: For each a, push two stack symbols; for each b, pop one. Then $n$ a's push $2n$ markers and $2n$ b's pop them, leaving the stack empty exactly when the count matches.

Let $M = (\{q_0, q_1\}, \{a,b\}, \{Z_0, A\}, \delta, q_0, Z_0, \emptyset)$ (empty-stack acceptance).

Transition function:

1. $\delta(q_0, a, Z_0) = \{(q_0, AAZ_0)\}$ — first a: push two $A$'s above $Z_0$.
2. $\delta(q_0, a, A) = \{(q_0, AAA)\}$ — each further a: push two more $A$'s.
3. $\delta(q_0, b, A) = \{(q_1, \epsilon)\}$ — first b: pop one $A$, switch to $q_1$.
4. $\delta(q_1, b, A) = \{(q_1, \epsilon)\}$ — each further b: pop one $A$.
5. $\delta(q_1, \epsilon, Z_0) = \{(q_1, \epsilon)\}$ — when all $A$'s gone, pop $Z_0$ to empty the stack.

Moves (instantaneous descriptions) on aabbbb ($n=2$, so $2n=4$ b's):

$$\begin{aligned} (q_0,\ aabbbb,\ Z_0) &\vdash (q_0,\ abbbb,\ AAZ_0) &&\text{rule 1}\\ &\vdash (q_0,\ bbbb,\ AAAAZ_0) &&\text{rule 2}\\ &\vdash (q_1,\ bbb,\ AAAZ_0) &&\text{rule 3}\\ &\vdash (q_1,\ bb,\ AAZ_0) &&\text{rule 4}\\ &\vdash (q_1,\ b,\ AZ_0) &&\text{rule 4}\\ &\vdash (q_1,\ \epsilon,\ Z_0) &&\text{rule 4}\\ &\vdash (q_1,\ \epsilon,\ \epsilon) &&\text{rule 5} \end{aligned}$$

All input is consumed and the stack is empty, so aabbbb is accepted. The two a's pushed four $A$'s, the four b's popped them, and $Z_0$ was finally popped — confirming $a^{2}b^{4} \in L$.

Pumping Lemma for Regular Languages

If $L$ is regular, then there exists a constant $p \ge 1$ (the pumping length) such that every string $w \in L$ with $|w| \ge p$ can be split as $w = xyz$ satisfying:

1. $|y| \ge 1$ (i.e. $y \ne \epsilon$),
2. $|xy| \le p$,
3. $xy^{k}z \in L$ for all $k \ge 0$.

Proof that $L = \{a^{i} b^{j} \mid i > j \ge 0\}$ is not regular

Assume, for contradiction, that $L$ is regular with pumping length $p$.

Choose $w = a^{p+1} b^{p}$. Then $i = p+1 > j = p$, so $w \in L$ and $|w| \ge p$.

By the lemma, $w = xyz$ with $|xy| \le p$ and $|y| \ge 1$. Since the first $p$ symbols of $w$ are all a's, both $x$ and $y$ lie within the $a$-block, so $y = a^{m}$ for some $m \ge 1$.

Now pump down with $k = 0$: $xy^{0}z = a^{(p+1) - m} b^{p}$.

The number of a's is $(p+1) - m \le (p+1) - 1 = p$, while the number of b's is still $p$. So $i = p+1-m \le p = j$, which violates the requirement $i > j$. Hence $xy^{0}z \notin L$.

This contradicts the pumping lemma. Therefore $L$ is not regular. $\blacksquare$

(a) Regular expressions (4 marks)

(i) All strings of even length over $\{0,1\}$ — any two symbols repeated zero or more times:

$$\big((0+1)(0+1)\big)^{*}$$

(The empty string, of length 0, is included.)

(ii) Every 0 is immediately followed by at least one 1. A 0 may never be the last symbol and never be directly followed by another 0. Equivalently, every 0 comes as the block 01. Such strings are made of the blocks 1 and 01 repeated:

$$\big(1 + 01\big)^{*}$$

(b) Identities for regular expressions and simplification (3 marks)

Useful algebraic identities (with $\emptyset$ = empty set, $\epsilon$ = empty string):

• $r + r = r$ (idempotence of $+$)
• $\epsilon\, r = r\, \epsilon = r$ (identity of concatenation)
• $(\epsilon + r)^{*} = r^{*}$
• $r^{*} r^{*} = r^{*}$, $(r^{*})^{*} = r^{*}$
• $\emptyset\, r = r\, \emptyset = \emptyset$, $\;\emptyset + r = r$

Simplify $(\epsilon + 0)^{*}\, 1\, (\epsilon + 0)^{*}$:

$$(\epsilon + 0)^{*}\,1\,(\epsilon + 0)^{*} = 0^{*}\,1\,0^{*}$$

using the identity $(\epsilon + 0)^{*} = 0^{*}$ on each factor. The resulting expression $0^{*} 1 0^{*}$ denotes all strings over $\{0,1\}$ containing exactly one 1.

Decidable vs Undecidable problems

• A decidable (recursive) problem is one for which there exists an algorithm — a Turing machine that halts on every input and answers "yes" or "no" correctly. Example: "Does DFA $M$ accept string $w$?"
• An undecidable problem is one for which no such always-halting algorithm exists; any TM that decides it must loop forever on at least some inputs. Undecidable problems may still be recognisable (semi-decidable) if a TM halts and accepts on "yes" instances but may loop on "no" instances.

The Halting Problem

Statement: Given (an encoding of) an arbitrary Turing machine $M$ and an input string $w$, decide whether $M$ halts when run on $w$. Formally, decide membership in

$$HALT = \{ \langle M, w \rangle \mid M \text{ halts on } w \}.$$

The Halting Problem is undecidable.

Proof outline (by contradiction / diagonalization):

1. Suppose a TM $H$ decides $HALT$: $H(\langle M, w\rangle)$ halts and outputs "halts" if $M$ halts on $w$, and "loops" otherwise.
2. Construct a new machine $D$ that takes input $\langle M \rangle$ and runs $H$ on $\langle M, \langle M\rangle\rangle$ (i.e. asks whether $M$ halts on its own description):
   • If $H$ says "$M$ halts on $\langle M\rangle$", then $D$ loops forever.
   • If $H$ says "$M$ loops on $\langle M\rangle$", then $D$ halts.
3. Now run $D$ on its own description $\langle D \rangle$:
   • If $D$ halts on $\langle D\rangle$, then by construction $D$ loops on $\langle D\rangle$ — contradiction.
   • If $D$ loops on $\langle D\rangle$, then by construction $D$ halts on $\langle D\rangle$ — contradiction.
4. Either way we reach a contradiction, so the assumed decider $H$ cannot exist.

Therefore the Halting Problem is undecidable. $\blacksquare$

(a) P, NP, NP-Complete and the P =? NP question (4 marks)

• P (Polynomial time): the class of decision problems solvable by a deterministic Turing machine in time polynomial in the input size, $O(n^{k})$. These are the "efficiently solvable" problems (e.g. sorting, shortest path, primality).
• NP (Nondeterministic Polynomial time): the class of decision problems for which a proposed solution ("certificate") can be verified by a deterministic TM in polynomial time — equivalently, solvable by a nondeterministic TM in polynomial time. $P \subseteq NP$.
• NP-Complete: a problem $X$ is NP-complete if (i) $X \in NP$, and (ii) every problem in NP reduces to $X$ in polynomial time ($X$ is NP-hard). These are the "hardest" problems in NP; SAT was the first proved NP-complete (Cook–Levin theorem).

Significance of $P \stackrel{?}{=} NP$: It asks whether every problem whose solution can be verified quickly can also be solved quickly. If $P = NP$, every NP-complete problem (SAT, TSP, etc.) would have an efficient algorithm, with huge consequences (e.g. cryptography would break). It is one of the major open problems in computer science; it is widely conjectured that $P \ne NP$.

(b) Polynomial-time reduction and its role (3 marks)

A polynomial-time (many-one) reduction from problem $A$ to problem $B$, written $A \le_{p} B$, is a function $f$ computable in polynomial time such that for every input $x$:

$$x \in A \iff f(x) \in B.$$

It transforms instances of $A$ into instances of $B$ while preserving yes/no answers, in polynomial time.

Role in NP-completeness proofs: To prove a new problem $B$ is NP-complete we (1) show $B \in NP$, and (2) pick a known NP-complete problem $A$ and show $A \le_{p} B$. Because every problem in NP already reduces to $A$, and reductions compose, this makes $B$ NP-hard; together with $B \in NP$, $B$ is NP-complete. The reduction "transfers hardness": if $B$ had a polynomial algorithm, so would $A$ and hence all of NP.

Moore vs Mealy machine

Both are finite-state transducers and are equivalent in expressive power (each can be converted to the other).

Mealy machine that outputs 1 when input ends in 101

We track how much of the suffix 101 has been seen. Output is on each transition (1 only when the move completes 101).

States:

• $S_0$ — no useful suffix (start)
• $S_1$ — last symbol matched 1 (prefix 1 of 101)
• $S_2$ — last symbols matched 10 (prefix 10)

Transition / output table (next state, output):

Explanation of key edges:

• From $S_2$ (10 seen) on input 1 we complete 101 → output 1, and the trailing 1 is itself a fresh prefix, so we go to $S_1$.
• On any 1 we move to $S_1$ (a 1 always starts a new potential match), except the accepting edge above which also lands in $S_1$.
• On 0 from $S_1$ we have 10 → go to $S_2$; on 0 from $S_2$ the partial match breaks → $S_0$.

Trace on 1101: $S_0 \xrightarrow{1/0} S_1 \xrightarrow{1/0} S_1 \xrightarrow{0/0} S_2 \xrightarrow{1/1} S_1$. Output stream 0001 — the final 1 correctly signals that the input ends in 101.

Ambiguous grammar

A context-free grammar $G$ is ambiguous if there exists at least one string $w \in L(G)$ that has two or more distinct parse trees (equivalently, two distinct leftmost derivations, or two distinct rightmost derivations). Ambiguity is a property of the grammar, not of the language.

Showing $E \to E + E \mid E * E \mid (E) \mid id$ is ambiguous

The string id + id * id has two different parse trees because the grammar does not fix the precedence of + and *.

Parse tree 1 — interprets as $id + (id * id)$ (multiplication grouped first):

          E
        / | \
       E  +  E
       |    /|\
      id   E * E
           |   |
          id  id

Leftmost derivation: $E \Rightarrow E + E \Rightarrow id + E \Rightarrow id + E * E \Rightarrow id + id * E \Rightarrow id + id * id$.

Parse tree 2 — interprets as $(id + id) * id$ (addition grouped first):

          E
        / | \
       E  *  E
      /|\    |
     E + E  id
     |   |
    id  id

Leftmost derivation: $E \Rightarrow E * E \Rightarrow E + E * E \Rightarrow id + E * E \Rightarrow id + id * E \Rightarrow id + id * id$.

Both trees derive the same terminal string id + id * id but have different structures (root operator + vs *). Since one string has two distinct parse trees, the grammar is ambiguous. $\blacksquare$

(This is usually fixed by introducing precedence/associativity levels: $E \to E + T \mid T,\; T \to T * F \mid F,\; F \to (E) \mid id$.)

(a) Three closure properties of regular languages (4 marks)

Let $L_1, L_2$ be regular languages over $\Sigma$.

1. Union: $L_1 \cup L_2$ is regular. Justification: given NFAs (or regular expressions) $r_1, r_2$ for them, $r_1 + r_2$ describes the union; equivalently a new start state with $\epsilon$-moves to both NFAs accepts $L_1 \cup L_2$.
2. Concatenation: $L_1 L_2$ is regular. Justification: the regular expression $r_1 r_2$ denotes it; or link the final states of the first NFA by $\epsilon$-moves to the start of the second.
3. Complementation: $\overline{L_1} = \Sigma^{*} \setminus L_1$ is regular. Justification: take a complete DFA for $L_1$ and swap accepting and non-accepting states; the resulting DFA accepts exactly the strings $L_1$ rejects.

(Other closures: intersection, Kleene star, reversal, difference — all regular.)

(b) Recursive and recursively enumerable languages (3 marks)

• A language $L$ is recursive (decidable) if there is a Turing machine that halts on every input and accepts exactly the strings in $L$ (it answers yes/no for all inputs and always terminates).
• A language $L$ is recursively enumerable (RE / Turing-recognisable) if there is a Turing machine that accepts (halts on) every string in $L$, but on strings not in $L$ it may either reject or loop forever.

Relationship: Every recursive language is recursively enumerable, i.e. Recursive $\subsetneq$ RE. The containment is strict: there exist RE languages that are not recursive (e.g. the language of the Halting Problem). Also, $L$ is recursive iff both $L$ and its complement $\overline{L}$ are recursively enumerable.

(a) Church–Turing Thesis (4 marks)

Statement: Every function that is effectively computable (computable by any well-defined mechanical/algorithmic procedure) can be computed by a Turing machine. In other words, the intuitive notion of "algorithm" coincides exactly with what Turing machines can compute.

It is a thesis (hypothesis), not a theorem, because "effectively computable" is an informal notion that cannot be proved equal to a formal model. Its strong support comes from the fact that every reasonable model of computation proposed — $\lambda$-calculus, recursive functions, RAM machines, while-programs, modern programming languages — has been shown equivalent in power to the Turing machine.

Significance:

• It justifies using the Turing machine as the standard definition of computability and algorithm.
• It lets us prove a problem is unsolvable by any algorithm by showing no Turing machine solves it (e.g. the Halting Problem).
• It underpins the whole theory of decidability and the classification of problems.

(b) Multi-tape TM equivalence to single-tape TM (3 marks)

A multi-tape TM has $k$ tapes each with its own independent head; one step reads/writes/moves all $k$ heads. It is clearly at least as powerful as a single-tape TM.

Single-tape simulation: A single-tape TM $S$ can simulate a $k$-tape TM $M$ by storing the contents of all $k$ tapes on its one tape, separated by a delimiter $\#$, and marking each tape's head position with a special "dotted" symbol:

$$\#\ \dot t_1 \ldots \#\ \dot t_2 \ldots \#\ \dot t_k \ldots \#$$

To simulate one step of $M$, $S$ sweeps left-to-right over the whole tape to read the $k$ marked symbols, then sweeps again to write the new symbols and shift the dot markers, expanding the tape if a head runs off its region.

Conclusion: $S$ recognises exactly the same language as $M$, so multi-tape and single-tape TMs are equivalent in computational power (they recognise the same class — the recursively enumerable languages). The only cost is efficiency: $t$ steps of $M$ take $O(t^{2})$ steps on $S$.