Theory of Computation (AD-501) Unit 5 Notes

How unit 5 is examined

This unit covers the Turing machine, its language classes, undecidability and P/NP; the marks sit in the Turing machine designs (a^n b^n c^n, 2's complement), the halting problem with PCP, the Universal TM and P, NP, NP-complete.

Turing Machine as acceptor

<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 Turing machine is a 7-tuple $M=(Q,\Sigma,\Gamma,\delta,q_0,B,F)$ with a finite control and an infinite tape, and it accepts a string $w$ if, started on $w$, it reaches a final state in $F$.==

Key points.

$Q$ is the finite set of states, $\Sigma$ the input alphabet, $\Gamma\supseteq\Sigma$ the tape alphabet, $B\in\Gamma$ the blank, $q_0$ the start state and $F$ the final states.
The transition function is $\delta: Q\times\Gamma\to Q\times\Gamma\times\{L,R\}$: read a symbol, write a symbol, move the head left or right, and change state.
The tape is unbounded on the right, the head reads one cell at a time, and the input is written on the tape with blanks around it.
The machine accepts by entering a final state, rejects by halting in a non-final state or with no move defined, and may loop forever.
Design method: mark symbols with new tape symbols (X, Y, Z) so that each is matched exactly once, then check that nothing unmarked is left.

Diagram. TM for $a^nb^nc^n$. Each $a$ is marked X, the first unmarked $b$ becomes Y, the first $c$ becomes Z, then the head returns left.

<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 338 338" width="338" height="338" role="img" aria-label="TM for a^n b^n c^n. q1 skips a,Y; q2 skips b,Z; q3 moves left over a,b,Y,Z to X; q4 skips Y,Z; qf accepts."><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="ah7" 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="ahh7" 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="M55.8,115.5 L151.5,51.6" marker-end="url(#ah7)"/><path class="e" d="M188,40 L277,40" marker-end="url(#ah7)"/><path class="e" d="M298,59 L298,191" marker-end="url(#ah7)"/><path class="e" d="M280,206 L59.9,132.6" marker-end="url(#ah7)"/><path class="e" d="M55.8,136.5 L151.5,200.4" marker-end="url(#ah7)"/><path class="e" d="M153.2,222.5 L57.5,286.4" marker-end="url(#ah7)"/><g class="wl"><rect x="81" y="74" width="47.1" height="18" rx="9"/><text class="t" x="104.5" y="83" dy=".35em" text-anchor="middle">a/X,R</text></g><g class="wl"><rect x="210" y="31" width="47.1" height="18" rx="9"/><text class="t" x="233.5" y="40" dy=".35em" text-anchor="middle">b/Y,R</text></g><g class="wl"><rect x="274.5" y="117" width="47.1" height="18" rx="9"/><text class="t" x="298" y="126" dy=".35em" text-anchor="middle">c/Z,L</text></g><g class="wl"><rect x="145.5" y="160" width="47.1" height="18" rx="9"/><text class="t" x="169" y="169" dy=".35em" text-anchor="middle">X/X,R</text></g><g class="wl"><rect x="81" y="160" width="47.1" height="18" rx="9"/><text class="t" x="104.5" y="169" dy=".35em" text-anchor="middle">Y/Y,R</text></g><g class="wl"><rect x="81" y="246" width="47.1" height="18" rx="9"/><text class="t" x="104.5" y="255" dy=".35em" text-anchor="middle">B/B,R</text></g><circle class="n" cx="40" cy="126" r="18"/><text class="t" x="40" y="126" dy=".35em" text-anchor="middle">q0</text><circle class="n" cx="169" cy="40" r="18"/><text class="t" x="169" y="40" dy=".35em" text-anchor="middle">q1</text><circle class="n" cx="298" cy="40" r="18"/><text class="t" x="298" y="40" dy=".35em" text-anchor="middle">q2</text><circle class="n" cx="298" cy="212" r="18"/><text class="t" x="298" y="212" dy=".35em" text-anchor="middle">q3</text><circle class="n" cx="169" cy="212" r="18"/><text class="t" x="169" y="212" dy=".35em" text-anchor="middle">q4</text><circle class="n" cx="40" cy="298" r="18"/><text class="t" x="40" y="298" dy=".35em" text-anchor="middle">qf</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">TM for a^n b^n c^n. q1 skips a,Y; q2 skips b,Z; q3 moves left over a,b,Y,Z to X; q4 skips Y,Z; qf accepts.</figcaption></figure>

Example (a^n b^n c^n, n=1: abc). q0 marks a as X, q1 marks b as Y, q2 marks c as Z and returns; q3 stops at X and moves right to q0; q0 sees Y, so q4 skips Y and Z, reads B and reaches qf: accepted. For $aabc$ the second round finds no $c$ for the second $a$, so the machine halts unaccepted.

Example (2's complement, Sigma={0,1}). Method: go to the right end, then move left copying every 0 up to and including the first 1 from the right, and flip every bit after it.

State	0	1	B
q0	0,R,q0	1,R,q0	B,L,q1
q1	0,L,q1	1,L,q2	B,R,qf
q2	1,L,q2	0,L,q2	B,R,qf

Trace for 00000: q0 runs right to B, q1 moves left over all five 0s to the left blank and reaches qf. Output: 00000 (no 1 exists, so nothing flips). Check: 0110 gives 1010, 1000 gives 1000, 101 gives 011.

Answer frame. Open with the 7-tuple and the meaning of acceptance; draw the transition diagram or table; explain the marking loop or the scan-and-flip rule in order; show the trace; close with "the machine accepts exactly when the input is in L".

Pitfall: Forgetting the final check (only Y and Z left) lets $aabbc$ style strings be accepted.

Asked: [7 marks] (Nov 2022) Design a Turing machine for the language $L=\{a^nb^nc^n \mid n\ge1\}$. Asked: [7 marks] (Nov 2023) Design a Turing machine that computes 2's complement of a string over $\Sigma=\{0,1\}$. Show the output for "00000".

Recognizing a Language

Definition. A TM recognizes language $L$ if it accepts every string of $L$ and never accepts a string outside $L$.

Key points.

For strings in $L$ the machine halts in a final state; for strings outside $L$ it may reject or loop forever.
The languages recognized by some TM are the recursively enumerable (Turing-recognizable) languages.
A machine that always halts, accepting or rejecting, decides the language, which is the stronger notion.

Universal TMs

Definition. <mark>A Universal Turing Machine (UTM) is a single TM that takes the encoding $\langle M,w\rangle$ of any TM $M$ and input $w$, and simulates $M$ on $w$.</mark>

Key points.

Encoding: states, tape symbols and moves are written as strings over $\{0,1\}$ (for example unary blocks separated by 1s), and the transition table of $M$ is listed as a string on the tape.
The UTM uses tape areas for the description of $M$, the current simulated tape of $M$, and the current state of $M$.
Working is a fetch-decode-execute cycle: read the simulated symbol and state, search the table for the matching rule, write the symbol, move the head and update the state.
It accepts $\langle M,w\rangle$ exactly when $M$ accepts $w$, so it recognizes but does not decide the language $A_{TM}$.
Significance: it is the stored-program idea, since program and data are both on the tape, and it underlies the halting-problem proof.

Answer frame. Open with the definition; list the encoding and tape layout; describe fetch-decode-execute; close with the stored-program significance.

Asked: [7 marks] (Nov 2022) Discuss about the Universal Turing Machine.

Linear Bounded Automata

Definition. A linear bounded automaton is a nondeterministic TM whose head is restricted to the tape cells holding the input, marked by end-markers.

Key points.

The usable tape length is a linear function of the input length, and the head can never leave the end-markers.
The end-markers are never overwritten and the head never moves beyond them.
LBAs accept exactly the context sensitive languages.
It is a weaker model than a TM, since its memory is bounded.

Context Sensitive Languages

Definition. A context sensitive grammar has productions $\alpha\to\beta$ with $|\alpha|\le|\beta|$, and its language is a context sensitive language (CSL), Type 1.

Key points.

Productions never shorten a sentential form, so a string of length $n$ can be checked within space linear in $n$.
CSLs are exactly the languages accepted by linear bounded automata.
Example: $a^nb^nc^n$ is context sensitive but not context free.
In the Chomsky hierarchy, regular is inside CFL, which is inside CSL, which is inside recursive, which is inside RE.

Recursive and Recursively Enumerable Languages

Definition. A language is recursive if some TM halts on every input and accepts exactly the strings of $L$; it is recursively enumerable (RE) if some TM accepts exactly its strings, possibly looping on others.

Key points.

Every recursive language is RE, but not every RE language is recursive; the halting language $A_{TM}$ is RE and not recursive.
Recursive languages are closed under complement, union and intersection.
A language is recursive if and only if both $L$ and $\overline{L}$ are RE.
RE languages are closed under union and intersection but not under complement.

Unrestricted Grammars

Definition. An unrestricted (Type 0) grammar has productions $\alpha\to\beta$ where $\alpha$ is any non-empty string containing at least one variable and $\beta$ is any string.

Key points.

There is no restriction on lengths or contexts, so derivations can shorten as well as lengthen strings.
Unrestricted grammars generate exactly the recursively enumerable languages, the same class a TM accepts.
Type 0 is the most general level of the Chomsky hierarchy.

Halting problem of Turing machine & the post correspondence problem

Definition (halting problem). <mark>The halting problem asks whether, given a TM $M$ and input $w$, $M$ halts on $w$; it is undecidable, so no algorithm answers it for all pairs.</mark>

Key points (halting).

The language $HALT=\{\langle M,w\rangle \mid M \text{ halts on } w\}$ is recursively enumerable (a UTM can simulate and accept if it halts) but not recursive.
Proof by contradiction: assume a halting decider $H(M,w)$ exists that answers halt or loop.
Build $D$ which, on input $\langle M\rangle$, runs $H(M,\langle M\rangle)$; if $H$ says "halts", $D$ loops forever; if $H$ says "loops", $D$ halts.
Run $D$ on its own description $\langle D\rangle$: if $D$ halts then $H$ said "loops", so $D$ loops, and if $D$ loops then $D$ halts.
Both cases contradict, so $H$ cannot exist and the halting problem is undecidable.
Consequence: many other questions (does a program ever print, is a language empty, are two programs equal) are undecidable by reduction from it.

Definition (PCP). ==Given two lists of strings $X=(x_1,\dots,x_n)$ and $Y=(y_1,\dots,y_n)$, the Post correspondence problem asks for a sequence of indices $i_1,\dots,i_k$ ($k\ge1$) such that $x_{i_1}\cdots x_{i_k}=y_{i_1}\cdots y_{i_k}$.==

Key points (PCP).

Each index $i$ gives a domino (tile) $(x_i,y_i)$; a match is a sequence of dominoes whose top string equals the bottom string, and indices may be repeated.
PCP is undecidable in general, shown by reduction from the halting problem.
A particular instance may have a solution, found by trial from a start pair whose strings begin the same way.

Example (Nov 2022 paper). $X=(ba,ab,a,baa,b)$, $Y=(bab,baa,ba,a,aba)$.

i	1	2	3	4	5
$x_i$	ba	ab	a	baa	b
$y_i$	bab	baa	ba	a	aba

Start with 1 (ba against bab, so the bottom has extra b); 4 continues (baa against a, extra bab then a...), then 5, 3, 4 close the gap.

Index	1	4	5	3	4
X	ba	baa	b	a	baa
Y	bab	a	aba	ba	a

X string = ba+baa+b+a+baa = babaababaa; Y string = bab+a+aba+ba+a = babaababaa. Solution: sequence 1, 4, 5, 3, 4 with common string babaababaa.

Answer frame. PCP question: define PCP, tabulate the pairs, give the index sequence, then verify both concatenations are equal. Halting short note: define, state undecidability, give the diagonal proof (points 2-5), close with the consequence and use of reduction.

Pitfall: Show both concatenated strings side by side; a sequence without the verification loses the marks.

Asked: [7 marks] (Nov 2022) Define PCP. Give the solution of PCP $X=(ba,ab,a,baa,b)$ and $Y=(bab,baa,ba,a,aba)$. Asked: [14 marks] (Nov 2023) Write short notes on (any two): a) Variation of Turing Machine b) Two way finite automata c) Multitape d) Halting problem of Turing machine.

