---
title: "Head shifting and symbol writing TM"
subject: "Theory of Computation"
chapter: 4
key: "semester_3/theory_of_computation:tm-head-symbol-define"
source: https://www.bctengineer.com/q/semester_3/theory_of_computation/tm-head-symbol-define
site: BCT Engineering
---

# Head shifting and symbol writing TM

Theory of Computation · Chapter 4: Turing Machine

- Asked in: 2071 Chaitra
- Video: [Turing Machine (Example 1)](https://www.youtube.com/watch?v=D9eF_B8URnw) — 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-head-symbol-define
- Whole chapter: https://www.bctengineer.com/md/semester_3/theory_of_computation/chapter-4

## Question

Define head shifting and symbol writing Turing machines.

## Short answer

Symbol-writing machine a writes a in the current cell and halts; head stays. Head-shifting machines R and L move the head one cell right or left and halt. These elementary TMs are building blocks: e.g., R⊔ moves right until blank. Combine with conditional branches to construct any TM.

## Answer

These are the two kinds of **elementary Turing machines** (Lewis and Papadimitriou), from which larger machines are built by composition.

#### Symbol-writing machines
For each symbol a ∈ Γ (including the blank ⊔) there is a machine, also written **a**, that **writes a** in the cell under the head and halts. The head does not move.

Formally, it has states {q0, h}, and δ(q0, x) = (h, a, S) for every x ∈ Γ. Example: the machine "1" replaces whatever symbol is scanned by 1. The machine "⊔" erases the cell.

#### Head-moving (head-shifting) machines
Two machines change only the head position and leave the tape contents unchanged:
- **R** moves the head one cell to the **right** and halts: δ(q0, x) = (h, x, R) for all x.
- **L** moves the head one cell to the **left** and halts: δ(q0, x) = (h, x, L) for all x.

```text
  Before:  ... a [b] c ...
  R   :    ... a  b [c] ...
  L   :    ... [a] b  c ...
  "x" :    ... a [x] c ...   (b overwritten by x)
```

#### Use
These machines are combined with arrows (conditions on the scanned symbol) to give larger machines. For example, **R⊔** means "move right until a blank is found" and **L⊔** means "move left until a blank is found". Any TM can be described as such a combination, which is why they are called the basic building blocks of Turing machines.

## Check yourself

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

1. What does the symbol-writing machine 'a' do?
   A. Moves right and writes a
   B. Writes a in the scanned cell and halts without moving
   C. Erases the tape
   D. Moves left until it finds a
   Answer: B. It has delta(q0, x) = (h, a, S) for every x, overwriting the current cell. (Key point: Symbol-writing machine)

2. What do the machines R and L do?
   A. Change the head position by one cell and leave the tape unchanged
   B. Write R or L on the tape
   C. Reverse the tape
   D. Move until a blank
   Answer: A. R and L only shift the head one cell and halt, rewriting the same symbol. (Key point: Head-moving machines)

3. How are larger machines built from these elementary machines?
   A. By composing them with arrows conditioned on the scanned symbol
   B. By adding more tapes
   C. By removing states
   D. By using a stack
   Answer: A. They are combined with arrows (conditions on the scanned symbol), e.g. R-blank means move right until a blank. (Key point: Composition)

## Related in Theory of Computation

- [TM that doubles a binary number](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Atm-doubles-binary) — Theory of Computation, chapter 4
- [TM accepting wwᴿ; process 101101](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Atm-accept-wwr-101101) — Theory of Computation, chapter 4
- [Compare TM with FA and PDA](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Atm-compare-fa-pda) — Theory of Computation, chapter 4
- [TM configuration; TM for palindromes](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Atm-config-palindrome) — Theory of Computation, chapter 4
- [TM for aⁿcbⁿ (single tape, deterministic)](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Atm-an-c-bn) — Theory of Computation, chapter 4
- [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

- [Design of Pelton wheel for given power and head](https://www.bctengineer.com/question.md?key=semester_5%2Ffluid_machines%3Apelton-wheel-design-numerical) — Fluid Machines, chapter 3
- [Centrifugal pump head, discharge and power](https://www.bctengineer.com/question.md?key=semester_5%2Ffluid_machines%3Acentrifugal-pump-head-power-numerical) — Fluid Machines, chapter 4