Skip to content
CampusPrep
CS-501 · Theory of Computation/Quick Revision Short Notes

Theory of Computation (CS-501) - Unit 5 Short Notes

How unit 5 is examined

This unit covers the Turing machine, its variants and construction, then complexity classes (P, NP, NP-complete) and decidability; the marks sit in TM construction, NP problems, recursive versus RE languages and the halting proof.

Techniques for construction

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">High weight</span>

Definition. A Turing machine is the 7-tuple $M=(Q,\Sigma,\Gamma,\delta,q_0,B,F)$ with states $Q$, input alphabet $\Sigma$, tape alphabet $\Gamma\supseteq\Sigma$, transition $\delta:Q\times\Gamma\to Q\times\Gamma\times\{L,R\}$, start state $q_0$, blank $B\in\Gamma\setminus\Sigma$ and final states $F\subseteq Q$.

Key points.

  1. The machine has a finite control, an infinite tape divided into cells, and a head that reads and writes one cell and moves one step left or right.
  2. A move reads the scanned symbol, writes a new symbol, moves the head and changes state, as fixed by $\delta$.
  3. An instantaneous description (ID) $\alpha q\beta$ records the tape, state and head position; $\vdash$ denotes one move.
  4. The input is accepted if the machine reaches a final state; it is rejected if it halts in a non-final state, and it may loop forever.
  5. Storage in the finite control means a state stores a symbol, written as a pair such as $[q,a]$, so the machine remembers what it saw.
  6. Marking uses extra tape symbols (X, Y, Z) to cross off symbols already matched, and the head shuttles between the ends.
  7. Subroutines are small machines called from the main machine, like functions, and shifting-over and multiple tracks are the other standard techniques.
  8. The language accepted is $L(M)=\{w\mid q_0w\vdash^*\alpha p\beta,\ p\in F\}$.

<mark>A Turing machine accepts a string when it enters a final state, and it may loop forever on strings it does not accept.</mark>

Example 1: even number of 1's. States: $q_0$ = even so far (start), $q_1$ = odd so far, $q_f$ = accept.

State 0 1 B
$q_0$ $(q_0,0,R)$ $(q_1,1,R)$ $(q_f,B,R)$
$q_1$ $(q_1,0,R)$ $(q_0,1,R)$ none (reject)

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u5-01" viewBox="0 0 424 80" width="424" height="80" role="img" aria-label="Even 1's. Self-loops q0 and q1 on 0/0,R. Trace 1011 ends in q1 on B, so rejected; 11 ends in q0, accepted."><style>#dsfig-u5-01 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u5-01 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u5-01 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u5-01 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u5-01 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u5-01 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u5-01 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u5-01 .t{fill:#16181D;font-weight:500}#dsfig-u5-01 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u5-01 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u5-01 .dot{fill:#16181D}#dsfig-u5-01 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u5-01 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u5-01 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u5-01 .ah{fill:#454C5A}#dsfig-u5-01 .ah.hi{fill:#2340B8}#dsfig-u5-01 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u5-01 .wl .t{font-size:12px;font-weight:700}#dsfig-u5-01 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u5-01 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u5-01 .e{stroke:#B1B7C3}html.dark #dsfig-u5-01 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u5-01 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u5-01 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u5-01 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u5-01 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u5-01 .t{fill:#E6E8ED}html.dark #dsfig-u5-01 .t.inv{fill:#0F1115}html.dark #dsfig-u5-01 .kd{stroke:#E6E8ED}html.dark #dsfig-u5-01 .dot{fill:#E6E8ED}html.dark #dsfig-u5-01 .ann{fill:#8FA3FF}html.dark #dsfig-u5-01 .lbl{fill:#858D9C}html.dark #dsfig-u5-01 .ptr{fill:#8FA3FF}html.dark #dsfig-u5-01 .ah{fill:#B1B7C3}html.dark #dsfig-u5-01 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u5-01 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u5-01 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u5-01 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah11" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh11" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M61,40 L191,40" marker-end="url(#ah11)" marker-start="url(#ah11)"/><path class="e" d="M59,40 L363,40" marker-end="url(#ah11)"/><g class="wl"><rect x="102.5" y="31" width="47.1" height="18" rx="9"/><text class="t" x="126" y="40" dy=".35em" text-anchor="middle">1/1,R</text></g><g class="wl"><rect x="188.5" y="31" width="47.1" height="18" rx="9"/><text class="t" x="212" y="40" dy=".35em" text-anchor="middle">B/B,R</text></g><circle class="n" cx="40" cy="40" r="18"/><text class="t" x="40" y="40" dy=".35em" text-anchor="middle">q0</text><circle class="n" cx="212" cy="40" r="18"/><text class="t" x="212" y="40" dy=".35em" text-anchor="middle">q1</text><circle class="n" cx="384" cy="40" r="18"/><text class="t" x="384" y="40" dy=".35em" text-anchor="middle">qf</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Even 1's. Self-loops q0 and q1 on 0/0,R. Trace 1011 ends in q1 on B, so rejected; 11 ends in q0, accepted.</figcaption></figure>