Concept of Solvability and Unsolvability

Definition. A problem is solvable (decidable) if some TM halts on every input with the correct yes or no answer; otherwise it is unsolvable (undecidable).

Key points.

Undecidable problems have no algorithm at all, however much time or memory is allowed.
Examples: halting problem, PCP, whether a TM accepts an empty language, and whether a CFG is ambiguous.
Undecidability is proved by contradiction or by reduction from a known undecidable problem.
Decidable examples: membership for regular languages, CFLs and CSLs.

Church's Thesis

Definition. Church's (Church-Turing) thesis states that every function that can be computed by an effective procedure can be computed by a Turing machine.

Key points.

It is a thesis, not a theorem, because "effective procedure" is informal and cannot be proved.
Lambda calculus, recursive functions, register machines and modern programming languages have all been shown equivalent in power to TMs.
So algorithm is taken to mean a TM that halts, which is why TM undecidability means no algorithm exists.

Complexity Theory – P and NP problems

Definition. <mark>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 verifiable in polynomial time.</mark>

Key points.

P example: sorting, shortest path, and testing if a number is in a list; all run in time $O(n^k)$.
NP example: the travelling salesman decision problem, subset sum and Hamiltonian cycle, where a proposed answer is checked in polynomial time.
A problem is NP-hard if every NP problem reduces to it in polynomial time, and NP-complete if it is in NP and NP-hard.
Example NP-complete problems: SAT (Cook's theorem), 3-SAT, vertex cover and the clique problem.
$P\subseteq NP$; whether $P=NP$ is open, and if any NP-complete problem is in P then $P=NP$.

Answer frame. Define P, NP and NP-complete in that order, with one example each, state $P\subseteq NP$, and close with the P versus NP question.

Asked: [7 marks] (Nov 2023) Explain the terms P, NP, NP complete. Give suitable example.

Last-minute revision

A TM is $(Q,\Sigma,\Gamma,\delta,q_0,B,F)$ with $\delta:Q\times\Gamma\to Q\times\Gamma\times\{L,R\}$.
$a^nb^nc^n$ TM: mark a as X, b as Y, c as Z, return to X, repeat, then check only Y and Z remain.
2's complement TM: scan right, then copy left up to and including the first 1, flip the rest; 00000 stays 00000.
UTM simulates any $\langle M,w\rangle$: fetch, decode, execute; the stored-program idea.
LBA accepts CSLs, and CSL productions satisfy $|\alpha|\le|\beta|$.
Recursive is inside RE; a language is recursive iff $L$ and $\overline L$ are both RE.
Type 0 grammars generate exactly the RE languages.
Halting problem is undecidable, proved by the diagonal machine $D$; $HALT$ is RE but not recursive.
PCP is undecidable; Nov 2022 solution is 1, 4, 5, 3, 4 giving babaababaa.
Church's thesis: computable means computable by a TM (not provable).
$P\subseteq NP$; NP-complete means in NP and NP-hard; SAT is the first NP-complete problem.

Memory hooks

XYZ marks: a becomes X, b becomes Y, c becomes Z.
2's complement: "keep up to the first 1 from the right, flip the rest".
Decides equals halts always; recognizes equals accepts only.
1-4-5-3-4: the PCP answer, "one four five three four".
P is find fast, NP is check fast.

Coverage checklist

Turing Machine as acceptor: Q4 (a^n b^n c^n), Q5 (2's complement).
Recognizing a Language: no past question.
Universal TMs: Q6.
Linear Bounded Automata: no past question.
Context Sensitive Languages: no past question.
Recursive and Recursively Enumerable Languages: no past question.
Unrestricted Grammars: no past question.
Halting problem of Turing machine & the post correspondence problem: Q3 (PCP), Q1 (short notes).
Concept of Solvability and Unsolvability: no past question.
Church's Thesis: no past question.
Complexity Theory – P and NP problems: Q2.

Account

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

How unit 5 is examined

Turing Machine as acceptor

Recognizing a Language

Universal TMs

Linear Bounded Automata

Context Sensitive Languages

Recursive and Recursively Enumerable Languages

Unrestricted Grammars

Halting problem of Turing machine & the post correspondence problem

Concept of Solvability and Unsolvability

Church's Thesis

Complexity Theory – P and NP problems

Last-minute revision

Memory hooks

Coverage checklist