BSc CSIT (TU) Science Theory of Computation (BSc CSIT, CSC257) Question Paper 2078 Nepal

Halting Problem of a Turing Machine

The Halting Problem asks: Given an arbitrary Turing machine $M$ and an input string $w$, does $M$ halt (stop) on input $w$?

Formally, define the language

The Halting Problem is to decide membership in $HALT_{TM}$.

Proof that the Halting Problem is Undecidable

We prove undecidability by contradiction (diagonalization).

1. Assume there exists a Turing machine $H$ that decides the Halting Problem. That is, for every $\langle M, w\rangle$:

2. Using $H$, construct a new machine $D$ that takes a single TM description $\langle M\rangle$ as input and behaves as follows:

D(<M>):
   run H(<M>, <M>)        # does M halt on its own description?
   if H accepts:  loop forever
   if H rejects:  halt (accept)

Thus $D$ does the opposite of what $M$ does on its own encoding.

3. Now run $D$ on its own description $\langle D\rangle$:
   • If $D$ halts on $\langle D\rangle$, then $H$ said "halts", so by construction $D$ loops — contradiction.
   • If $D$ loops on $\langle D\rangle$, then $H$ said "loops", so by construction $D$ halts — contradiction.

Either case is a contradiction, so the assumed decider $H$ cannot exist. Therefore the Halting Problem is undecidable. (It is, however, recursively enumerable / semi-decidable — a TM can simulate $M$ on $w$ and accept if it halts.)

Decidable vs. Undecidable Problems

In short: decidable problems have total deciders; undecidable problems (like the Halting Problem) have none.

Chomsky Hierarchy of Languages

Noam Chomsky classified formal grammars/languages into four nested types by restrictions on production rules. Each type corresponds to a class of grammar and an abstract machine that recognizes it.

The containment is strict: $\text{Regular} \subset \text{CFL} \subset \text{CSL} \subset \text{RE}$.

Closure Properties of Context-Free Languages

Let $L_1, L_2$ be context-free languages.

CFLs are CLOSED under:

• Union: $L_1 \cup L_2$ — combine grammars with new start symbol $S \to S_1 \mid S_2$.
• Concatenation: $L_1 L_2$ — use $S \to S_1 S_2$.
• Kleene star: $L_1^*$ — use $S \to S_1 S \mid \varepsilon$.
• Substitution and homomorphism.
• Intersection with a regular language: $L_1 \cap R$ is context-free (product of PDA and DFA).
• Reversal: $L_1^R$.

CFLs are NOT CLOSED under:

• Intersection: e.g. $L_1=\{a^n b^n c^m\}$ and $L_2=\{a^m b^n c^n\}$ are CFLs but $L_1 \cap L_2 = \{a^n b^n c^n\}$ is not context-free.
• Complementation: follows from non-closure under intersection (since $L_1 \cap L_2 = \overline{\overline{L_1} \cup \overline{L_2}}$ and CFLs are closed under union).
• Set difference in general.

These properties are central to deciding whether a language is context-free.

Complexity Classes P and NP

• P (Polynomial time): the class of decision problems solvable by a deterministic Turing machine in time $O(n^k)$ for some constant $k$, where $n$ is the input size. These are the efficiently solvable (tractable) problems. Examples: sorting, shortest path, primality testing.

• NP (Nondeterministic Polynomial time): the class of decision problems for which a proposed solution (certificate) can be verified by a deterministic TM in polynomial time; equivalently, problems solvable by a nondeterministic TM in polynomial time. Examples: SAT, Hamiltonian cycle, subset-sum.

Clearly $P \subseteq NP$ (a problem that can be solved quickly can be verified quickly). Whether $P = NP$ is the most famous open problem in computer science.

Polynomial-Time Reduction

A language $A$ is polynomial-time reducible to $B$, written $A \le_p B$, if there is a function $f$ computable in polynomial time such that

Meaning: an efficient algorithm for $B$ yields an efficient algorithm for $A$. Reductions transfer hardness: if $A \le_p B$ and $B \in P$, then $A \in P$.

NP-Completeness

A language $L$ is NP-complete if:

1. $L \in NP$, and
2. Every language $A \in NP$ satisfies $A \le_p L$ (NP-hardness).

NP-complete problems are the hardest in NP: if any one of them is in $P$, then $P = NP$.

SAT (Satisfiability) Example

The SAT problem asks whether a given Boolean formula (e.g. in CNF) has an assignment of truth values making it true.

• SAT is in NP: given a truth assignment (certificate), we can evaluate the formula in polynomial time to verify satisfaction.
• Cook–Levin Theorem: SAT is NP-complete — it was the first problem proved NP-complete by showing that the computation of any polynomial-time NDTM on an input can be encoded as a Boolean formula that is satisfiable iff the machine accepts.

