---
title: "What is a Turing machine; its operation"
subject: "Theory of Computation"
chapter: 4
key: "semester_3/theory_of_computation:tm-define-operation"
source: https://www.bctengineer.com/q/semester_3/theory_of_computation/tm-define-operation
site: BCT Engineering
---

# What is a Turing machine; its operation

Theory of Computation · Chapter 4: Turing Machine

- Asked in: 2072 Kartik
- Video: [Turing Machine - Introduction (Part 1)](https://www.youtube.com/watch?v=PvLaPKPzq2I) — Neso Academy
- 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-define-operation
- Whole chapter: https://www.bctengineer.com/md/semester_3/theory_of_computation/chapter-4

## Question

What is a Turing machine? Describe its operation.

## Short answer

A Turing machine is a mathematical model of computation with an infinite tape, a read/write head, and a finite control. It reads a symbol, writes a new symbol, moves the head, and changes state per a transition function. It accepts if it halts in a final state.

## Answer

#### Definition
A **Turing machine** (TM) is a mathematical model of a general-purpose computer, proposed by Alan Turing (1936). It consists of a finite control, an **infinite tape** divided into cells, and a read/write head.

Formally, M = (Q, Σ, Γ, δ, q0, ⊔, F), where
- Q is a finite set of states, q0 ∈ Q the start state, F ⊆ Q the final (accepting) states,
- Σ is the input alphabet (not containing the blank), Γ ⊇ Σ ∪ {⊔} the tape alphabet, ⊔ the blank,
- δ : Q × Γ → Q × Γ × {L, R, S} is the transition function (partial).

```text
         ┌───────────────┐
         │ finite control│  state q
         └───────┬───────┘
                 │ head
     ... ⊔ │ a │ b │ a │ ⊔ │ ⊔ ...   infinite tape
```

#### Operation
1. The input string w is written on the tape, the rest of the tape is blank, the head is on the leftmost symbol, and the state is q0.
2. In each step, the machine reads the symbol under the head. If δ(q, a) = (p, b, D), it **writes b** over a, **moves** the head one cell in direction D (L, R or stay), and **changes state** to p.
3. This repeats. If no move is defined, the machine **halts**.
4. w is **accepted** if M halts in a state of F. It is rejected if M halts in a non-final state; on some inputs M may also run forever (loop).

The language accepted is L(M) = { w : q0 w ⊢* u p v with p ∈ F }.

#### Example
For δ(q0, 1) = (q0, 1, R) and δ(q0, ⊔) = (qa, ⊔, S): the machine scans a string of 1's from left to right and accepts at the first blank, so it accepts 1*.

Turing machines accept exactly the recursively enumerable languages and compute the partial recursive functions. By the Church–Turing thesis, they capture everything an algorithm can compute.

## Check yourself

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

1. What is the transition function of a single-tape TM?
   A. Q x Gamma -> Q x Gamma x {L,R,S}
   B. Q -> Gamma
   C. Q x Sigma -> Q
   D. Gamma -> Gamma
   Answer: A. It reads a symbol, writes a symbol, moves, and changes state. (Key point: Formal definition)

2. If delta(q, a) = (p, b, D), what does the machine do?
   A. Writes b over a, moves in direction D and enters state p
   B. Writes a and stays
   C. Moves then reads b
   D. Halts
   Answer: A. A move writes, moves the head and changes state. (Key point: One step)

3. When does a TM halt?
   A. Never
   B. When no move is defined
   C. After one step
   D. When it reads a blank
   Answer: B. If no transition is defined for the current state and symbol, the machine halts. (Key point: Halting)

4. When is w accepted?
   A. When M halts in a state in F
   B. When M halts in any state
   C. When M loops
   D. When the tape is empty
   Answer: A. Halting in a non-final state is rejection; looping is also not acceptance. (Key point: Acceptance)

## Related in Theory of Computation

- [Define multitape Turing machine](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Atm-multitape-define) — 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
- [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

## 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
- [Replace existing machine now; AEC and ESL](https://www.bctengineer.com/question.md?key=semester_6%2Fengineering_economics%3Areplace-existing-machine-cash-flow-aec) — Engineering Economics, chapter 5
- [Transformer operation; flux constant at any load](https://www.bctengineer.com/question.md?key=semester_4%2Felectrical_machine%3Atransformer-load-noload-flux-constant) — Electrical Machine, chapter 2, asked 3×