“Go down deep enough into anything and you will find Mathematics.” This is exactly what I experienced when I started grad school in Computer Science. I just want to share my incredible journey from Computer Science to Mathematics. I think it is worthwhile to understand how concept of computation and Mathematics are inextricably linked.
People often tend to ignore mathematics while learning Computer Science. You need not be a Mathematician to be a Computer Scientist however every computer scientist or professional must understand the underlying mathematics of computation. It is also very beautiful and fascinating.
In my opinion Computer Science was born when Kurt Godel wrote his proof of Incompleteness theorem in 1931. This is arguably the most important and beautiful result in last 2000 years. This proof has answered the long pursued question by many great thinkers including Greg Cantor. "Is there a theory of everything?". The answer is negative. Godel had proved limits of mathematics using mathematics, limits of science using science. He proved that the concept of "Theory of Everything" of fallacious.
It was not obvious to many people that this deep result will give rise to an extremely promising field that will change the face of the world. This was because Godel's proof was complicated in nature and was based on formal language. In 1936 Alan Turing reformulated Godel's result with the concept of Turing Machine and defined the terms Computation and Algorithm. While the results are same in nature the concept of Algorithm, Computation and Turing Machine are much more graspable than the formal language based proof of Godel. Turing's result presents what is computable and what is not computable. Later on he also proved the undecidability of 'Halting Problem'. Both Godel and Turing were extraordinary mathematicians of the 20th century.
A lot of research in mathematics contributed to the idea of computation. The famous Church-Turing theses states or hypothesized that all the computational models are equivalent to Turing machine. Or putting in other words, the set of computable functions remains same under any computational model. This was a very fundamental and ground breaking result as the concept of computation proved to be independent of the underlying computational model.
After it was proven that the concept of computation had an emmence potential, electric engineering research focused on building computers. It led to successful development of early computers and various research challenges were faced by the newly born computer science community. In my opinion the two research papers stand out in terms of their contribution to Computer Science.
First paper is by Juris Hartmanis and Richard Stearns. They proved the time complexity theorem. Performance of any computer program / software is measured mainly on the basis of its asymptotic running time. The concept of running time is not something that is defined for our convention but it is an intrinsic property of computation. Those who are familiar with the notion of BigOh BigOmega etc, should understand that these concepts are not defined for convention. It emerged as an intrinsic property of the algorithm.
Second major contribution is the Theory of NP-Completeness which is a beautiful theory in itself and also an extremely interesting topic of research.
Theoretical Computer Science looks at these topics in depth. When you start studying Theory, you go in the reverse direction the development of Computer Science. You will never realize when you escaped from computer science and entered the realm of pure mathematics. The borders lines are as thin as soap bubble surface. Computer science in a way is a branch of Mathematics which can be a realized using digital computers.
No comments:
Post a Comment