Haneen Shariff

Theory of Computation is the branch in Computer Science that is most concerned about as to how are problems solved using an algorithm. These problems are usually solved on a model of computation, which are a mathematical abstraction of computers. Questions arise such as, what problems can be solved on a computer? What problems cannot be solved even if we use more machines?  Theory of computation seeks to provide answers to these questions by forcing us to think in a new way about computation. The most common model of computation that is used is the ‘Turing Machine’. Only a finite amount of memory is required to solve problems using a Turing machine.

There are three categories into which the field ‘Theory of Computation’ is divided.

 

1. Automata Theory – It is the study of the problems that can be solved using abstract mathematical machines. The main function of an Automata Theory is that it takes an input and decides whether or not it should accept it or reject it.

​

 

1. Computability Theory – It determines to what extent can a problem be solved on a computer. It is said that the Turing machine cannot solve the halt problem. The halt problem states that “Given a description of an arbitrary computer program, decide whether the program finishes running or continue to run forever” 

​

 

1. Computer Complexity Theory – This branch of Computational theory deals with whether or not a problem can be solved by a computer and then goes into more depth, how efficiently can this problem be solved? The two aspects that we should keep in mind is time and space, while solving a problem we should be aware about how many steps are involved to perform a computation and also what is the memory that will be needed to solve this computation. A certain problem is considered to be difficult if it takes a lot of resources to get to the Solution, irrespective of which algorithm is being used.

​

Analysis of algorithms and Computability theory are closely linked to the field of computer science. Analysis of algorithm seeks to determine the amount of resources that would be needed by a particular algorithm. Whereas, Computability theory is more concerned about the possible algorithms to solve the same problem.

To sum it all up, Theory of computation is a field that is more concerned about how to solve a particular problem with an algorithm.

 

 

3 Questions

 

1) Why is it that the Halt problem cannot be solved?

2) Does the Halt problem require a highly advanced computer?

3) What is the average memory required to solve complex problems?

 

Want to know more? Check out these links!