We’re about to start up the Fall semester, so it seems like a good time to be updating Wombat for the new semester. With that, a whole slew of bugs have been squashed:
We’re about to start up the Fall semester, so it seems like a good time to be updating Wombat for the new semester. With that, a whole slew of bugs have been squashed:
Something was bugging me about my proof from yesterday. If we take another tack on proving Turing completeness, all we would have to prove is that we can simulate SUBLEQ. Since SUBLEQ is Turing complete, that’s all we need–just convert each SUBLEQ into a SUB, JZ, and a JLS. So that means that Tiny as written should be Turing complete.
So how does that work?
Today’s challenge at /r/dailyprogrammer asks to implement an assembler for a small virtual machine. It has only 16 mnemonics which in unique opcodes (each instruction can have multiple forms for if they’re accessing memory or literals), so it’s a simple virtual machine indeed. As a challenge, you’re supposed to write an interesting program (I actually wrote a virtual machine as well to test them). As an even better challenge, we’re supposed to prove that Tiny is Turing complete. Well, let’s get to it!
In my research, I work with a lot of rather large text files–on the order of gigabytes if not terabytes per file. Since they’re plain text, they’re generally rather compressible though, so it makes sense to gzip them while they’re on disk. The drawback though comes when you’re working with them. There are a few options though.
So far, we’ve had three different ideas for figuring out the author of an unknown paper (top n word ordering in Part 1 and stop word frequency / 4-grams in Part 2). Here’s something interesting though from the comments on the Programming Praxis post:
Globules said July 19, 2013 at 12:29 PM Patrick Juola has a guest post on Language Log describing the approach he took.
Last time, we used word rank to try to figure out who could possibly have written Cuckoo’s calling. It didn’t work out so well, but we at least have a nice framework in place. So perhaps we can try a few more ways of turning entire novels into a few numbers.
About two weeks ago, the new crime fiction novel Cuckoo’s Calling was revealed to have actually been written by J.K. Rowling under the pseudonym Robert Galbraith. What’s interesting is exactly how they came to that conclusion. Here’s a quote from Time magazine (via Programming Praxis):
Two Programming Praxis puzzles in a week? Madness! Let’s do it!
This time, the puzzle at first seems rather minimal:
Write a function f so that f(f(n)) = -n for all integers n.
If you haven’t seen this problem before, take a moment to think though it. It’s a neat little problem–a close cousin to a lateral thinking puzzle.
It’s been rather a while since I’ve worked out a Programming Praxis problem, but they posted a new one yesterday, so now seems as good a time as any. The problem is relatively simple:
Given a linked list, swap the kth node from the head of the list with the kth node from the end of the list.
Since all lists in Scheme are linked lists, that part seems easy enough. To make the problem a little more interesting however, I’m going to work it out in a purely functional manner: no mutation.
Last Thursday I wrote a post about generating Perlin/simplex noise in Racket. Later that day, I posted to the Racket mailing list asking how I could make it faster. What resulted was a whole sequence of responses (primarily about Typed Racket) and a bit of a rabbit hole that I’m still trying to wrap my head around.