Theory of Computation:

  • Is one of the most fundamental courses of Computer Science
  • Will help you understand how people have thought about Computer Science as a Science in the past 50 years
  • Is mainly about what kind of things can you really compute mechanically, how fast can you do it and how much space does it take to do so.


Can we design a machine that accepts all binary strings that end in $\displaystyle'{0}'$?

→ YES we can. The machine can easily scan the last digit and decide whether it is $\displaystyle{0}$ or $\displaystyle{1}$ and can accept the string if it happens to end with $\displaystyle{0}$

2. Can we design a machine that accepts all valid JAVA codes?

→ YES we can. The COMPILERS that we use are the best example for this and they do the exact same thing.

Can we design a machine that accepts all valid JAVA codes and NEVER GOES INTO AN INFINITE LOOP?

→ NO we can’t. It is not possible to design a machine that will never allow a code to go into infinite loop.

The basic idea of this subject is depicted using the figure below. We give an input to the machine/ system that we design and the machine either accepts or rejects the input based on some predefined rules

basic idea of TOC

Layers / Levels of the Subject that will be studied:

levels of TOC

No homework for this lecture

Theory of Computation

Chapter 1: Introduction

11:35Lec 1: Introduction to Theory of Computation 15:32Lec 2: Finite State Machine (Prerequisits) 11:05Lec 3: Finite State Machine (Finite Automata)

Subscribe on YouTube