Theoretical Computer Science is domain of Computer Science that looks at the notion of information and about how information can be processed. It also looks at the way models are built in computer science. Common divisions of theoretical computer sciences include:
- Automata theory: An automaton is an abstraction of a machine, which changes its internal state according to some rules. Automata theory also looks at the kinds of problems that can be solved by such automata.
- Computability theory and Computational complexity theory look at the question if a problem can be solved by a given automaton, and how well a given solution is, compared to others.
- Formal languages are the way to communicate with a given automaton. Most of the time, the question is whether the automaton will accept a word of a formal language, that is, when the word is fed into the automaton, the automaton will end up in an exit state. Semantics are used to talk about the grammars of such languages, and how they are constructed.
- Information theory talks about the notion of information. Originally it was developed for signal processing. It is concerned with how a message needs to be changed, so that it can be transmitted over a channel, an how to undo the changes at the other end, so that the original message can be recovered. These processes are known as encoding and decoding. Information theory also talks about how much self-information there is in a message. This is the theoretical basis for data compression, cryptography and digital signatures. Error detection and correction is about detecting if errors have occurred when the message was transmitted. In some cases, it may be possible to recover the original message even if errors have occurred, or part of the message has been lost.
Other domains, such as Logic and Statistics used as well, but in most cases, they are not the primary focus of theoretical computer science.