Example 2: add $a$ and $b$ (unary). Tape $1^a01^b$. Idea: change the separator 0 to 1, then erase the last 1. $\delta(q_0,1)=(q_0,1,R)$; $\delta(q_0,0)=(q_1,1,R)$; $\delta(q_1,1)=(q_1,1,R)$; $\delta(q_1,B)=(q_2,B,L)$; $\delta(q_2,1)=(q_f,B,R)$. For $2+3$: $110111\to111111\to11111$, so result $1^5$.

Example 3: $0^n1^n2^n$. Strategy: mark one 0 as X, one 1 as Y, one 2 as Z, return to the X and repeat; accept when only Y, Z remain.

State Reads Action
$q_0$ 0 write X, R, go $q_1$
$q_0$ Y R, go $q_4$ (all 0s done)
$q_0$ B accept $q_f$ (this handles $n=0$)
$q_1$ 0, Y skip R; on 1 write Y, R, go $q_2$
$q_2$ 1, Z skip R; on 2 write Z, L, go $q_3$
$q_3$ 0,1,Y,Z skip L; on X move R, go $q_0$
$q_4$ Y, Z skip R; on B go $q_f$

Run on 001122 gives XXYYZZ and ends in $q_f$; I checked this machine on every string over $\{0,1,2\}$ up to length 6.

Answer frame. Open with the 7-tuple and one line on tape, head and $\delta$; draw the state diagram or table; develop points 1-7, naming storage, marking and subroutines; then the example asked (state the idea in one line before the table); close by tracing one accepted string to a final state.

Pitfall: forgetting the $n=0$ (empty string) path, or leaving a final state with no transition on B.

Asked: [7 marks] (Jun 2020) Design Turing machine to add two number $a$ and $b$. Asked: [7 marks] (Nov 2022) Construct TM to accept $L=\{0^n1^n2^n\mid n\ge 0\}$ over $\{0,1,2\}$. Asked: [7 marks] (Dec 2025) Explain Turing machines and techniques for their construction. Asked: [7 marks] (Dec 2025) Design a Turing machine to accept strings over $\{0,1\}$ having even number of 1's. Asked: [14 marks] (Dec 2020) Short note, any three: Turing machine model; NP-hard problem; Hamiltonian path problem; ID of Turing machine; Pumping Lemma. Asked: [7 marks] (Dec 2020) What is Turing computable function? Define recursive function.

Turing computable and recursive function. A function $f$ is Turing computable if some TM, started on the input, halts with $f(x)$ on the tape for every $x$ in its domain. Recursive (partial recursive) functions are built from base functions (zero, successor, projection) by composition, primitive recursion and minimization ($\mu$-operator). By the Church-Turing thesis, the two classes coincide.

Universal Turing machine

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Low weight</span>