Because SAT is NP-complete, it serves as the canonical starting point for proving other problems NP-complete: to show a new problem $X$ is NP-hard, we exhibit a polynomial-time reduction $\text{SAT} \le_p X$ (e.g. SAT $\le_p$ 3-SAT $\le_p$ Clique $\le_p$ Vertex Cover).

Universal Turing Machine (UTM)

A Universal Turing Machine $U$ is a single Turing machine that can simulate the behaviour of any other Turing machine $M$ on any input $w$. It takes as input an encoding $\langle M\rangle$ of the machine $M$ together with the input string $w$, i.e. the pair $\langle M, w\rangle$, and then simulates $M$ step by step:

If $M$ accepts $w$, $U$ accepts; if $M$ rejects, $U$ rejects; if $M$ loops, $U$ loops.

Significance

• Stored-program concept: The UTM treats a program (the description $\langle M\rangle$) as data on its tape — the theoretical basis for modern general-purpose, stored-program computers (von Neumann architecture).
• Programmability: A single fixed machine can perform any computation simply by changing its input, rather than building a new machine per task.
• Foundation for undecidability: The existence of a UTM makes self-reference possible and underlies proofs that the Halting Problem and the language $A_{TM}=\{\langle M,w\rangle : M \text{ accepts } w\}$ are undecidable.
• It confirms the Church–Turing thesis that Turing machines capture the notion of effective/algorithmic computation.

Recursive vs. Recursively Enumerable Languages

Both are accepted by Turing machines, but differ in the halting guarantee.

• A language is recursive (decidable) if there exists a TM that halts on every input, accepting strings in the language and rejecting those not in it.
• A language is recursively enumerable (RE / semi-decidable) if there exists a TM that halts and accepts every string in the language, but may loop forever on strings not in the language.

Key relation: $\text{Recursive} \subset \text{RE}$. A language $L$ is recursive iff both $L$ and its complement $\overline{L}$ are RE.

Mealy and Moore Machines

Both are finite-state machines with output (finite-state transducers).

Moore machine — output depends only on the current state. Defined as a 6-tuple $(Q,\Sigma,O,\delta,\lambda,q_0)$ where $\lambda: Q \to O$ associates an output with each state.

Mealy machine — output depends on the current state AND the current input symbol. Defined as a 6-tuple $(Q,\Sigma,O,\delta,\lambda,q_0)$ where $\lambda: Q \times \Sigma \to O$ associates an output with each transition.

Differences

Both models are equivalent in computational power and can be converted into each other (they compute the same input–output relations, ignoring the initial-state output of Moore).

Closure Properties of Regular Languages

Regular languages are closed under a wide range of operations: applying these operations to regular languages always yields a regular language. Let $L_1, L_2$ be regular over alphabet $\Sigma$.

• Union: $L_1 \cup L_2$ is regular (combine NFAs with a new start state and $\varepsilon$-moves).
• Concatenation: $L_1 L_2$ is regular (link accepting states of the first NFA to the start of the second).
• Kleene star: $L_1^*$ is regular (loop back accepting states to start).
• Complement: $\overline{L_1} = \Sigma^* \setminus L_1$ is regular (complete the DFA and swap accepting/non-accepting states).
• Intersection: $L_1 \cap L_2$ is regular (product/Cartesian construction of the two DFAs; also via $\overline{\overline{L_1}\cup\overline{L_2}}$).
• Set difference: $L_1 \setminus L_2 = L_1 \cap \overline{L_2}$ is regular.
• Reversal: $L_1^R$ is regular (reverse all transitions, swap start and accepting states).
• Homomorphism and inverse homomorphism preserve regularity.

Significance: Because the regular languages form a Boolean algebra (closed under union, intersection, complement), these closure properties let us build and reason about regular languages compositionally and prove non-regularity by closure arguments.

Membership Problem

The membership problem for a grammar/language asks: Given a grammar $G$ (or automaton) and a string $w$, does $w \in L(G)$? i.e. can the grammar generate the string? For context-free grammars this problem is decidable, and the CYK algorithm solves it efficiently.

CYK (Cocke–Younger–Kasami) Algorithm

The CYK algorithm decides membership of a string $w = a_1 a_2 \dots a_n$ in a context-free language. The grammar must first be converted to Chomsky Normal Form (CNF) (rules of the form $A \to BC$ or $A \to a$).

It uses dynamic programming / bottom-up parsing, filling an upper-triangular table $V[i][j]$ where $V[i][j]$ holds the set of non-terminals that can derive the substring $a_i \dots a_j$.

