Theory of Computation Basics: Models, Problems & Computability Foundations

TAKEAWAYS:

• Computation is modeled using abstract machines (Turing machines, finite automata) that define the boundaries of what problems can be solved.
• Problems are classified as tractable (solvable efficiently) or intractable (solvable but inefficiently or unsolvable), with P and NP being the most critical classes.
• Recursive functions and recursive languages are the building blocks for defining computable problems, while recursively enumerable languages extend this to problems where solutions can be verified but not always found.
• The Church-Turing thesis unifies all reasonable models of computation, implying that if a problem can be solved by any algorithm, it can be solved by a Turing machine.
• Reduction is a key technique to prove problem hardness, showing that one problem is at least as hard as another.
• Real-world systems (e.g., eSewa’s payment validation, Pathao’s route optimization, or NEPSE’s stock matching) rely implicitly on these models to define what computations are possible.

1. What is Computation? Formal Models and Their Purpose

Computation is the process of transforming input into output using a well-defined set of rules. In Theory of Computation, we study abstract models of computation to answer fundamental questions:

• What problems can be solved by computers?
• What problems cannot be solved, even in theory?
• How do we classify problems by their computational difficulty?

The three most important models are:

1. Finite Automata (FA): Models simple computations (e.g., keyword matching in text).
2. Pushdown Automata (PDA): Models computations with memory (e.g., parsing nested structures like parentheses).
3. Turing Machines (TM): The most powerful model, capable of simulating any computer algorithm.

Why Abstract Models?

Real computers are complex, but their core logic can be distilled into these models. For example:

• A finite automaton can model a spam filter that checks if an email contains forbidden keywords.
• A Turing machine can model compilation, where source code is transformed into machine code.

2. Recursive Functions and Recursive Languages

Recursive Functions

A recursive function is a function that can be defined in terms of itself. In computation theory, recursive functions are used to define computable problems.

Definition: A function $f$ is recursive if there exists a Turing machine that computes $f$ for all inputs in finite time.

