Self-referential Proofs and Paradoxes

Please follow the materials within the syllabus as closely as possible, please dont use materials that are above this class. If you have any questions feel free to email me  here are other topics if you want to do them instead the one i chose that is fine with me as well 1) Choose a mathematical problem from one of these lists: https://en.wikipedia.org/wiki/List_of_NP-complete_problems https://en.wikipedia.org/wiki/List_of_PSPACE-complete_problems https://en.wikipedia.org/wiki/List_of_undecidable_problems https://en.wikipedia.org/wiki/EXPTIME https://en.wikipedia.org/wiki/EXPSPACE https://en.wikipedia.org/wiki/RE_(complexity)#RE-complete Or find some other mathematical problem you’re interested in that’s in a complexity class higher than P. Then, describe the problem mathematically and also in your own words, and describe the complexity class it’s in. For “complete” problems, prove its completeness. Showing a problem is NP-complete, for example, generally involves two steps: first, show it’s in NP; then, show some known NP-complete problem reduces to it. Some of the proofs and reductions you come across may be very complex, so you may need to just outline the reduction as best you can, rather than explaining it fully. 2) Pick a complexity class. Discuss the class, its canonical problems, and its relations to other classes. This one is a little more free-form, so you’ll have to figure out what to write about. Or you can focus on 2 classes with a subset/superset relation, describe them and their canonical problems, and prove the subset/superset relation. 3) If you’re interested in compilers and/or parsing, you can pick a parsing algorithm from here: https://dzone.com/articles/a-guide-to-parsing-algorithms-and-technology-part-3 and write your paper on that, analyzing its strengths and weaknesses, and explaining the algorithm. These algorithms should be understandable at your level, so I would expect a more thorough explanation and not just an outline. If the entire algorithm is too much to fit in the paper, find some part you can focus on. 4) Other options if you want to tackle them could be writing about decidability and unsolvable problems, including the Church-Turing thesis, lambda calculus, Godel’s incompleteness theorem, etc. Or possibly the equivalence of Turing machines and non-deterministic Turing machines, or self-referential proofs and paradoxes. These are very abstract and conceptually difficult topics, so if you’re interested in more advanced computer theory, formal logic, or philosophy, these topics might be interesting. 5) If you want to write a paper that goes further into the P vs. NP problem that I discussed in my P vs. NP video, that’s also a possibility. https://en.wikipedia.org/wiki/P_versus_NP_problem 6) You can write a paper on the proof of undecidability of any of the undecidable properties of context-free, context-sensitive, recursive or RE languages, provided the proof is substantial enough for this paper.