Writing papers on three hours of sleep and two shots of espresso is hard, but slaving away in Butler has its benefits–Bwog’s got the composition process almost down to a science. To help you through this finals season, here are some helpful guidelines for getting your thesis statement from your brain onto the page. Last time, we offered some help with FroSci and Econ. Next up, a guide to a first-semester Lit Hum paper and a Comp Sci final exam.

Lit Hum

________ (Quote from beginning of Iliad/Agamemnon/Oedipus/Genesis/John). And so begins the _________ (same book), a tale that has _________ (withstood the test of time/captured the hearts of readers/barely kept me awake/been shoved down our throats by old white men). However, the theme of ________ (glory in death/communication/fate/social order/immortality) in ________ (same book) is problematized when _________ (compared/contrasted/stacked one on top of the other like a tower in 209) with the ideas expressed by ________ (different book). Throughout _________ (second book) concepts of _________ (Pick 3: family/epistemology/race/this adorable red panda/gender/identity/love/temporality/coffee/class) emerge and present a separate view of __________ (original topic). ___________ (quote from Book 2). These __________ (number of words/lines/5 Hour energy shots it took to deliver the last quote) spell ruin for ___________ (Homeric values/patriarchy/self-determination/the theodicy/my GPA). The ________(Book 1) is a text that is powerful in its depictions of ________ (warfare/social structure/power dynamics/human nature), yet it fails to address the issues raised by _________ (Book 2). This sentiment is perhaps most effectively illustrated by the stark differences between __________ (throw Book 1 in the air and write whatever page it opens to) and ________ (Repeat for Book 2/check out this cute baby sloth).

Comp Sci

Let L_x = {[M,x]: M writes an x at some point, when started on blank input}. Prove that L_x is undecidable using a Turing reduction.

Shit, I knew one of these would be on the final. Okay, I think this is that thing where you like make a Turing machine in a Turing machine and then somehow it decides itself. Well shit, I never did figure out how to do these. Well, I know the first line:

We suppose that L_x is decidable. Now, let R be a Turing machine deciding L_x. We will construct a Turing machine, S, that decides A_TM.

Phew, that wasn’t so bad. Now for the hard part: actually doing it. We’re making R, right? No, dammit, I think we’re making S. Okay we’re definitely making S. Which like has R inside it. Yeah, that’s it. Okay, so now we say how to build S. Here we go: 

Construct S as follows:

Input is [M,w], where M is the code for a Turing Machine and w is a string.

Well fuck, now what? I just introduced a new Turing Machine. Can this be right even? Oh well, can’t stop now. Wait, so M is the one that decides ATM…nope, that’s S. Ohhhh, M runs R on stuff! …I thought S did that though? Now I just have a Turing Machine in my Turing Machine doing the thing that my outer one was supposed to do. Ehh. Better keep writing.

Construct the code for a new Turing machine M_W as follows:

On input y (which will be ignored)

I think usually in class examples it gets ignored, but also I don’t know what the fuck I would do with it anyway. Okay, now we just run one of those other guys on this string w, right? This feels almost familiar. Which one though? Can’t be R, so let’s do M, since that guy is still floating around and hasn’t been used.

Simulate M on w

Wait, that was too simple. What is this problem even about? Oh, finding X’s or some shit. Okay, then we gotta do something with x’s on the input string. Which input string? FIVE MINUTES LEFT ARE YOU KIDDING!? Ummmmmmm. Fuck. Okay, let’s make something up. Uhhh, how about every time we see an x, we accept? Wait, but we’re running M_W right? Or M? I forget. IS THERE A DIFFERENCE? WHY DID I MAKE ALL THESE STUPID MACHINES?  Would there be x’s on w? Probably not. Let’s just have M do whatever the fuck Mw does since I think they’re the same anyway and this final is BULLSHIT.

If M rejects w, reject.
If M accepts w, accept.

Wait, still too easy. Gotta make it look like I tried somehow. I know, let’s print some x’s or something. Try this:

If M accepts w, print an x and accept.

Yeah, that looks good. Now there’s an x in there. Which is what we’ve been looking for all along? CRAP ONE MINUTE. Okay now I gotta end this. How? Oh yeah, run that other Turing Machine…

Run R on M.

Is that the right one? Maybe. I don’t know anymore. I DON’T KNOW ANYTHING. WHAT HAVE I LEARNED? WHERE AM I? MUST KEEP WRITING.

If R accepts, accept. If R rejects, reject.

There, that looks pretty final. Okay, now I just gotta be like “look it was sooooo right.”

So If M accepts w, then Mw will print x. If M rejects w or loops on w, then Mw won’t print x. So R will accept exactly when M accepts w. Therefore, S decides A_TM, but we know that A_TM is undecidable, so S can’t exist and L_x must have been undecidable.

Well that was completely wrong. Fuck this shit. I’m going to happy hour.