Theory Of Computation

Theory of Computation is most important theoretical subject taught in Bachelor level Computer Science/Engineering in many Universities around the world.

The core design of computer relies on how it is made to identify the input to be right or wrong. Once this identification/classification between correct and incorrect is established, the computer becomes an intelligent machine. What languages can we make a simple computer to identify? How much memory will we need to do this? Can a computer made to identify more complex languages? Can all the problems given to a computer be solved? What are the problems that computer wont be able to solve? What are the parameters that make a problem solvable or unsolvable? These are the questions addressed in this subject.

The first theoretical computer was proposed ( which obviously worked using paper-pencil) in the years as early as 1936. Alan Turing; after whom the reputed Turing Award is awarded every year to most important contributor in the field of Computer Science, was the computer scientist who proposed this machine and related theories.