During the semester, you will work on a project in which you will explore a more advanced topic in the theory of computation, and see how it connects to some of your other classes at Southwestern. The topic of your presentation can go in any number of directions, and it should reflect your unique passions and interests, while still being relevant to the course material. You will also identify paideia connections between the topic you explore and topics you have seen in another non-math/CS class. You will turn in a writeup in which you explain the topic in a way that would be accessible to your fellow classmates (or even your non-math/CS friends). It is very clear to note that the intended audience is not the instructor.
Your report will be graded for completeness, clarity and effort. You should get the main points of your topic across, and you should demonstrate that you engaged with the topic in an active and intellectually curious manner. If you choose a topic that poses a philosophical question, you should also demonstrate that you tried to answer the question in a mathematically rigorous manner using the techniques we have learned about in this course.
Here are some examples of directions you could go with your project:
-
A survey of practical applications of finite automata, regular expressions, context-free grammars, and pushdown automata. These machines have applications in compilers, parsers, and embedded systems and software; however, you might be surprised by how these machines are useful for linguistics, biology, music, and other areas.
-
It is commonly assumed that humans are smarter than computers. Is that actually true? By taking this course, you have developed a vocabulary and mathematical framework to explore this question in a more rigorous manner. You could survey the positions for and against human intelligence being strictly more powerful than Turing machines. You could also study quantum computing, or propose some other form of super-Turing complete computation.
-
What was the first "computer"? Now that you know the definition mathematicians use for the word "computer", you have the means to give a satisfying answer to this question. You could identify the oldest machine that you believe meets all of the criteria to be called a "computer".
-
There have been some surprising Turing-completeness results. For example, DNA itself, Conway's game of life, Wang dominoes, and even Magic: The Gathering have been shown to be Turing complete. You can explore one of these systems, or some other combinatorial object that is (surprisingly) expressive enough to simulate any conceivable Turing machine (and thus, any conceivable computer program).
-
Advanced topics related to Turing's research, such as Lambda calculus, Goedel's incompleteness theorems, and Kolmogorov complexity.
-
We will be focusing on what problems are (un)decidable if we are given infinite resources. But another area of computer science studies what problems we can (and can't) solve given certain resource constraints. The classic example of this is the P vs. NP problem: what problems can be solved using a polynomial runtime? What problems can have solutions verified in polynomial runtime? Are these two categories the same? We will not be covering complexity theory, but you can use your paideia project to explore the topic. Your paideia project cannot simply explore the P vs. NP problem; you must go beyond this. Here are some suggestions:
-
Advanced topics in complexity theory, such as co-NP, PSPACE, Interactive Proof Systems, etc.
-
Several puzzles, such as sudoku and kakuro have been shown to be NP-complete; that is, any algorithm to solve the puzzle will (probably) not scale very well with the size of the puzzle. You can explore the NP-completeness proof for one of these puzzles, or some other problem that you find to be particularly interesting.
-
If a problem is NP-complete, it means that it is highly unlikely that we will ever find an efficient algorithm to solve the problem. This sounds like a bad thing - and in some cases it is. But for cryptographers, this is actually a boon. You could study one problem that is used in crytographic schemes specifically because of (and not in spite of) its inherent intractability.
-
You are also free to propose something in a completely different direction - perhaps a coding project, perhaps even a hardware project. As long as you can justify its relevance for this course and its paideia connections, I am pretty open to any proposal that you feel enthusiastic and passionate about.
The project the following components:
-
Initial proposal: 1-2 paragraphs describing the topic you want to explore, and why. I will provide feedback on whether I believe your proposal is appropriate for this course, and give you suggestions on materials that you can explore.
-
Presentation: The last week of classes will be dedicated towards final project presentations. You will give a 4-5 minute presentation on your topic in a way that is accessible to your classmates. Your presentation should address the following:
-
Introduce the topic that you chose, and explain how it is connected to the material in the course.
-
Describe and summarize your findings in a way that is accessible to your classmates. You don't have to get into all of the technical details - focus on getting the big picture points across.
-
Share one paideia connection - that is, a connection between the material in this course and another course you are taking at Southwestern.
-
Answer any questions that your peers ask to the best of your abilities. Additionally, you will be expected to ask at least one question to one other presenter.
-
Final submisssion: Due at the end of the final week of classes. Your writeup should be at least 2 pages in length; it should single spaced, 11 point font, and written in either Arial (the default font on Google Docs), Times New Roman, or Computer Modern (the default font on Overleaf). Your writeup should contain the following:
-
Introduce the topic or question you are exploring.
-
Explain what drew you to this particular topic.
-
Explain why the topic is related to the this course.
-
Document your explorations and findings.
-
Explain what paideia connections you found between the topic you researched and material from one of your other courses at Southwestern. You should have at least two paideia connections, and for full credit at least one of those connections should be to a non-Math/CS course.
-
Cite all of your sources! That said, your bibliography will not count towards your 2 page minimum. If you decide to use LaTeX, feel free to reach out for help on how to manage citations - you will be pleasantly surprised to see just how convenient this process is in LaTeX! For full credit, I expect you to reference and cite at least two academic sources.
-
Figures are allowed and encouraged - but please make sure your writeup is at least two pages of text.
-
If applicable, you should also submit any code, and/or a video of a demonstration of your hardware/software.
The idea for this course component was borrowed from Dr. David Chiang's
theory of computation course at Notre Dame.