Introduction
When we write Programs, we have seen that there are some programs that takes little time to execute, then there are other programs that take a lot of time to execute. So it's fair to conclude that there are easy problems, and there are difficult problems for Computers to solve.
Now we'll go a step ahead, and discuss about problems that Computers can solve, and about problems that Computers cannot solve. So all of our easy and difficult problems, will be falling under the category of problems that Computers can solve. Then there are unsolvable pronlems.
Theory of Computation is the study of problems that can be solved mechanically, also the speed, and the space taken by the solution.
Examples
A good example of solvable problem is given a number as an input, we have to determine whether the number is divisible by 3 or not. This is a solvable problem.
Another example is, given a code we have to find out if it is Python code. This is also a solvable problem. The solution is what we call compilers.
Now one example of an unsolvable problem is, given a program, can we find out if the program will be stuck in an infinite loop. It may sound simple, but we cannot solve this problem, hence it's an unsolvable problem.
What do we do in Theory of Computation?
In the subject of Theory of Computation, we design systems based on some rules, that takes an input, and gives the output as either yes or no. Yes, means the problem can be solved, no means the problem cannot be solved.
Now among these systems, there are different layers:
Finite State Machine (FSM) is the simplest model of Computation.
Context-Free Language (CFL) is a level-above FSM. Langauge in CFL is not a Programming language, it is more like our real languages.
Turing Machine is a powerful Computational Model. We may have heard about it many times in the context of AI.
Undecided is our unsolvable problems.
Conclusion
This is Theory of Computation in brief. In the upcoming Blogs we'll delve deeper into it.
Top comments (0)