Theory of Computation Lecture Notes

Introduction

• Considered the most abstract and foundational course for computer scientists.
• Focuses on the fundamental questions in computer science:
  • What can we compute?
  • How fast can we compute it?
  • How much space and memory are needed?
• Known as Theory of Computation.
• Applications include:
  • Compiler design.
  • Finite state machines used in computer architecture and string searching.

Key Concepts

Models of Computation

• Discusses different models of computation.
• Program or computation takes an input, processes it, and outputs "yes" or "no."
• Simplifies computation to strings over a chosen alphabet.

Examples

• Binary strings that end in 0.
• Java programs represented as binary strings.
• Checking if Java programs will go into infinite loops (Halting problem).

Turing Machine

• Alan Turing's abstraction of computation.
• Represents the most powerful form of computation possible with a simple machine.

Course Blueprint

Hierarchy of Computation

1. Finite State Machines (FSM):
   • Simplest model.
   • Can handle simple computations like string endings.
2. Context-Free Languages:
   • More complex languages.
   • Used in compilers and language representation.
3. Turing Machines:
   • Full level of computation.
   • Can compute anything that can be computed with current programming languages.
4. Undecidable Problems:
   • Problems that no mechanical program can solve (e.g., Halting Problem).

Finite State Machines (FSM)

• Definition & Structure:
  • States and transitions based on input symbols.
  • Start and final states determine if a string is accepted.
• Example Problems:
  • Strings with an even number of zeros.
  • Strings divisible by 4.
  • Strings containing a specific substring.
• Design and Analysis:
  • Design involves understanding the problem semantics.
  • Can be minimized to find the simplest form.

Non-Deterministic Finite Automata (NFA)

• Allows for multiple transitions for the same input.
• Accepts a string if there exists a path that ends in a final state.
• Easier to design but can be converted to deterministic finite automata (DFA).
• Conversion Process:
  • Track all potential states in the DFA.
  • Resulting DFA may have exponentially more states than the NFA.

Advanced Topics

Non-Determinism

• Enables parallel computations and decisions.
• Use Cases:
  • Simplifies the design of string matchers.
  • Provides a framework for discussing computational complexity.

Computational Hierarchies

• Distinctions between P, NP, and other complexity classes.
• Hierarchies within Turing machines and their applications.

Challenges of FSM

• FSM cannot handle computations requiring counting beyond a finite limit.
• Examples:
  • Equal numbers of zeros and ones.
  • Strings that require counting or complex arithmetic.

Proof Techniques

• Diagonalization: Used for proving undecidability.
• Finite state machine minimization: Proves there is a canonical form for FSM.

Conclusion

• Understanding FSM is crucial as a foundational layer of computation.
• Provides a basis for studying higher levels of computational theory and complexity.