CYK(w = a1..an, grammar G in CNF):
  for i = 1 to n:                         # length-1 substrings
     V[i][i] = { A : (A -> a_i) in G }
  for len = 2 to n:                       # increasing substring length
     for i = 1 to n-len+1:
        j = i + len - 1
        V[i][j] = {}
        for k = i to j-1:                 # split point
           for each rule A -> B C:
              if B in V[i][k] and C in V[k+1][j]:
                 add A to V[i][j]
  accept if  S (start symbol) in V[1][n]

Result: $w \in L(G)$ iff the start symbol $S \in V[1][n]$.

Time complexity: $O(n^3 \cdot |G|)$, where $n = |w|$ — polynomial, hence the membership problem for CFLs is efficiently decidable.

NFA for $(0+1)^*1$

The regular expression $(0+1)^*1$ denotes all binary strings that end with the symbol $1$.

NFA $N = (Q, \Sigma, \delta, q_0, F)$:

• States: $Q = \{q_0, q_1\}$
• Alphabet: $\Sigma = \{0, 1\}$
• Start state: $q_0$
• Accepting state: $F = \{q_1\}$

Transition function:

Diagram (described): State $q_0$ has self-loops on both $0$ and $1$ (this realizes $(0+1)^*$, allowing any prefix). On reading a $1$, $q_0$ also has a transition to the final state $q_1$, which is the guess that this $1$ is the last symbol. $q_1$ has no outgoing transitions.

Working: The machine stays in $q_0$ consuming any combination of $0$s and $1$s, and nondeterministically moves to the accepting state $q_1$ exactly when the final input symbol is a $1$. Thus it accepts precisely the strings ending in $1$, e.g. $1, 01, 11, 001, 101 \dots$, and rejects strings ending in $0$ or the empty string.

Rice's Theorem

Statement: Every non-trivial semantic (behavioural) property of the language recognized by a Turing machine is undecidable.

Here:

• A property $P$ is a set of recursively enumerable languages (it refers to what the machine computes — i.e. its language $L(M)$ — not to how it is coded).
• The property is non-trivial if it is true for some TMs but not all — i.e. $P$ is neither the empty set nor the set of all RE languages.

Then the problem "Does $L(M)$ have property $P$?" — formally deciding $\{\langle M\rangle : L(M) \in P\}$ — is undecidable.

Explanation / Consequences

Rice's theorem generalizes the undecidability of the Halting Problem: we cannot algorithmically test any interesting property of a program's input–output behaviour. The proof reduces the Halting Problem (or $A_{TM}$) to deciding the property.

Examples of undecidable questions (by Rice's theorem):

• Is $L(M) = \emptyset$? (Is the language empty?)
• Is $L(M)$ regular / finite / infinite?
• Does $M$ accept a particular string $w$?
• Are two TMs equivalent ($L(M_1)=L(M_2)$)?

Note: The theorem applies only to semantic properties. Syntactic properties (e.g. "does $M$ have 5 states?" or "does $M$ ever move left?") are about the machine's description and can be decidable.

Alphabet, String, and Language

Alphabet ($\Sigma$): A finite, non-empty set of symbols.

• Example: $\Sigma = \{0, 1\}$ (binary alphabet); $\Sigma = \{a, b, c\}$.

String (word): A finite sequence of symbols drawn from an alphabet. The empty string is denoted $\varepsilon$ (length 0). The length $|w|$ is the number of symbols.

• Example: over $\Sigma=\{0,1\}$, the strings $0110$, $1$, and $\varepsilon$ are valid; $|0110| = 4$.
• $\Sigma^*$ denotes the set of all strings over $\Sigma$ (including $\varepsilon$); $\Sigma^+ = \Sigma^* \setminus \{\varepsilon\}$.

Language: A set of strings over a given alphabet, i.e. any subset of $\Sigma^*$. A language may be finite or infinite.

• Example over $\Sigma=\{0,1\}$:
  • $L_1 = \{0, 01, 011\}$ (finite),
  • $L_2 = \{w : w \text{ ends in } 1\}$ (infinite),
  • $L_3 = \{0^n 1^n : n \ge 0\}$,
  • $\emptyset$ (the empty language) and $\{\varepsilon\}$ are both valid languages.

DFA vs. NFA

Both are finite automata of the form $(Q, \Sigma, \delta, q_0, F)$ and accept exactly the regular languages, but they differ in how transitions are defined.

Equivalence: Every NFA can be converted to an equivalent DFA by the subset (powerset) construction; an NFA with $n$ states yields a DFA with at most $2^n$ states. Hence DFA and NFA have the same expressive power — both recognize exactly the class of regular languages.