---
title: "Define multitape Turing machine"
subject: "Theory of Computation"
chapter: 4
key: "semester_3/theory_of_computation:tm-multitape-define"
source: https://www.bctengineer.com/q/semester_3/theory_of_computation/tm-multitape-define
site: BCT Engineering
---

# Define multitape Turing machine

Theory of Computation · Chapter 4: Turing Machine

- Asked in: 2072 Chaitra
- Video: [Multi Tape Turing Machines](https://www.youtube.com/watch?v=5qZ9zT01Lxc) — Andreas Schaefer
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_3/theory_of_computation/tm-multitape-define
- Whole chapter: https://www.bctengineer.com/md/semester_3/theory_of_computation/chapter-4

## Question

Define a multitape Turing machine.

## Short answer

A multitape TM has k≥2 tapes, each with its own head, controlled by a single finite control. Transition δ: Q×Γᵏ→Q×Γᵏ×{L,R,S}ᵏ reads current state and k symbols, writes new symbols, and moves heads independently. Input is on tape 1; other tapes blank. It is equivalent to a single-tape TM but simplifies design.

## Answer

A **multitape Turing machine** is a Turing machine with **k ≥ 2 tapes**, each with its own read/write head, and a single finite control.

#### Formal definition
M = (Q, Σ, Γ, δ, q0, ⊔, F), where
- Q is a finite set of states, q0 the start state, F ⊆ Q the final states,
- Σ is the input alphabet, Γ ⊇ Σ the tape alphabet, ⊔ ∈ Γ − Σ the blank,
- δ is the transition function

δ : Q × Γᵏ → Q × Γᵏ × {L, R, S}ᵏ

In one move, depending on the current state and the k symbols under the k heads, the machine
1. changes state,
2. writes a new symbol on each tape, and
3. moves each head independently left, right or stays.

The input is placed on tape 1; the other tapes start blank, with all heads at the left end.

```text
 finite control (state q)
     |      |      |
  ┌──v──────v──────v──┐
 T1│ # │ 1 │ 0 │ # │ ⊔ ...
 T2│ # │ ⊔ │ ⊔ ...
 T3│ ⊔ │ ⊔ │ ...
```

#### Equivalence with the single-tape TM
A multitape TM is no more powerful than a single-tape TM: every language accepted by a k-tape machine is accepted by a one-tape machine. The single tape stores all k tapes side by side, separated by a marker, with a mark for each head position, and each move is simulated by sweeping the tape. If the k-tape machine takes t(n) steps, the one-tape machine takes O(t(n)²) steps.

Multitape machines are used because they are easier to design (copying, adding, comparing) and to analyse for time complexity.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. What is a multitape Turing machine?
   A. A TM with k >= 2 tapes, each with its own head, and one finite control
   B. A TM with one tape and many heads sharing a position
   C. A TM with several finite controls
   D. A TM with a stack
   Answer: A. It has k tapes, each with an independent head, controlled by a single finite control. (Key point: Definition)

2. What is the form of its transition function?
   A. Q x Gamma -> Q x Gamma x {L,R,S}
   B. Q x Gamma^k -> Q x Gamma^k x {L,R,S}^k
   C. Q -> Q x Gamma
   D. Q x Sigma^k -> Q
   Answer: B. It reads k symbols, writes k symbols, and moves each head independently. (Key point: Transition function)

3. How does a multitape TM compare in power with a single-tape TM?
   A. It accepts more languages
   B. It accepts fewer languages
   C. It accepts the same languages
   D. It accepts only regular languages
   Answer: C. Any k-tape machine can be simulated by a one-tape machine, so the power is the same. (Key point: Power)

4. If a k-tape TM takes t(n) steps, how many steps does the one-tape simulation take?
   A. O(t(n))
   B. O(t(n)^2)
   C. O(2^t(n))
   D. O(log t(n))
   Answer: B. Each simulated move requires sweeping the tape, giving a quadratic slowdown. (Key point: Simulation cost)

## Related in Theory of Computation

- [Multitape TM as copying machine](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Atm-multitape-copy) — Theory of Computation, chapter 4
- [What is a Turing machine; its operation](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Atm-define-operation) — Theory of Computation, chapter 4
- [How a universal Turing machine works](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Auniversal-tm-example) — Theory of Computation, chapter 5

## Related in other subjects

- [AI, Turing test, CSP examples](https://www.bctengineer.com/question.md?key=semester_6%2Fartificial_intelligence%3Aturing-test-pass-csp-examples) — Artificial Intelligence, chapter 1