Example: The Ackermann function is a classic recursive function: $$A(m,n)=\{\begin{array}{ll}n+1& \text{if }m=0,\\ A(m-1,1)& \text{if }m>0\text{ and }n=0,\\ A(m-1,A(m,n-1))& \text{otherwise.}\end{array}$$ This function grows extremely rapidly and cannot be computed by primitive recursion alone.

Recursive Languages

A language $L$ is recursive (or decidable) if there exists a Turing machine that always halts and accepts if the input is in $L$ and rejects otherwise.

Example: The language $L=\{a^n{b}^n\mid n\ge 0\}$ is recursive because a Turing machine can count the number of $a$'s and $b$'s and verify if they match.

Recursively Enumerable Languages

A language $L$ is recursively enumerable (RE) if there exists a Turing machine that halts and accepts if the input is in $L$, but may loop forever if the input is not in $L$.

Example: The Halting Problem language $L_{halt}=\{⟨M,w⟩\mid M\text{ halts on input }w\}$ is RE but not recursive.

3. The Church-Turing Thesis

The Church-Turing thesis states:

Any function that can be computed by an algorithm can be computed by a Turing machine.

This thesis unifies all models of computation (e.g., lambda calculus, while-programs) under the Turing machine model.

Implications:

• If a problem cannot be solved by a Turing machine, it cannot be solved by any computer program.
• The thesis is not a theorem (it cannot be proven), but it is widely accepted because no counterexample has been found.

4. Decidability and Undecidability

Decidable Problems

A problem is decidable if there exists an algorithm that always halts with the correct answer.

Example:

• Palindrome Check: Given a string $w$, is $w$ a palindrome? Algorithm: Compare characters from the start and end moving inward. Turing Machine: Can simulate this comparison and halt with "accept" or "reject."

Undecidable Problems

A problem is undecidable if no Turing machine can solve it for all inputs.

Example 1: The Halting Problem

• Problem: Given a Turing machine $M$ and input $w$, does $M$ halt on $w$?
• Proof of Undecidability: Assume a decider $H$ exists for the Halting Problem. Then, construct a machine $D$ that:
  1. Takes input $⟨M,w⟩$.
  2. Runs $H$ on $⟨M,w⟩$.
  3. If $H$ accepts, $D$ loops forever; if $H$ rejects, $D$ halts. This leads to a contradiction (see diagonalization below).

Example 2: The Empty Language Problem for TM

• Problem: Given a Turing machine $M$, does $M$ accept any input?
• Proof: Reduce from the Halting Problem. If $M$ halts on some input, it accepts the empty language if it never halts on any input.

5. Reduction and Problem Hardness

Many-One Reduction

A problem $A$ is reducible to problem $B$ (written $A{\le }_{m}B$) if any algorithm for $B$ can be used to solve $A$.

Example:

• Problem $A$: Given a graph $G$, is it connected?
• Problem $B$: Given a graph $G$ and vertices $u,v$, is there a path from $u$ to $v$?
• Reduction: To check if $G$ is connected, run $B$ for all pairs $(u,v)$. If any pair fails, $G$ is disconnected.

NP-Completeness

A problem is NP-complete if:

1. It is in NP (a solution can be verified in polynomial time).
2. Every problem in NP can be reduced to it in polynomial time.

Example:

• Boolean Satisfiability (SAT): Given a Boolean formula, is there an assignment of variables that makes it true?
• Reduction: Many NP problems (e.g., Hamiltonian Cycle, Knapsack) can be reduced to SAT.

6. P vs. NP: The Million-Dollar Question

Definitions

• P: Problems solvable in polynomial time by a deterministic Turing machine.
• NP: Problems where a solution can be verified in polynomial time (but may not be efficiently computable).
• NP-Hard: At least as hard as any NP problem (not necessarily in NP).
• NP-Complete: In NP and NP-hard.

The P vs. NP Question

Is every problem whose solution can be verified quickly also solvable quickly?

Current Status:

• No one knows if $P=NP$ or $P\ne NP$.
• If $P=NP$, many "hard" problems (e.g., cryptography, optimization) would become tractable.
• If $P\ne NP$, it would revolutionize computer science.

Tractable vs. Intractable Problems

7. Real-World Applications

In the Real World

1. eSewa’s Payment Validation

   • Idea Used: Recursive functions and decidable problems.
   • How: eSewa checks if a transaction is valid by recursively verifying each step (e.g., checking account balance, OTP validity). This is a decidable problem because the system can always halt with "accept" or "reject."

2. Pathao’s Route Optimization

   • Idea Used: P vs. NP and NP-Hard problems.
   • How: Finding the fastest route for a driver is an NP-Hard problem (similar to the Traveling Salesman Problem). Pathao uses heuristics (approximate solutions) because an exact solution would take too long.

3. NEPSE’s Stock Matching

   • Idea Used: Recursively enumerable languages and verification.
   • How: NEPSE’s system must verify that a trade is valid (e.g., buyer has enough shares, seller has enough shares). This is in NP because verification is fast, but finding the best trade (maximizing profit) is NP-Hard.

4. Khalti’s Fraud Detection

   • Idea Used: Reduction and NP-Completeness.
   • How: Khalti’s system reduces fraud detection to checking patterns in transactions. If a transaction matches a known fraud pattern (e.g., too many rapid payments), it is flagged. This is similar to SAT where each transaction is a Boolean variable.

5. NTC’s Network Routing

   • Idea Used: Turing Machines and decidability.
   • How: NTC’s routers use finite automata to decide the next hop for a packet. The routing table is a decidable problem because the router can always find the next step (or reject the packet if no route exists).

8. Worked Example: Proving a Language is Recursive

Problem: Show that $L=\{a^n{b}^n{c}^n\mid n\ge 0\}$ is recursive.

Solution: We design a Turing machine $M$ that:

1. Counts the number of $a$'s: Move right, mark each $a$ until a $b$ is encountered.
2. Counts the number of $b$'s: Move right, mark each $b$ until a $c$ is encountered.
3. Counts the number of $c$'s: Move right, mark each $c$ until the end of the tape.
4. Compares the counts: If all counts match, accept; otherwise, reject.

Trace for Input $aabbcc$:

Initial tape: a a b b c c $
Step 1: Mark \( a \)'s → [X X] b b c c $
Step 2: Mark \( b \)'s → [X X] [X X] c c $
Step 3: Mark \( c \)'s → [X X] [X X] [X X] $
Step 4: Counts match (3 \( a \)'s, 3 \( b \)'s, 3 \( c \)'s) → ACCEPT.

Why is this recursive? The Turing machine always halts and gives the correct answer for any input.

9. Worked Example: Proving a Problem is NP-Complete

Problem: Show that Hamiltonian Cycle (HC) is NP-Complete.

Solution:

1. HC is in NP:

   • Given a cycle, we can verify in polynomial time that it visits every vertex exactly once and returns to the start.

2. Reduce from SAT (which is NP-Complete):

   • For any Boolean formula $\varphi$, construct a graph $G$ where:
     • Each variable $x_i$ is represented by two vertices $x_i$ and $\neg x_i$.
     • Each clause is represented by a gadget that forces the clause to be satisfied.
   • If $\varphi$ is satisfiable, $G$ has a Hamiltonian cycle; otherwise, it does not.

Example Reduction: For $\varphi =(x_1\vee \neg x_2)\wedge (x_2\vee x_3)$, construct $G$ as follows:

• Vertices: $x_1,\neg x_1,x_2,\neg x_2,x_3,\neg x_3$.
• Edges: Connect vertices to enforce clause satisfaction (e.g., if $x_1$ is true, the first clause is satisfied).

Implication: Since SAT reduces to HC, and HC is in NP, HC is NP-Complete.

10. Visualizing Computation Models

Finite Automaton (FA)

stateDiagram-v2
    [*] --> q0
    q0: q0
    q0 -->|a| q1
    q1: q1
    q1 -->|b| q2
    q2: q2
    q2 -->|a| q1
    q2 -->|b| q3
    q3: Accepting State
    q1 -->|b| [*]
    q2 -->|a| [*]

Caption: A finite automaton for $L=\{a^n{b}^n\mid n\ge 1\}$. It only accepts strings with equal numbers of $a$'s followed by $b$'s.

Turing Machine Tape

![turing machine tape diagram](/media/187057100e36e51d9291.png "A Turing machine's tape with read/write head. (Image: Cbuckley, CC BY-SA 3.0, via Wikimedia Commons)")

Caption: A Turing machine’s tape stores input, and the head reads/writes symbols. The machine moves left/right and changes states based on the current symbol.

Reduction Graph (SAT to HC)

graph LR
    A["SAT Problem"] -->|"Polynomial Reduction"| B["Graph Construction"]
    B --> C["Hamiltonian Cycle Problem"]
    C -->|"Solution"| D["Accept/Reject"]

Caption: Reduction from SAT to Hamiltonian Cycle. If SAT is NP-Complete, then HC must also be NP-Complete.

P vs. NP Venn Diagram

Caption: If $P=NP$, then every problem whose solution can be verified quickly can also be solved quickly.

11. Common Mistakes to Avoid

1. Confusing Recursive and Recursively Enumerable:

   • Recursive: Always halts (decidable).
   • Recursively Enumerable: May loop forever (e.g., Halting Problem).

2. Assuming All NP Problems are NP-Complete:

   • NP-Complete problems are the "hardest" in NP. Not all NP problems are NP-Complete (e.g., Prime Check is in P).

3. Ignoring the Church-Turing Thesis:

   • It’s not a theorem, but it’s the foundation for defining computability.

4. Misapplying Reduction:

   • A reduction must be polynomial-time to preserve hardness.

12. Exam Tip

How This Unit is Examined

1. Definitions (20-30%):

   • Expect questions on recursive functions, recursively enumerable languages, decidable/undecidable problems, and P/NP/NP-Complete.
   • Example Question: "Define a recursively enumerable language and give an example that is not recursive."

2. Proofs (30-40%):

   • Prove a language is recursive (design a Turing machine).
   • Prove a problem is NP-Complete (show it’s in NP and reduce from a known NP-Complete problem).
   • Example Question: "Show that the language $L=\{a^n{b}^n{c}^n\mid n\ge 0\}$ is recursive."

3. P vs. NP (20-30%):

   • Explain the difference between tractable (P) and intractable (NP-Complete) problems.
   • Discuss real-world implications (e.g., cryptography, optimization).
   • Example Question: "Is P=NP? Explain why this question is significant in computer science."

4. Applications (10-20%):

   • Relate theory to real-world systems (e.g., eSewa’s validation, Pathao’s routing).
   • Example Question: "How does the concept of NP-Completeness apply to Daraz’s order fulfillment system?"

Key Formulas to Remember

What to Draw in the Exam

1. Turing Machine Tape: For decidability proofs.
2. Finite Automaton: For regular language examples.
3. Reduction Graph: For NP-Completeness proofs.
4. Venn Diagram: For P vs. NP vs. NP-Hard.

13. Summary Table

14. Practice Questions

1. Define a recursively enumerable language and give an example that is not recursive.
2. Design a Turing machine that decides $L=\{w\mid w\text{ has an equal number of }0\text{’s and }1\text{’s}\}$.
3. Prove that the Subset Sum Problem is NP-Complete by reducing from SAT.
4. Explain why the Halting Problem is undecidable using a proof by contradiction.
5. Discuss how NP-Completeness affects real-world systems like eSewa or Pathao.

15. Further Reading

• Books:
  • Introduction to the Theory of Computation by Michael Sipser.
  • Computability and Logic by George Boolos, John Burgess, and Richard Jeffrey.
• Online Resources:
  • MIT OpenCourseWare: Theory of Computation.
  • NP-Completeness Proofs: Garey & Johnson’s Computers and Intractability.