Math 29 Presentation Ideas and Information
The point of the presentations is to augment the class material with additional topics that build on what we've learned or explore related aspects of the area. There will be two components, written and oral. I'd like everyone to give a 25-30 minute class presentation, either on the blackboard or with slides, and put together a more detailed write-up to hand in. The bulk of the 50 points will be for the write-up. I do not expect you to solve an open problem for this, so references to open problems below are to presenting/explaining open problems.
Since this is a quarter of your non-exam points, I want it to be fairly in-depth. You should find a minimum of three references for the topic (so the references suggested below are just starting points).
Finally, remember these are just suggestions (and they will be augmented as the term progresses). If you would like to do a topic not on this list, just clear it with me and you're good to go!
| Module | Topic | Description/Suggestions |
|---|---|---|
| 1 | Bounds on Turing machines | Can bound computation time and/or space, say by a polynomial function of the input size. Discuss some of this theory. |
| 1 | Two-state Turing machines | Describe how a two-state TM is as powerful as a general TM. Might need augmentation with other TM equivalences depending on how involved it is. |
| 1, 2 | Other models of computation | Examples: lambda calculus, abacus machines, Post and Markov computability. |
| Lambda calculus reference: Alonzo Church, "An Unsolvable Problem of Elementary Number Theory", American Journal of Mathematics Apr 1936 | ||
| Abacus machine reference: "Computability and Logic", Boolos, Burgess, and Jeffrey, 4th edition chapter 5 | ||
| Post/Markov reference: Cutland 3.5 | ||
| c.e. sets | Post's Program | Trying to find a "complement-thinness" property that guarantees incompleteness: simple, hypersimple, hyperhypersimple, maximal. |
| c.e. sets | Strong reducibilities | Non-Turing ways to compare sets: truth table, weak truth table, many-one, one-to-one. |
| c.e. sets | Lattice theory | Additional results and open problems on the Turing degrees or c.e. degrees. |
| randomness | Different randomness definitions | Look at one or more different kinds of randomness, such as computable randomness, Schnorr randomness, or weak randomness. Compare to 1-randomness (our standard) and present any open problems you can find. |
| randomness | Information theory | Relationship between Shannon's "information entropy" (very important in coding theory and cryptography) and Kolmogorov complexity as measures of the information content of a string; places where they fail to line up. |
| randomness | Logical depth | A string may carry a lot of information but be dense with it, so redundancies/patterns are minimized. An effort to define this concept of "logical depth" is ongoing: anything totally regular like a crystal or totally chaotic like a gas is not deep; such strings lie in-between. |
Back to the main 29 page.