What is Theoretical Computer Science?

Article Details
  • Written By: Michael Anissimov
  • Edited By: Niki Foster
  • Last Modified Date: 25 July 2017
  • Copyright Protected:
    Conjecture Corporation
  • Print this Article

Theoretical computer science is largely an abstract mathematical discipline that seeks to better understand the nature of computation. But like research in physics, advances in theoretical computer science end up providing practical contributions to the field of computing in general. The discipline of theoretical computer science can be divided into several subcategories.

The prototypical subcategory of theoretical computer science is the study of abstract complexity, which involves algorithms, automata, complexity, and games. For example, what generalizations can we make about the behavior of certain algorithms as they approach an infinite amount of computing power in the limit? What is the space of possible programs that can be described with less than 50 bits? What statistical methods may be used to determine whether or not a given algorithm or program is performing its task optimally?

Another subcategory of theoretical computer science is logic, semantics, and the theory of programming. This category tends to be a bit more concrete than the above. For example, how can we determine which programming language has an advantage in addressing a given computational problem? How can we use programming languages to write automated theorem provers? How do we validate code as possessing given information-theoretic properties?

A final general category in theoretical computer science is the study of computational processes occurring in nature, and artificial computational processes inspired by nature. For example, evolutionary computing, neural networks, molecular computing, and quantum computing. It attempts to answer questions like: what is going on, computationally, during the process of evolution and natural selection? Is reality itself fundamentally computational? And so on.

Theoretical computer science originated in the 1940s and 50s with geniuses like Jon von Neumann and Alan Turing. Additional goals in theoretical computer science are to unify seemingly separate fields of computing, determine whether or not certain problems are in principle unsolvable, what techniques may be used to factor huge numbers or discover the largest prime numbers, an so on.



Discuss this Article

Post your comments

Post Anonymously


forgot password?