Theory of Computation - Lecture 1

Introduction

• Instructor: Raghunath Tewari
• Overview of the course: Theory of Computation
• Topics covered:
  • Introduction to computation
  • Basic model: Finite Automata

What is Computation?

• Definition: Step-by-step solution to a problem.
• Examples:
  • Multiplication of two numbers: Use known algorithms to get the product.
  • Searching a word in a dictionary:
    • Words are ordered alphabetically.
    • Reduce search base until the word is found.
  • Graph Reachability Problem:
    • Given two vertices (s and t), determine if a path exists from s to t.
    • Use graph traversal algorithms (e.g., depth-first or breadth-first search).
• Key Point: Algorithms provide a method to answer computational questions.

Computational Devices

• Various devices can compute solutions:
  • Calculator: Performs basic arithmetic operations.
  • Smartphones: Multifunctional computational devices.
  • Computer: Popular computational device.
  • Pen and Paper: Traditional computational device.
• Focus of the Course:
  • Study computational devices based on their resources, power, and limitations.
  • Explore which problems can/cannot be solved by these devices and provide mathematical proofs.

Finite Automata

• Definition: A computational model with a finite amount of memory (finite number of states).
• Terminology:
  • “Automata” is the plural of “automaton.”

Examples of Finite Automata

1. Electric Switch:

   • States: ON and OFF
   • Transitions:
     • Push operation changes the state.
     • Odd pushes: ON, Even pushes: OFF.

2. Fan Regulator:

   • States: OFF (0), Low (1), Medium (2), High (3)
   • Transitions:
     • Clockwise increases the state, Anticlockwise decreases it.
   • Example sequence of operations: CC AC CA → ends at state 2.

Mathematical Example: Binary Strings Divisible by 4

• Set L: Binary strings that are divisible by 4.
• Key Insight:
  • Strings in L must end with two zeros (00).
  • Other endings (01, 10, 11) indicate non-divisibility by 4.
• Finite Automata Design:
  • States represent last two bits of a binary number.
  • Accept state: 00 (indicating divisibility by 4).
• State Transitions:
  • Use last two bits to determine next state based on input.
  • Example transitions:
    • 00 -> 01 (on seeing a 1), 00 -> 00 (on seeing a 0)
    • 01 -> 11 (on seeing a 1), 01 -> 10 (on seeing a 0)

Example Strings

• String 1: 110 (not accepted)
  • Transitions: 0 0 → 0 1 → 1 1 → 1 0
• String 2: 1100 (accepted)
  • Transitions: 0 0 → 0 1 → 1 1 → 1 0 → 0 0

Conclusion

• The lecture introduced basic concepts of computation and finite automata as a model.
• Emphasized understanding through examples and mathematical foundations.