Theory of Computation

The theory of computation deals with Computer Science in regards of the solvability of the problem; how efficiently, time and space-wise, a problem might be solved on computers using algorithms. The theory of computation has three subfields: Automata theory, Computability theory and Computational complexity theory. Automata theory deals with the problems that can be solved using them, it consists of a finite set of loops, which iterate the input more than several times and thus produce the output. Computability theory deals with figuring out the complexity of a provable solution instead of on the proving of an unknown one. Lastly, computational complexity theory deals with figuring out how long the program will take, memory-wise and time-wise, how long a problem will take if we make it bigger and such. Theory of computation does not only deal with these though, it is also concerned with finding relationships and connections between seemingly unrelated problems, making new secure algorithms for currently unsolvable problems, and testing current algorithms for parallelisms, randomness, fault tolerance and etc.


How do people come up with new algorithms?

How are current algorithms tested?

What are the limitations of algorithms?

Link 1 Link 2 Link 3 Link 4