Theoretical Computer Science is a field where all the real world computational problems come under it. Theoretical Computer Science is also called as Theory of Computation. Theory of computation speaks about “How efficiently the real world problems can be solved by using an algorithm in a model of computation. The model of computation denotes any mathematical model which is embedded on any electronic hardware through the software. Theory of computation is divided in to three sub fields. They are automata theory, computability theory and computational complexity theory. Automata theory denotes the study of problem solving in abstract machines. Here the abstract machines are called as mathematical model rather than it’s not a hardware. Automata theory has various types of automata such as Deterministic Finite Automata, Non-deterministic finite automata, Pushdown Automata and Linear Bounded Automata. These entire automata can be performed in a single hardware called “Turing Machine”. Till now nobody proved that, a problem that cannot be solved by a Turing Machine can be solved by a real world computer. The Computability speaks about “what are all the problems can be solved by a computer and cannot be solved by a computer”. This is called as decidability and un-decidability. The computational complexity theory speaks about “how much time and space an algorithm takes to solve a problem. This is called as Time and Space Complexity. These are the topics are discussed in this course “Principles in Theory of Computation”.
