Final Recap: What Do You Believe, and Why Do You Believe It?

Reading through other SLOGs, I see many, many cases of anxiety, and so it would be remiss for me not to close with some advice sufficiently general that most students can get something out of it.  As someone who has worked with logic and proofs before, it would also be remiss for me not to give some hints as to integrating this knowledge and the accompanying skills (so they don't get forgotten immediately after the final).

But doing it the normal "here is some advice" way would be boring, and that's no good for actually remembering it.  So I'm going to give such sufficiently general advice and integration hints by talking about a variety of fiction and nonfiction reading that I have personally enjoyed and how they are connected to what we've learned.

I hope these selections will satisfy a wide variety of tastes, so there should be something for everyone somewhere in this post.

In our very first lecture, Professor Heap talked about ambiguity in English and the importance of precision when doing logical reasoning.  Last month I found a nonfiction post largely about ambiguity, precision, and reasoning applied to everyday life on the blog of someone who frequently combines careful logical reasoning and strong scientific evidence with hilarity.  I recommend you read the whole post to get a feel for how this works outside the classroom.

A quote from early in the post to illustrate said hilarity:

Remember, Jonathan Haidt and his team hypnotized people to have strong disgust reactions to the word “often”, and then tried to hold in their laughter when people in the lab came up with convoluted yet plausible-sounding arguments against any policy they proposed that included the word “often” in the description. 

I’ve never heard of the experiment being done the opposite way, but it sounds like the sort of thing that might work. Hypnotize someone to have a very positive reaction to the word “often” (for most hilarious results, have it give people an orgasm). “Do you think governments should raise taxes more often?” “Yes. Yes yes YES YES OH GOD YES!”

For those who want some fictional entertainment, there's Harry Potter and the Methods of Rationality (warning: very long), which combines elements of so many different genres that it's very hard to pin down a genre classification for it other than "rationalist fiction" (warning: TVTropes).  Since it's so long I'd advise reading it after your final exams are over, and so I'll pick out a quote that gives sufficiently general advice:

"I ask the fundamental question of rationality: Why do you believe what you believe? What do you think you know and how do you think you know it?"

I personally prefer the phrasing "what do you believe, and why do you believe it?" in some situations, but either version is a good question to ask yourself both in life and in proofs.  It's about checking if (and how) your beliefs are justified by reasoning and evidence, which is helpful whether that reasoning is written out on the final or for yourself.

There's also a fantasy romance novel called Luminosity in the genre of rationalist fiction; it is similarly too long for me to tell you to read it right away and so I will take the same tactic of quoting sufficiently general advice:

My favorite three questions are, What do I want?, What do I have?, and How can I best use the latter to get the former?

These are also good questions to ask yourself in both life and proofs, and since they're similar to the last set I'll leave reasoning out why as a final exercise.

Good luck on your exams!

Computability and the Halting Problem: Scooping the Loop Snooper

Since we proved the uncomputability of the halting problem in class, I thought I'd share a version of the proof I particularly enjoyed - one written entirely in the poetic style of Dr. Seuss.  It's called "Scooping the Loop Snooper" and it uses the same argument we covered in class.

There's also an extra stanza, which I found here:

Or so you might think… but before you get smug,
There’s one last loop to throw you for, speaking of bugs.
It’s a Turing tape parade so I hate it to rain,
But the whole preceding argument applies to your brain!

Big O and Algorithm Analysis: The Hydra Problem

This time I wanted to present a more challenging problem in an open-ended way; I have a solution but I'm not sure if it's the best solution.

A while ago I stumbled upon the hydra problem, specifically this version.  (Go ahead and read that page now.)

The proof that the hydra will eventually be defeated requires transfinite induction, which we're not covering in this course, but I was curious about defeating the hydra efficiently.  (Let's consider a step to be chopping off a single head, since it's nicely independent of the hydra size and easy to track.)  So I tried my first guess at an efficient algorithm, and then tried the autoplay function.

The results?  Ba gur fnzr fgnegvat ulqen, zl svefg-thrff nytbevguz svavfurq va gjb uhaqerq naq friragl-guerr fgrcf (gurer'f fbzr inevngvba orgjrra ehaf qhr gb gur enaqbzvmngvba bs tebjvat onpx urnqf, ohg vg fgnlf jryy jvguva guvf beqre bs zntavghqr) naq gur nhgbcynl nytbevguz tbg gb bire n zvyyvba fgrcf (gnxvat jryy bire n jrrx!) orsber zl oebjfre penfurq.  (Take a guess first if you want to, then decode the above here.)

Clearly there is a huge difference in efficiency, and the multiple orders of magnitude involved show why efficiency matters.  I haven't done a big-O analysis of this problem, but I suspect the worst-case performance bound would be a function of starting hydra depth h, maximum recursive depth (when growing back from dire necks) r, and maximum copies allowed (when growing back from normal necks) m.

But which algorithms are efficient on this problem?  I invite you to guess; I'll present my solution at the end.

Hints:

1. What could you do to minimize the hydra's ability to grow back?
2. What could you do to maximize the hydra's ability to grow back?  (Pretend that after a while your worst enemy was going to fight it and you wanted to make the fight as hard as possible, if that helps.)
3. Observe the autoplay algorithm.  Are there any moves it makes which help it defeat the hydra quickly?  Are there any moves it makes which make more work for itself?

My solution: Ng rnpu fgrc, pbafvqre bayl gur uvturfg yriry bs urnqf.  Phg nal qver arpxf svefg, sbyybjrq ol abezny arpxf.  Erfbyir gvrf ol phggvat arpxf jvgu gur fznyyrfg ahzore bs fvoyvat arpxf svefg (erphefviryl vs arprffnel).  Vs guvf qbrfa'g erfbyir gur gvr, cvpx ng enaqbz orgjrra gur gvrq arpxf.  (Again, decode here.)

Logical Reasoning: Visualizing the Folding Problem

At the end of the problem-solving session on the folding problem, Professor Heap gave us an additional challenge: to find a way to generate a graphical representation of the folded paper viewed side-on (so that all the creases are visible) for any number of folds.  This post is about my attempt at tackling that problem.

I won't show the code for this, but you could code up a program to generate such visualizations in Python (and maybe have some insights into the problem in the process).  It might be helpful to use a module such as turtle which shows the drawing as it progresses so that you can see what's going on.

Warning: my approach uses my solution to the folding problem itself, so don't read further if you want to solve the problem for yourself without seeing a solution.

A Policy

Since this post has been heavily delayed, it will probably serve more as an example of policies for students helping other students in your future courses. I am posting it nevertheless.

Here is my policy on helping other students in this course:

1. All help must be within the limits allowed by the University's Academic Integrity policies. Questions about assignments will also be limited by the course policy on working together on assignments. If you ask me for help beyond these bounds, you will not get it and will be sorely disappointed.
2. General requests for help (clarification requests, definition questions, pretty much anything not related to a specific attempt to solve a problem) should preferably be directed to Piazza first. (Unless an instructor (including your TA) is around, in which case go ahead and ask them as you normally would.) This is because most students and multiple instructors are checking the Piazza board for this course, so everyone benefits: you get an answer from the first person who can help you and has a chance to give one, everyone who is inclined to help knows where to find unanswered student questions and isn't inundated with requests, and other students can refer to those answers later. (This doesn't mean you can't take them to office hours, tutorials, etc.)
3. I will allow requests to go over attempted solutions to problems (as will professors and the CS Help Center) but you will probably get more out of it if you come to me with a practice problem that isn't being marked (so we can take notes on the discussion, draw things out, etc.). Please don't send attempted solutions to assignment questions to me electronically, as those constitute notes and I would have to delete them unread. Regardless of the problem you bring, I will try to ask questions to help you think about the problem (to encourage learning) rather than giving you the answer.

Ok, so I've worked with proofs and logic before, which makes the course material so far fairly easy.  There's really no point in pretending otherwise.

Other students have also noticed this and started asking me for help rather quickly.  I don't mind helping people, but I do have to limit what I can help with in order to:

• Make sure the students asking for help are actually learning,
• Prevent academic offenses, and
• Avoid being inundated with requests and unable to get to them all.

To this end, I will be posting a detailed policy regarding what I can help with and where requests should be directed.  Until this policy is posted, please use the existing resources available to all students in the course, such as tutorials, office hours, and the course discussion board.