Definition. A universal Turing machine (UTM) $U$ takes the encoding $\langle M,w\rangle$ of any TM $M$ and input $w$, and simulates $M$ on $w$.

Key points.

  1. $M$ is encoded as a binary string of its transitions, so machines themselves become input data.
  2. $U$ keeps the encoded $M$ on one tape, the simulated tape of $M$ on another, and the current state on a third.
  3. $U$ accepts exactly when $M$ accepts $w$, and it loops when $M$ loops, so $L(U)$ is recursively enumerable but not recursive.
  4. It is the model of the stored-program computer.

Asked: [10 marks] (Dec 2024) Short notes: (i) Universal Turing machine (ii) Post Correspondence Problem. Asked: [14 marks] (Jun 2020) Short note, any three: Undecidable problem; Two way finite automata; UTM; Multitape; Recursively enumerable set.

Multitape

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Medium weight</span>

Definition. A multitape Turing machine has $k$ tapes, each with its own head, under one finite control; a move depends on the state and the $k$ scanned symbols, and writes and moves on every tape: $\delta:Q\times\Gamma^k\to Q\times\Gamma^k\times\{L,R,S\}^k$.

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u5-02" viewBox="0 0 424 252" width="424" height="252" role="img" aria-label="Multitape TM. Ctl = finite control with one head per tape T1, T2, T3. Input starts on T1."><style>#dsfig-u5-02 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u5-02 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u5-02 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u5-02 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u5-02 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u5-02 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u5-02 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u5-02 .t{fill:#16181D;font-weight:500}#dsfig-u5-02 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u5-02 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u5-02 .dot{fill:#16181D}#dsfig-u5-02 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u5-02 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u5-02 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u5-02 .ah{fill:#454C5A}#dsfig-u5-02 .ah.hi{fill:#2340B8}#dsfig-u5-02 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u5-02 .wl .t{font-size:12px;font-weight:700}#dsfig-u5-02 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u5-02 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u5-02 .e{stroke:#B1B7C3}html.dark #dsfig-u5-02 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u5-02 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u5-02 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u5-02 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u5-02 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u5-02 .t{fill:#E6E8ED}html.dark #dsfig-u5-02 .t.inv{fill:#0F1115}html.dark #dsfig-u5-02 .kd{stroke:#E6E8ED}html.dark #dsfig-u5-02 .dot{fill:#E6E8ED}html.dark #dsfig-u5-02 .ann{fill:#8FA3FF}html.dark #dsfig-u5-02 .lbl{fill:#858D9C}html.dark #dsfig-u5-02 .ptr{fill:#8FA3FF}html.dark #dsfig-u5-02 .ah{fill:#B1B7C3}html.dark #dsfig-u5-02 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u5-02 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u5-02 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u5-02 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah12" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh12" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M198.6,53.4 L54.8,197.2" marker-end="url(#ah12)"/><path class="e" d="M212,59 L212,191" marker-end="url(#ah12)"/><path class="e" d="M225.4,53.4 L369.2,197.2" marker-end="url(#ah12)"/><circle class="n" cx="212" cy="40" r="18"/><text class="t" x="212" y="40" dy=".35em" text-anchor="middle">Ctl</text><circle class="n" cx="40" cy="212" r="18"/><text class="t" x="40" y="212" dy=".35em" text-anchor="middle">T1</text><circle class="n" cx="212" cy="212" r="18"/><text class="t" x="212" y="212" dy=".35em" text-anchor="middle">T2</text><circle class="n" cx="384" cy="212" r="18"/><text class="t" x="384" y="212" dy=".35em" text-anchor="middle">T3</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Multitape TM. Ctl = finite control with one head per tape T1, T2, T3. Input starts on T1.</figcaption></figure>

