Computer Science Courses You Missed (Part 3: Complexity & Computation)

This is Part 3 of a sequence (Part 1 and Part 2 are relevant, though they are not prerequisites). Here, I explain why it is important to understand the nature of computation the way it is implemented in modern computers and provide some pointers in case you are interested in learning more.

Most programmers understand regular expressions and state machines intuitively, but only a relatively small fraction of them have the understanding needed to reason about the limitations of these tools.

Can you use a regular expression to check proper nesting of parentheses? (E.g. determine that "( ( ) ) ( ( ( ) ( ( ) ) ) )" is valid while "( ( ( ) ) " is not, for arbitrarily long inputs.) How much do deterministic (easy to turn into code) and non-deterministic (harder to turn into code) state machines differ? This is the sort of topics that the first part of "Introduction to the Theory of Computation" covers and it will be well worth your time.

It is hard to be a versatile software engineer without understanding the limitations of the languages you work with, and regular expressions and finite automata are among the simplest "languages" in day to day use; from there, you go to stack machines and beyond. Cement your understanding by doing some independent research on compilers (for example, consider this random course handout that you get from a Google search for "compilers context free C").

It gets better: there is fascinating, and not too difficult to grasp, theory behind what computers (as well as mathematical formulas) can and can not compute. Not everything is possible, even with an infinite tape! (An inside joke that you will understand once you learn about Turing machines and the halting problem.)

Computability is the subject of the second part of Sipser's book. Some of that material is very relevant to #cybersecurity professionals because it has implications about what is practically achievable when evaluating programs via automation (think: static analysis, emulation, and malware analysis).

Finally, the section on Complexity ties back nicely into what you may have already learned from your reading and practice in Algorithms: no better way to master a concept than approaching it from multiple angles. Happy Computing!