Difficulty: Intermediate | Prerequisites: Basic Turing Machine definition (states, alphabet, transition function, accept/reject), familiarity with formal proof structure.
Turing Machines are the standard model for reasoning about what computers can and cannot compute. A natural question is whether adding hardware (a second tape, for instance) makes a TM genuinely more powerful. This discussion proves it does not: a single-tape TM can simulate any multi-tape TM, so the two models recognise exactly the same languages. The discussion also shows that TMs confined to yes/no decisions can, by combining answers bit by bit, solve open-ended computational problems. Both results reinforce the central thesis of the course: different-looking models of computation are often equivalent in power.
A 2-tape Turing Machine looks more powerful than a 1-tape TM, but the two are provably equivalent: each can simulate the other. Separately, any open-ended computation whose answer is a binary string can be decomposed into a series of yes/no decision problems, one per bit, so decision-problem TMs are just as expressive as "function-computing" TMs.
Turing Machine (TM)
A 7-tuple (Q, Σ, Γ, q₀, q_accept, q_reject, δ) with a single infinite tape and a read/write head that moves left or right according to δ. Think of it as the simplest possible programmable computer: one strip of memory, one instruction at a time.
2-tape Turing Machine
A TM with two independent infinite tapes, each with its own head. The transition function reads both tapes and writes to both tapes in a single step. In simple terms, this means the machine can look at two pieces of data simultaneously and update them independently.
Transition function (δ)
The rule that tells the machine what to do next, given its current state and the symbol(s) under its head(s). For a 1-tape TM: δ : (Q \ F) × Γ → Q × Γ × {L, R}. For a 2-tape TM: δ : (Q \ F) × Γ × Γ → Q × Γ × Γ × {L, R} × {L, R}.
Simulation
Designing one model of computation so that it exactly replicates the behaviour of another, step by step. If model A can simulate model B, then anything B computes, A can compute too.
Decision problem
A computational question with a yes/no answer. A TM "decides" a language L if it accepts every string in L and rejects every string not in L. Think of it as a true/false test on an input.
Language (in TM theory)
A set of strings. A TM is said to decide language L when it correctly accepts or rejects every possible input with respect to membership in L.
Binary string encoding
The principle that any piece of information (a number, a program, an image) can be represented as a finite string of 0s and 1s. This is what lets us convert open-ended questions into sequences of yes/no questions, one per bit.
A 2-tape TM is still a 7-tuple (Q, Σ, Γ, q₀, q_accept, q_reject, δ). The only structural difference is the transition function, which now reads from two tape cells and specifies writes and head moves for both tapes.
Direction 1: A 2-tape TM can do anything a 1-tape TM can.
This is the easy direction. A 2-tape TM simply ignores its second tape and operates exactly as a 1-tape TM would. No clever construction needed.
Direction 2: A 1-tape TM can do anything a 2-tape TM can.
This is the harder and more interesting direction. We construct a 1-tape TM called T that simulates an arbitrary 2-tape TM called M.
Tape layout: T stores both of M's tapes on its single tape, separated by # delimiters. The format is: # [contents of tape 1] # [contents of tape 2] #
Head tracking: T uses a special dot marker (•) above the symbol where each simulated head sits. This lets T remember where M's two heads are, even though T has only one physical head.
Step-by-step operation:
T formats its tape as # •w₁...wₙ # •⊥ # (input on tape 1, blank on tape 2, both heads at the start)
T scans from the first # to the third # to find both dot markers, reading the symbols under them
T makes a second pass, applying M's transition function δ_M: it writes the new symbols, moves the dot markers left or right accordingly
If a dot marker would overwrite a # delimiter, T shifts all cells one space to the right and writes a blank where the # was, preserving the boundary between the two simulated tapes
Correctness: Because M was arbitrary, this construction works for every 2-tape TM. The 1-tape TM T perfectly replicates M's computation, so the two models are equivalent in power.
Turing Machines output only ACCEPT or REJECT. Does that mean they can only answer yes/no questions? No. Any piece of information can be encoded as a binary string, so any question whose answer is a binary string can be broken into a sequence of yes/no questions, one per bit.
Consider a function f : {0,1}ⁿ → {0,1}ⁿ. To compute f(x), define n separate decision problems:
M₁ decides L₁ = { x ∈ {0,1}ⁿ | the 1st bit of f(x) = 1 }
M₂ decides L₂ = { x ∈ {0,1}ⁿ | the 2nd bit of f(x) = 1 }
... and so on through Mₙ
Run all n machines on input x. Concatenate their answers (ACCEPT = 1, REJECT = 0) to reconstruct f(x).
Let n = 3. Suppose M₁(x) = ACCEPT, M₂(x) = ACCEPT, M₃(x) = REJECT. Then f(x) = 110.
This technique proves that the decision-problem model of Turing Machines is not a limitation. Anything you could compute with a "function-outputting" machine, you can also compute with a collection of decision-problem machines. The expressive power is the same.
1-tape TM:
δ : (Q \ F) × Γ → Q × Γ × {L, R}
Read: given a non-terminal state and one tape symbol, produce a new state, a symbol to write, and a direction to move the head.
2-tape TM:
δ : (Q \ F) × Γ × Γ → Q × Γ × Γ × {L, R} × {L, R}
Read: given a non-terminal state and the symbols under both heads, produce a new state, a symbol to write on each tape, and a direction for each head.
The 1-tape simulator T arranges its tape as:
# [•w₁ ... wₙ] # [•⊥] #
The # symbols are delimiters. The • markers track where each of M's two heads sit. When a head reaches a #, the simulator shifts cells right and inserts a blank to extend that simulated tape.
The equivalence result is why computer architects can add multiple memory banks, caches, or registers without changing what is theoretically computable. Extra hardware changes speed, not capability. The decision-to-open-ended reduction is the conceptual ancestor of how real systems encode complex outputs (images, audio, video) as sequences of bits, with each bit determined independently.
"A 2-tape TM is more powerful than a 1-tape TM." It is faster for some problems (fewer steps), but it computes exactly the same class of languages. Power here means what you can compute, not how quickly.
"The simulation proof means the 1-tape TM runs in the same number of steps." It does not. The single-tape simulation is slower because it must scan back and forth to find the dot markers. The proof is about computability (can it be done at all?), not complexity (how many steps does it take?).
"Decision-problem TMs can only solve yes/no questions." They can solve any computable problem, because any answer can be encoded in binary and each bit is a separate yes/no question.
"You need one single TM that outputs all the bits at once." The construction uses n separate machines, one per bit. The key insight is that combining their individual accept/reject outputs reconstructs the full answer.
⚠️ Equivalence proofs require both directions. Always show (i) the new model can simulate the standard model, and (ii) the standard model can simulate the new model.
⚠️ The tape-layout construction (# delimiters, • head markers, shift-right on overflow) is a common exam question. Be ready to describe or diagram each step.
⚠️ The bit-by-bit reduction from open-ended to decision problems can appear as: "Show that if every decision problem is decidable, then every function from {0,1}ⁿ to {0,1}ⁿ is computable."
⚠️ Know the difference between computability and complexity. The 1-tape simulation is slower (more steps per simulated step), but it computes the same thing.
True or False: A 2-tape TM can decide languages that a 1-tape TM cannot.
Fill in the blank: To simulate two tapes on one tape, we separate the simulated tapes using ______ symbols and track each head with a ______ marker.
True or False: The 1-tape simulation of a 2-tape TM always runs in the same number of steps as the 2-tape machine.
Fill in the blank: To compute a function f : {0,1}³ → {0,1}³ using decision-problem TMs, we need ______ separate Turing Machines.
True or False: If M₁(x) = REJECT and M₂(x) = ACCEPT and M₃(x) = ACCEPT, then f(x) = 011.
Answers: 1. False. 2. # (hash); • (dot). 3. False (it is slower). 4. Three. 5. True.
Q: Describe how a 1-tape TM T simulates a 2-tape TM M. What is the tape format, and how does T handle the case where a simulated head reaches the end of its tape region?
A: T stores both tapes on a single tape separated by # delimiters, with • markers above the current head positions. Each step, T scans to find both markers, reads the symbols under them, applies M's transition function, then updates the symbols and moves the markers. If a marker would overwrite a # delimiter, T shifts all cells one position to the right and writes a blank (⊥) where the # was, so the tape regions stay properly separated.
Q: Why is it trivial to show that a 2-tape TM can simulate a 1-tape TM?
A: A 2-tape TM simply ignores its second tape. It uses only the first tape and operates exactly as the 1-tape TM would. No construction is needed.
Q: Explain how a function f : {0,1}ⁿ → {0,1}ⁿ can be computed using only Turing Machines that solve decision problems.
A: Define n Turing Machines M₁ through Mₙ, where Mᵢ decides the language Lᵢ = { x ∈ {0,1}ⁿ | the i-th bit of f(x) = 1 }. Run each machine on input x. If Mᵢ accepts, the i-th bit of the answer is 1; if it rejects, the i-th bit is 0. Concatenating the results gives f(x).
Q: Does the equivalence of 1-tape and 2-tape TMs imply they are equally efficient? Why or why not?
A: No. Equivalence here is about computability, not efficiency. The 1-tape simulation requires extra scanning passes back and forth across the tape on every step, so it uses more time steps than the 2-tape machine. The two compute the same languages, but the 2-tape machine may be faster for a given problem.
This material connects directly to the Church-Turing thesis, which asserts that every "effectively computable" function can be computed by a Turing Machine. The equivalence proofs here are concrete evidence for that thesis: adding tapes does not escape the TM model. It also sets the stage for undecidability results later in EECS 376, because once you accept that all these models are equivalent, proving something is undecidable on one model proves it for all of them. The decision-to-open-ended reduction reappears in complexity theory, where function problems are often reduced to decision problems for analysis.
Turing Machine equivalence, multi-tape TM, 2-tape Turing Machine, k-tape TM, tape simulation, TM simulation proof, transition function delta, decision problem, language decidability, binary encoding, open-ended computation, function computation with TMs, EECS 376, Foundations of Computer Science, Church-Turing thesis, computability theory