I recently finished CIS 2620: “Automata, Computability, and Complexity”. It is a staple of Penn’s CS curriculum. The course is theory-first and problem sets are completed through formal mathematical proofs, not coding assignments. If I were to summarize the essence of the course from a 30,000-foot view, CIS 2620 is the study of computation.

Here is a basic outline of the course:

1. Finite automata (DFA and NFAs)
2. Regular languages
3. Turing machines
4. Recursively enumerability and decidability
5. Reductions
6. P, NP, and NP-completeness

Finite automata and regular languages

Deterministic Finite Automaton (DFAs) describe a stateful process by which some function $\delta$ is applied recursively on an input until it halts. We hold on to a single state $q$ which is continually updated.

By coupling certain states with meaning, we can answer questions like “does input $x$ contain substring ‘aa’?”. Basically, DFAs give us formal notation for finding answers to basic questions (these questions are called regular languages).

Turing machines

With DFAs, the possible states we could enter were fixed. What if we want an unbounded number of states? This is useful when we need some flexible memory (keeping track of which states the program has already encountered).

We do this by introducing a tape (a list of input symbols) of unbounded length. We need a few more tools to navigate this tape: a head that points to a location in the tape, ways to define movement of the head, ways to append to the tape, etc. DFAs plus unbounded memory is the basic structure of a Turing machine (TM).

With TMs we can answer more questions than we could before. Consider a question like “is string $x$ a palindrome?”. You could not do this with a fixed number of states in a DFA. How would you keep track of which symbols the process has already seen? You can now answer this question (and others) with a TM. The class of questions TMs can solve is called recursively enumerable.

More machines?

So, what’s the next machine to build? I had the same question.

Here’s Turing’s real genius: you don’t need one. You don’t get to answer any more questions by creating a new machine with more complicated machinery. Any machine you could build has the same power as a TM.

Getting from an input to an output through a series of steps is called an algorithm or a program. You can enumerate all mappings of a computable function through an algorithm. You can run this algorithm on a TM (or any machine with equivalent power).

Philosophical implications

I have encountered the idea of computation many times.

• Mind is computational. (Minsky)
• All languages are computational. (Chomsky, Wittgenstein, Pinker)
• Organic cells are computational. (Levin)
• The universe is computational.

I can deduce what computational means from these use cases and my background in coding. This is good but does not give me a formal notion of computation.

CIS 2620 was the formal approach I needed. We can use the basic structure of automaton to build a new structure called a computer (or a machine, or a program, or an algorithm). We have symbols and operators to define computers which is useful. It means we can study them well.

For something to be computational means it can be run on a computer.

Other connections

I found the last part of the course on P/NP cool but mostly practical. Why do I care about polynomial time? The hard line drawn between polynomial and exponential time is philosophically arbitrary but useful.

I do think undecidability is cool; to mean it means we can’t find a master computer that can deduce what a program does. The only way to really understand a program is to run it. Is this the “computational irreducibility” that Stephen Wolfram can’t stop talking about?

Taking this course alongside CIS 2400 was a gift because there were philosophical implications from 2400—mainly the idea of representation—that tied together neatly with the idea of computation. I will write more about this when I complete the course.