CS 125 - Computability and Complexity

0001 January 1

![banner]({{ site.url }}{{ site.baseurl }}/assets/utm-manchester-22.jpg){:class=“img-responsive”}

I am teaching assistant for CS 125 — Computability and Complexity — fall semester 2019. I took this class in spring of 2015 with Prof Skalka and enjoyed it very much!

Here is a link to Prof Ling’s course page and to Webber’s page for Formal Language.

Office hours for CS 125 are

  • Monday, 8:30 AM - 9:30 AM
  • Tuesday, 10:00 AM - 11:00 AM
  • Wednesday, 11:00 AM - 12:00 noon
  • Wednesday, 2:00 PM - 3:00 PM (Filip Saulean)

or by appointment. My office is E332 Innovation Hall, but office hours will be in E338, the common area immediately outside E332.

Please feel free to email with questions to clayton dot cafiero at (you know the rest)!

Topics - Formal languages and expressiveness. Chomsky hierarchy. Finite automata. Turing completeness and Church’s Thesis. Decidability and tractability. Complexity classes and theory of NP completeness. Prerequisites: CS 064 or MATH 052. Co-requisite: CS 124.

About the image - The image above is a detail from Roman Verostko’s Manchester Illuminated Universal Turing Machine, #23. The work was executed in 1998, and is a 30" by 22" pen-plotted drawing with gold leaf. It resides in the St Vincent Archabbey and College Legacy Collection, in Latrobe, PA. Verostko works in the intersection of visual arts and computer science. For more information, visit his website. Versostko’s work was featured in [Art by the Numbers]({{ site.url }}{{ site.baseurl }}/assets/pdf/ornes_2018.pdf), by Stephen Ornes, Scientific American, August 2018, Vol. 319(2), p. 68(6).