EECS 376 - Foundations of Computer Science

This class covered the fundamental mathematics behind computer science, and the concepts that underlie our notions of computability.

Theory of Computation

Our class began by considering what qualified as computation. A number of competing definitions were offered, and we examined the strengths and merits of each, along with what distinguished them from each other.

Finite State Machines

Finite state machines were introduced as a model of computation. We investigated how these machines could solve various problems and identify patterns. We were also given anonymous finite state machines, whose purpose we had to determine from examining the operations they performed.

Turing Machines

Turing machines were introduced next. We learned how such a machine could compute anything that can be expressed in Church's lambda calculus (see Programming Languages for more on this subject), and what implications that had for solving problems on a Turing machine. As with before, given an anonymous Turing machine, we were tasked with evaluating what problem it solved more broadly, and we were asked to simulate execution manually for given inputs.

Decidability and Constructing Deciders

We learned the notion of decidability next, and learned that we could construct a problem such that it was not decidable. We learned this initially through Russel's paradox, which we used to demonstrate that we cannot decide whether a given machine accepts a given input for all machines and inputs. From there, we proceeded with Turing reduction to this language to prove that other languages were not decidable, and eventually proved Rice's theorem that no non-trivial semantic property could be decided more generally.

Polynomial Computability for Decision and Verification (P & NP)

Having considered issues of decidability, we then progressed to whether problems could be decided efficiently. We learned to identify problems in P and NP, and learned how to create proofs demonstrating their existence in the class. We also learned how to use functions to create equivalent problems, for example from boolean satisfiability to vertex covering, that would allow us to create reductions for the purpose of evaluating this. Additionally, we investigated NP Hard and NP Complete problems, created proofs to demonstrate that they belonged in that class, and evaluated the implications of P = NP.

Working Around Intractability

Finally, we worked on dealing with intractability. We used threshold algorithms, 2-approximations, and other strategies to move the problem to a domain we could more easily deal with. We also investigated the value of problems known to be in NP and believed not to be in P. Any of these problems could be useful for encryption or other cybersecurity purposes, as verification with a certificate is simple, but solving the problem is not. This is analogous to decryption with a key compared to breaking the encryption outright; presuming P does not equal NP, we can identify a problem where the latter is much more difficult than the former, which is a valuable property to us.