What exactly is theoretical computer science? Is it learning to code in various language and making apps in platforms? Or is it just thinking about faster and faster algorithms so that you can achieve a task more efficiently by the computers? Or is it programming and thinking of new life situations which can be simulated on a computer? What exactly are we trying to do here ?

For example, physics is trying to find all the laws of nature that govern it; mathematics is a tautology based to model reality and used as a very precise language by other subjects.

What exactly is theoretical computer science? When computers were designed by us humans for application purposes, hence it must all drop down to mathematics and physics in the end? Then where is the "theory" in computer science itself.

Sorry for being too naive but I want to know what does a theoretical computer scientist do ?

  • 5
    $\begingroup$ en.wikipedia.org/wiki/Theoretical_computer_science ... The field of theoretical computer science is interpreted broadly so as to include algorithms, data structures, computational complexity theory, distributed computation, parallel computation, VLSI, machine learning, computational biology, computational geometry, information theory, cryptography, quantum computation, computational number theory and algebra, program semantics and verification, automata theory, and the study of randomness ... $\endgroup$ – Marzio De Biasi Nov 3 '13 at 19:35
  • 1
    $\begingroup$ See help center. $\endgroup$ – Kaveh Nov 3 '13 at 19:42
  • 6
    $\begingroup$ Q. "What exactly are we trying to do here ?" A: "Follow a passion" :-D :-D $\endgroup$ – Marzio De Biasi Nov 3 '13 at 19:50
  • 8
    $\begingroup$ we study computation, not computers. this is mathematics, but it is mathematics that we only recently started studying. the mathematical theory of computation is not necessarily tied to specific real-world realization; it does not reduce to physics, because it is independent of the "real world". it has, however, the potential of being a language for sciences $\endgroup$ – Sasho Nikolov Nov 3 '13 at 19:52
  • 1
    $\begingroup$ It is widely accepted that "computer science" is a misnomer. To paraphrase Dijkstra: "Referring to this field as computer science is like referring to surgery as knife science" or, I sometimes add, referring to astronomy as telescope science. --- "Computation science" might be closer to the truth, but that still doesn't quite cover the field. In the Netherlands we call it "informatica", i.e., "information science". --- There is obviously some overlap with mathematics. Especially discrete mathematics. $\endgroup$ – mhelvens Nov 3 '13 at 20:01

Your question itself is not naive but the type of answer you ask for is. It is rare for any line of work or intellectual enquiry to have an elevator pitch explanation. Not all would agree with your characterizations of mathematics and physics because they ignore the depth and nuances of those fields.

Theoretical computer scientists are concerned with studying and applying computation. The computational perspective is a deep and all encompassing one so the study of computation is also deep and has a bearing on many other areas of study. Every single process, whether arising in nature or synthetic, manipulates information. They compute. As in mathematics, there are different languages and types of structures involved in computation, as in physics, there are fundamental laws about computation that we are trying to discover, as in chemistry, fundamental elements of computation can be classified. Theoretical computer science is broad and robust enough to be amenable to any perspective you bring to it. Some of the questions studied are:

  • What is computation and how can it be characterized? (Turing machines, lambda calculi, tiling systems, register machines, DNA computers etc.)
  • What is the computational model underlying a process? (Biological, chemical, economic, sociological processes, etc.)
  • What is efficient computation? (complexity via time, space, communication, amortized, smoothed, etc.)
  • What are characterizations of efficient computation? (Turing machines, algebraic notions, logic, type systems, etc.)
  • What is the most efficient way to compute a solution to a problem? (algorithms)
  • How efficient are existing algorithmic processes (analysis of algorithms, statistical phenomena, market equillibria, etc.)

These are a small and non-representative sample of the questions that one may ask. As in any field, answers to some questions generate new questions and drive enquiry about other questions. You can find a rather dated view of the field by browsing the articles in the Handbook of Theoretical Computer Science.

  1. Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity, 1990
  2. Handbook of Theoretical Computer Science, Volume B: Formal Models and Sematics, 1990

For a rough answer, if you are new to TCS you can probably think of it as a sub-area of mathematics: Theoretical computer science consists mainly of proving theorems.

If you want a contrast with standard "mathematics", TCS is (I think) primarily algorithmic: Focusing on the design, analysis, and theoretical capabilities/limitations of algorithms.

Computer science can also be experimental, i.e. a natural science like physics or biology, but this tends to more often fall outside the realm of "theory".


Your Answer