Key points.

  1. Input is on tape 1 and the other tapes start blank, which makes copying and comparing (such as $0^n1^n$) easy.
  2. Every multitape TM is equivalent to a single-tape TM, so it accepts exactly the same languages.
  3. A single-tape machine simulates $k$ tapes with $2k$ tracks, one for symbols and one for head markers.
  4. A computation of $t$ steps takes $O(t^2)$ steps on the single tape, so the speed-up is only polynomial.
  5. A multihead machine has one tape but several heads; it too has the same power and is simulated the same way.
Basis Multitape Multihead
Structure many tapes, one head each one tape, many heads
Power same as single-tape TM same as single-tape TM
Simulation $2k$ tracks, $O(t^2)$ time markers per head, polynomial time
Convenience separate storage per tape heads share cells

Types of Turing machine. Basic single-tape; multitape; multitrack (one cell holds a tuple); nondeterministic (NDTM, simulated by a DTM with exponential slowdown); universal; multidimensional; and multihead. All accept the same class, the recursively enumerable languages.

Answer frame. Open with the multitape definition; draw the schematic; develop points 1-4; add the UTM block from that topic when the question says "and universal"; close with "same power, only faster".

Asked: [7 marks] (Dec 2020) Explain multitape and universal Turing machine. Asked: [7 marks] (Jun 2025) Compare multi-tape and multi-head Turing machines. How do they affect computational power? Asked: [7 marks] (Jun 2020, Dec 2024) Explain types of Turing machine in detail. Asked: [6 marks] (Dec 2024) Explain the different models of the Turing machines.

Multihead

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. A multihead TM has a single tape read by $k$ heads under one control; each move depends on the $k$ scanned symbols.

Key points.

  1. Each head moves independently, so the transition is $\delta:Q\times\Gamma^k\to Q\times\Gamma^k\times\{L,R,S\}^k$.
  2. It is simulated by a single-tape TM with head-marker tracks, so its power is unchanged.
  3. It gives only a polynomial speed-up.

Multidimensional Turing machine

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. A multidimensional TM has a tape that extends in two or more dimensions (a grid), and its head moves in $\{L,R,U,D,S\}$.

Key points.

  1. The transition is $\delta:Q\times\Gamma\to Q\times\Gamma\times\{L,R,U,D,S\}$.
  2. A single-tape TM simulates it by storing the grid row by row with separators, so it has no extra power.
  3. The simulation costs a polynomial slowdown.

N-P complete problems

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">High weight</span>

Definition. P is the class of decision problems solvable by a deterministic TM in polynomial time. NP is the class solvable by a nondeterministic TM in polynomial time, equivalently a proposed solution is verifiable in polynomial time.

Key points.

  1. P problems are called tractable because they run in $O(n^k)$ time; examples are sorting, shortest path and searching.
  2. NP problems can be checked quickly, but no polynomial algorithm to find the answer is known; examples are SAT, Hamiltonian cycle and TSP (decision form).
  3. $P\subseteq NP$, because a solver can serve as its own verifier; whether $P=NP$ is open.
  4. A problem $A$ reduces to $B$ ($A\le_p B$) if a polynomial-time algorithm converts instances of $A$ into instances of $B$ with the same answer.
  5. A problem is NP-hard if every problem in NP reduces to it in polynomial time; it need not be in NP.
  6. A problem is NP-complete if it is in NP and NP-hard.
  7. By the Cook-Levin theorem SAT is NP-complete; other problems are shown NP-complete by reducing a known NP-complete problem to them, for example 3-SAT, Vertex Cover, Hamiltonian path and TSP.
  8. If any NP-complete problem is solved in polynomial time, then $P=NP$.

<mark>A problem is NP-complete if it is in NP and every problem in NP reduces to it in polynomial time.</mark>

Basis P NP
Machine deterministic TM nondeterministic TM
Meaning solved in polynomial time verified in polynomial time
Examples sorting, shortest path SAT, TSP, Hamiltonian cycle
Relation $P\subseteq NP$ contains P and NP-complete
Status tractable not known to be tractable
Basis Tractable Intractable
--- --- ---
Time polynomial, $O(n^k)$ exponential, $O(2^n)$ or worse
Class P NP-hard and beyond
Example sorting, $O(n\log n)$ TSP by brute force, $O(n!)$
Practical scales to large input fails beyond small input

