Search code examples
programming-languagescomputer-sciencetheorycomplexity-theory

What is the technical definition of theoretical computer science? What subfields are included?


What is the technical definition of theoretical computer science? (Or, what should it be?)

What main subfields does it include, and what is the commonality that separates them from the rest of computer science?

More specifically: if some particular research has direct practical motivations, goals and outcomes but mostly involves very abstract methods, is it theoretical computer science or not?

Two examples to consider:

"Dual quaternions for rigid transformation blending" (Better mathematical representation of rotation and transform for animation) https://www.cs.tcd.ie/publications/tech-reports/reports.06/TCD-CS-2006-46.pdf

"Relational Semantics for Effect-Based Program Transformations with Dynamic Allocation" (Complier optimisation via denotational semantics): http://research.microsoft.com/pubs/67977/ppdprelational.pdf

[The Wikipedia article gives only a vague definition and a long list of subfields. Should just accept that there's no better definition than this? http://en.wikipedia.org/wiki/Theoretical_computer_science ]

EDIT: I guess this question comes down to "What does the term 'theory' mean in the context of computer science?". Looking at the 6 different meanings of the word at wiktionary, I don't think any of them fully fits. I guess the mathematical sense of a theory fits well for completely mathematical fields but not for others, and for VLSI, machine learning and computational biology from wikipedia:TCS it basically doesn't fit.


Solution

  • I think the easiest way to distinguish theory from application is to look at the field's definition of a computer. If work in the field is based on the assumption that a computer is a physical object or system, then it's probably application. On the other hand, if work in the field is based on the assumption that a computer is an abstract (usually mathematical) object, it's probably theory. So, when you decide whether to say you are a theoretical computer scientist, I think you just have to ask yourself, "what is a computer?"

    (For me, it's definitely an abstract object)