Difficulty: Intermediate | Prerequisites: Basic Turing Machine definition (states, tape, transitions, accept/reject), understanding of simulation arguments.
This topic sits at the heart of computability theory. The central question is whether modifying the physical setup of a Turing Machine (its tape, head position) changes what it can compute. It does not. Proving that different TM variants are equivalent in computational power is a core technique in EECS 376 and in theoretical computer science more broadly. You should already be comfortable with the formal definition of a standard TM before working through this material.
A Turing Machine with a doubly infinite tape (infinite in both directions) can compute exactly the same languages as a standard (singly infinite) TM. You prove equivalence by showing each can simulate the other. This simulation technique generalises to many TM variants and is a fundamental proof pattern in the course.
Standard Turing Machine (singly infinite tape)
A theoretical computing device with a finite set of states, a read/write head, and a tape that extends infinitely to the right. The tape starts with the input written at the left end, followed by blanks. The head begins at the leftmost cell.
Think of it as: the baseline model of computation, the one everything else gets compared to.
Doubly Infinite Tape Turing Machine
A TM variant whose tape extends infinitely in both directions (left and right). The tape is initially blank everywhere except for the input, and the head may start at any position on the input. The head never "falls off" the left end because there is no left end.
In simple terms, this means: the tape has no boundary on either side, so the machine can always move left or right without restriction.
TM Equivalence (simulation)
Two models of computation are equivalent if each can simulate the other. "M1 simulates M2" means M1 can replicate every computation M2 performs, accepting and rejecting the same inputs.
Think of it as: two machines speak different dialects but can translate perfectly between them, so they understand exactly the same set of sentences.
Decidability
A language L is decidable if there exists a TM that halts on every input and correctly accepts strings in L and rejects strings not in L.
In simple terms, this means: you can build an algorithm that always finishes and always gives the right yes/no answer.
To prove two TM models are equivalent, you show two directions: the standard TM can simulate the doubly infinite tape TM, and the doubly infinite tape TM can simulate the standard TM.
The idea is to encode the doubly infinite tape onto a singly infinite tape using a two-track technique.
Track encoding: Split the doubly infinite tape at the head's starting position. The right half (positions 0, 1, 2, ...) goes on the top track of the standard TM's tape. The left half (positions -1, -2, -3, ...) goes on the bottom track, reversed.
Head movement: When the doubly infinite TM moves right, the standard TM moves right on the top track. When the doubly infinite TM moves left past position 0, the standard TM switches to reading/writing the bottom track and moves right (which corresponds to moving further left on the original tape).
State bookkeeping: The standard TM uses its state to remember which track is currently active. This at most doubles the state set.
Key point: The standard TM's tape never runs out on the left because leftward movement on the original tape is encoded as rightward movement on the bottom track.
This direction is simpler.
Place the input at some position on the doubly infinite tape, with blanks everywhere else (matching the standard TM's initial configuration).
Position the head at the leftmost symbol of the input.
Run the standard TM's transition function directly. The doubly infinite tape TM simply never uses the cells to the left of the starting position, so the extra tape space is irrelevant.
The head-start position flexibility does not matter: you fix it at the leftmost input symbol.
Both machines recognise and decide exactly the same class of languages. Any language decidable (or recognisable) by one is decidable (or recognisable) by the other. The simulation preserves acceptance, rejection, and looping behaviour.
Given a doubly infinite tape TM M, the language L_RIGHT is defined as:
L_RIGHT = { (⟨M⟩, x) | M moves its head to the right at least once during its execution on input x }
The key insight is that a doubly infinite tape TM that never moves right is extremely limited. If the head only moves left (or stays put), it can only visit a bounded number of distinct configurations before it must either halt or repeat a configuration and loop.
Deciding L_RIGHT:
Simulate M on input x step by step.
Track the head position. If the head ever moves right, accept immediately.
If the head never moves right, it can only move left. Since it starts at some position on the input and only moves left, the number of tape cells it can visit is bounded by the number of cells to the left of the start position plus the tape alphabet and state set.
Count the total number of distinct configurations (state, head position, tape contents in the visited region). This number is finite and computable from ⟨M⟩ and x.
If the simulation runs for more steps than the number of distinct configurations without ever moving right, the machine must be in a loop. Reject.
Why this works:
The argument depends on the fact that a TM restricted to leftward movement on a doubly infinite tape has a bounded number of reachable configurations. Once you exceed that bound without a rightward move, you know a rightward move will never happen. This gives a concrete halting criterion, making the language decidable.
Configuration bound:
The number of configurations is at most |Q| x |Γ|^k, where Q is the state set, Γ is the tape alphabet, and k is the number of tape cells the head could possibly visit without moving right. Since the head only moves left from its start, k is finite and determined by the input length and start position.
Two-track encoding (Direction 1):
Original doubly infinite tape: ... | a_{-2} | a_{-1} | a_0 | a_1 | a_2 | ...
Standard TM tape (two tracks):
Top track: a_0, a_1, a_2, ...
Bottom track: a_{-1}, a_{-2}, a_{-3}, ...
The standard TM uses a special marker in cell 0 to know when the simulated head crosses the boundary between the two halves.
Configuration bound for L_RIGHT:
Maximum configurations without a rightward move = |Q| x |Γ|^k
Where Q = state set, Γ = tape alphabet, k = number of cells reachable by leftward-only movement from the start position.
TM equivalence proofs underpin the Church-Turing thesis: the idea that any reasonable model of computation (lambda calculus, register machines, modern CPUs) can simulate any other. This is why software written for one architecture can, in principle, run on another. The two-track simulation technique is conceptually similar to how virtual machines and emulators work, encoding one machine's memory layout within another's.
Students often think that a doubly infinite tape gives the TM "more power" because it has more space. It does not. The standard TM already has infinite tape to the right, which is sufficient to encode any additional space.
Students sometimes confuse equivalence of computational power with equivalence of efficiency. Two equivalent TM models recognise the same languages, but one simulation may take more steps than the other. Equivalence here is about what can be computed, not how fast.
A common error in the L_RIGHT proof is forgetting to bound the number of configurations. Without a finite bound, you cannot guarantee the simulation terminates, and the decider would not be a decider at all.
Some students assume L_RIGHT must be undecidable because it asks about TM behaviour. Not every question about TM behaviour is undecidable. L_RIGHT is decidable precisely because restricting the head to leftward movement creates a finite configuration space.
⚠️ The two-track simulation is a classic exam technique. Be prepared to sketch the encoding and explain how the standard TM handles crossing from the "right half" to the "left half" of the original tape.
⚠️ Expect a question asking you to prove a TM variant is equivalent to the standard model. The structure is always the same: simulate in both directions.
⚠️ L_RIGHT-style questions test whether you can identify when a TM behaviour question is decidable. The trick is always bounding the configuration space.
⚠️ Know the difference between "equivalent in power" and "equivalent in efficiency." Exam questions sometimes test whether you conflate the two.
True or False: A doubly infinite tape TM can recognise languages that a standard TM cannot.
Fill in the blank: To simulate a doubly infinite tape on a standard TM, you use a ____-track encoding.
True or False: L_RIGHT is undecidable because it asks about TM runtime behaviour.
Fill in the blank: If a TM only moves left and runs for more than |Q| x |Γ|^k steps, it must be in a ____.
True or False: Proving TM equivalence requires showing simulation in both directions.
Q: Describe how a standard TM simulates a doubly infinite tape TM. What encoding do you use?
A: Use a two-track encoding. Split the doubly infinite tape at the head's start position. The right half goes on the top track, the left half (reversed) goes on the bottom track. The standard TM uses its state to track which track is active and a boundary marker at cell 0. Leftward moves past the boundary become rightward moves on the bottom track.
Q: Why is the reverse direction (doubly infinite tape TM simulates standard TM) straightforward?
A: The doubly infinite tape TM simply places the input at a fixed position, starts the head at the leftmost symbol, and runs the standard TM's transitions directly. The extra leftward tape is never used, so it does not affect the computation.
Q: Is L_RIGHT decidable? Justify your answer.
A: Yes. Simulate M on x. If the head moves right, accept. If it never moves right, the head only moves left from its start position, giving a finite number of reachable configurations. If the simulation exceeds this bound without a rightward move, the TM is looping, so reject. The bound is computable, so the decider always halts.
Q: A student claims that because L_RIGHT involves simulating a TM, it must be undecidable (like the halting problem). What is wrong with this reasoning?
A: The halting problem is undecidable because there is no finite bound on how long a TM might run before halting. L_RIGHT avoids this because restricting the head to leftward-only movement creates a finite configuration space. Once you exceed the configuration bound, you know the answer. The key distinction is whether the simulation has a guaranteed termination criterion.
This connects to the Church-Turing thesis, which asserts that all reasonable models of computation are equivalent. You will see more TM variants (multi-tape, nondeterministic) later in the course, and the simulation technique here is the template for all of those proofs. The L_RIGHT decidability argument connects to the broader theme of Problem 4 in this homework: identifying which questions about TM behaviour are decidable by finding finite configuration bounds.
Related Terms / Search Tags
Turing Machine equivalence, doubly infinite tape, two-way infinite tape, bi-infinite tape, singly infinite tape, two-track simulation, multi-track TM, TM variant, computational equivalence, Church-Turing thesis, decidable language, configuration space, configuration bound, head movement, L_RIGHT, EECS 376, Foundations of Computer Science, University of Michigan