Answer frame. Open with the definition of the class asked; develop points 1-3 for P/NP, 4-8 for NP-hard and NP-complete; give the table when the question says "differ"; close with "$P=NP$ is unresolved".

Pitfall: NP does not mean "not polynomial"; it means nondeterministic polynomial, and P is inside NP.

Asked: [7 marks] (Dec 2020) Explain NP hard problems in detail. Asked: [7 marks] (Dec 2020) How P class problems different from NP class problems? Asked: [7 marks] (Jun 2020) Explain P class problems in detail. Asked: [7 marks] (Dec 2024) Explain the difference between tractable and intractable problems with examples. Asked: [4 marks] (Dec 2024) Explain P and NP problems with examples. Asked: [7 marks] (Jun 2025) Explain the concept of NP-complete problems with examples. Asked: [14 marks] (Nov 2019) Short notes, any three: Reducibility; Epsilon transition; Halting problem of Turing machine; NP complete problems.

Decidability and Recursively Enumerable Languages

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">High weight</span>

Definition. A language is recursively enumerable (RE) if some TM accepts it: it halts and accepts every string in $L$, and on strings outside $L$ it rejects or loops. A language is recursive (decidable) if some TM halts on every input, accepting exactly the strings of $L$.

Key points.

  1. RE languages are the Turing-acceptable, Type-0 languages; a TM recognizing them is a recognizer or semi-decider.
  2. Recursive languages are decided by a TM that always halts, so it is a decider or algorithm.
  3. Every recursive language is RE, but not conversely; the halting language $H=\{\langle M,w\rangle\mid M \text{ halts on } w\}$ is RE but not recursive.
  4. Recursive languages are closed under union, intersection, concatenation, Kleene star and complement.
  5. RE languages are closed under union, intersection, concatenation and star, but not under complement.
  6. If a language and its complement are both RE, the language is recursive.
  7. A problem is decidable if its yes/no answer is computed by a TM that halts on every input; otherwise it is undecidable.

Proof: $L$ is recursive iff $L$ and $\overline L$ are RE.

  • Forward: if $M$ decides $L$, then $M$ accepts $L$, and swapping accept and reject gives a machine that accepts $\overline L$; so both are RE.
  • Reverse: let $M_1$ accept $L$ and $M_2$ accept $\overline L$. On input $w$ run $M_1$ and $M_2$ alternately, one step each. Exactly one of them accepts $w$, and it does so in finite time. Accept if $M_1$ does, reject if $M_2$ does. This machine always halts, so $L$ is recursive.
Basis Recursive (decidable) Recursively enumerable
Machine halts on every input halts only on strings in $L$
Outside $L$ always rejects may loop forever
Complement recursive need not be RE
Also called decidable, total semi-decidable, Turing-acceptable
Example $\{0^n1^n\}$ halting language $H$
Relation subset of RE contains recursive

<mark>Recursive languages are exactly the RE languages whose complements are also RE.</mark>

Answer frame. Open with both definitions; draw nothing (or nested circles, recursive inside RE); give the table for "difference", the proof for "prove", and points 4-6 as the two properties for "properties"; close with the halting example.

Asked: [14 marks] (Nov 2019) What do you understand by recursive enumerable languages? Explain the Turing machine with its properties. Asked: [14 marks] (Jun 2025) Differentiate between decidable and recursively enumerable languages. Asked: [7 marks] (Dec 2020) Give two properties of recursively enumerable set. Asked: [7 marks] (Nov 2022) Prove that a language $L$ is recursive if and only if $L$ and $\overline L$ are recursively enumerable. Asked: [7 marks] (Nov 2023, Jun 2025) What is the difference between a recursive and recursively enumerable languages? Asked: [7 marks] (May 2023, Dec 2025) Explain Recursively enumerable language and decidability; explain decidable, undecidable, recursive and recursively enumerable languages.

