During the semester, you will work on a project in which you will explore a more advanced topic in the theory of computation. The topic of your presentation can go in any number of directions, and should reflect your unique passions and interests, while still being relevant to the course material. 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 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 and/or regular expressions. These machines have applications in compilers and parsers, embedded systems and software, and linguistics; however, you might be surprised by how these machines are useful for 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.
-
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.
-
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.
-
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".
-
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, 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 you believe it is appropriate for this course.
-
Final submission prototype: You will submit a draft of your final proposal, and I will provide feedback on what you need to improve to get full credit. This does not need to be a finished product; however, the more work you put into this, the fewer changes you will have to make for your final submission.
-
Final submisssion: Due at the end of the final week of classes. Your writeup should be at least 2 pages in length (single spaced, 11 point arial font). 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.