The study of the theory of computation is equal parts computer science and pure mathematics. As such, we will need to put on our mathematicians’ hats to understand the course material. Today, we review the basics of mathematical literacy, the ability to read and write mathematical prose.
To prepare, read through §0 (Introduction) of our required textbook, Introduction to the Theory of Computation by Michael Sipser, for an overview of the field of the theory of computation as well as a review of the background mathematics for the course. Pay special attention to the section in §0.2 (Strings and Languages) for the definitions of strings and languages, a core concept in this course that you will have likely not encountered in a formal setting.
In addition, I recommend spending time getting your mathematical writing software setup. In the past, I’ve used LaTeX for this course, but because of the sheer badness of the tooling support, I have begun to use Markdown with sufficient extensions to typeset mathematics in my own work. You can use either for this course, but please be mindful that your writing tools don’t get in the way of your learning!
If you choose to use Markdown, there are a variety of tools that you can use, e.g., HackMD is the Overleaf-equivalent for Markdown-with-Math, but any Markdown setup that allows you to typeset mathematics and render to PDF will work.