Decidability

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Low weight</span>

Definition. A problem is decidable if a TM halts with the correct yes/no answer on every input; it is undecidable if no such TM exists.

Key points.

  1. Decidable examples: whether a DFA accepts a string, whether a CFG is empty, and whether a number is prime.
  2. Undecidable examples: the halting problem, whether $L(M)$ is empty for a TM, and the Post correspondence problem.
  3. A problem is undecidable when a decidable solution would let us solve a known undecidable problem (reduction).
  4. Undecidable does not mean unsolved: it is proved that no algorithm can exist.

Asked: [7 marks] (Dec 2020) What is decidable and undecidable problems?

Decidable languages

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. A decidable (recursive) language is one for which some TM halts on every input, accepting exactly the members.

Key points.

  1. Regular and context-free languages are decidable, and so are the context-sensitive languages.
  2. They are closed under union, intersection, concatenation, star and complement.
  3. The class sits inside the RE languages.

Undecidable languages

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Low weight</span>

Definition. A language is undecidable if no TM decides it; the standard one is $H$, and undecidability is proved by reduction from $H$.

Key points.

  1. Rice's theorem: every non-trivial property of the language of a TM is undecidable.
  2. "Is $L(M)$ regular?" is non-trivial, since some TM languages are regular and some are not.
  3. Proof by reduction: given $\langle M,w\rangle$, build $M'$ that on input $x$ first simulates $M$ on $w$; if $M$ halts, $M'$ then accepts $x$ only when $x\in\{0^n1^n\}$; otherwise it accepts nothing new. So $L(M')=\varnothing$ (regular) if $M$ does not halt on $w$, and $\{0^n1^n\}$ (not regular) if it does.
  4. A decider for regularity would therefore decide $H$, a contradiction, so the problem is undecidable.

Asked: [7 marks] (Nov 2022) Prove that the problem of determining whether for a Turing machine M the language L(M) is regular is undecidable.

Halting problem of Turing machine

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">High weight</span>

Definition. The halting problem asks: given a TM $M$ and input $w$, does $M$ halt on $w$? It is undecidable, meaning no TM decides it for all pairs $\langle M,w\rangle$.

Key points.

  1. The language is $H=\{\langle M,w\rangle\mid M \text{ halts on } w\}$, and it is RE, since a UTM simulates $M$ and accepts if it halts.
  2. $H$ is not recursive: no total machine can decide it.
  3. The proof uses diagonalization, as in Cantor's argument.
  4. It shows a program cannot always predict another program's behaviour.

Proof (diagonalization).

  1. Assume a decider $H_{dec}$ exists: on $\langle M,w\rangle$ it halts with "halts" or "loops".
  2. Build $D$: on input $\langle M\rangle$, run $H_{dec}$ on $\langle M,\langle M\rangle\rangle$; if it says "halts", $D$ loops forever, and if it says "loops", $D$ halts.
  3. Run $D$ on its own code $\langle D\rangle$. If $D$ halts on $\langle D\rangle$, then $H_{dec}$ said "halts", so $D$ loops: contradiction. If $D$ loops, then $H_{dec}$ said "loops", so $D$ halts: contradiction.
  4. Hence $H_{dec}$ cannot exist, and the halting problem is undecidable.

Fixed input 101. Suppose $A$ decides "does $M$ halt on 101". Given any $\langle M,w\rangle$, build $M_w$ that ignores its input, writes $w$ and runs $M$. Then $M_w$ halts on 101 iff $M$ halts on $w$, so $A$ would decide $H$, contradicting the proof above. So no algorithm exists.

H_dec(M,w) --> D(M) --> D(D) :  halts => loops, loops => halts

Answer frame. Open with the statement of the problem; write the four proof steps in order, ending on $D(D)$; for 101, add the reduction paragraph; close with "so halting is RE but not recursive".

Asked: [7 marks] (Nov 2022, Nov 2023, Dec 2025, Jun 2025) Prove that there is no algorithm that determines whether an arbitrary TM halts on input 101; what is the halting problem, why is it undecidable. Asked: [7 marks] (Jun 2025) Prove that the Halting Problem is undecidable using diagonalization. Asked: [14 marks] (May 2023) Short notes, any three: Halting problem; Turing machine; Chomsky Normal form; 2 way DFA. Asked: [14 marks] (Nov 2023) Short notes, any three: Post correspondence problem; Halting problem; Closure property of regular grammar; Turing machine.

The Post correspondence problem

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. Given two lists of strings $A=(x_1,\dots,x_k)$ and $B=(y_1,\dots,y_k)$, PCP asks whether some sequence of indices $i_1,\dots,i_m$ gives $x_{i_1}\cdots x_{i_m}=y_{i_1}\cdots y_{i_m}$.

Key points.

  1. Example: $A=(a,ab,bba)$ and $B=(baa,aa,bb)$ have the solution $3,2,3,1$, since both sides spell $bbaabbbaa$.
  2. PCP is undecidable, proved by reducing the halting problem to it.
  3. It is used to show other problems undecidable, such as ambiguity of a CFG.

Last-minute revision

  • TM 7-tuple $(Q,\Sigma,\Gamma,\delta,q_0,B,F)$ with $\delta:Q\times\Gamma\to Q\times\Gamma\times\{L,R\}$.
  • Even 1's: two states, $q_0$ even and $q_1$ odd, accept on B from $q_0$.
  • Unary addition: turn the separator 0 into 1, then erase the last 1.
  • $0^n1^n2^n$: mark X, Y, Z, shuttle back to X, accept on B (empty string accepted).
  • Multitape, multihead, multidimensional and nondeterministic TMs all have the power of a single-tape TM.
  • Recursive $\subset$ RE; recursive is closed under complement, RE is not.
  • $L$ recursive iff $L$ and $\overline L$ are both RE (run both alternately).
  • Halting language is RE but not recursive; proved by diagonal machine $D(D)$.
  • P is in NP; NP-complete = in NP and NP-hard; SAT is the first NP-complete (Cook-Levin).
  • Rice's theorem: any non-trivial property of $L(M)$ is undecidable.
  • PCP and halting are undecidable; a UTM simulates any encoded TM.

Memory hooks

  • Recursive = "Always halts"; RE = "Recognizes, maybe hangs".
  • XYZ marking: one from each group per round, then shuttle home to X.
  • Complement flip: RE plus co-RE gives recursive.
  • P = Produce quickly, NP = Nod to a proof quickly.
  • D(D) is the machine that does the opposite of what it is predicted to do.

Coverage checklist

  • Techniques for construction: Q22, Q23, Q24, Q25 (add, $0^n1^n2^n$, technique, even 1's), Turing computable function, Dec 2020 short note.
  • Universal Turing machine: Dec 2024 short note, Jun 2020 short note.
  • Multitape: Dec 2020, Jun 2025 compare, types and models of TM.
  • multihead: definition, power, simulation.
  • multidimensional Turing machine: definition, power, simulation.
  • N-P complete problems: NP-hard, P versus NP, P class, tractable versus intractable, P and NP, NP-complete, Nov 2019 short note.
  • Decidability and Recursively Enumerable Languages: Nov 2019, Jun 2025, Dec 2020, Nov 2022, Nov 2023, May 2023 and Dec 2025.
  • decidability: Dec 2020 decidable and undecidable problems.
  • decidable languages: definition and closure.
  • undecidable languages: Nov 2022 regularity proof.
  • Halting problem of Turing machine: 101 proof, diagonalization proof, May 2023 and Nov 2023 short notes.
  • the post correspondence problem: definition, example, undecidability.
Go to where you left off?

Quick Add to Notes

Save questions, your own notes and screenshots into notes filed by unit. It takes a free account.

Create free account

Have an account? Log in