Saturday, September 20, 2014

A proof of Löb's theorem in Haskell

I just wrote a post about programming on LW: A proof of Löb's theorem in Haskell. There's some discussion there, and also in these two threads on /r/haskell. Many thanks to gelisam, who deserves at least as much credit as I do :-)

Wednesday, September 10, 2014

Even after all these years, writing quines still feels like I'm hacking the universe somehow

Quine's paradox is fascinating:
"Yields falsehood when preceded by its quotation" yields falsehood when preceded by its quotation.
It's a variant of the liar paradox "this sentence is false", but doesn't use explicit self-reference anywhere, only simple text substitution! That reflects the fact that you can write a quine in any programming language, and a program doesn't need any special "self-referential instructions" to print its own source code.

I just made a simple generator for English sentences that are similar to Quine's paradox. Given an input like this:
I believe in the sentence X
The generator assumes that X stands for "this sentence", and gives you an equivalent sentence without explicit self-reference:
I believe in the sentence "I believe in the sentence X, with the first X replaced by the previous quoted sentence", with the first X replaced by the previous quoted sentence.
Or it could take an input like this:
I don't think X means what you think it means
And give you this:
I don't think "I don't think X, with the first X replaced by the previous quoted sentence, means what you think it means", with the first X replaced by the previous quoted sentence, means what you think it means.
See?

Here's the JavaScript code for the generator, it's very simple:

function quine(phrase) {
  if (phrase.split("X").length != 2) {
    throw "Input phrase must contain exactly one occurrence of X";
  }
  var inner = phrase.replace(
    "X",
    "X, with the first X replaced by the previous quoted sentence" +
    ((phrase.indexOf("X ") == -1) ? "" : ","));
  return inner.replace("X", "\"" + inner + "\"") + ".";
}

Saturday, September 6, 2014

Cylinders in Spheres, Revisited

A couple months ago, a post called Cylinders in Spheres made the rounds on HN. It asks the question "what's the biggest cylinder that can fit inside a sphere?", and then solves it by doing a whole bunch of equations. I'm not satisfied with that solution, because in truth you can solve the problem by using geometrical imagination alone. You can do it in your head, in five minutes. Here's how:

1) Imagine a square inscribed in a circle. It's easy to see that the area of the square has a constant ratio to the area of the circle, regardless of the size of the circle. If we project out that shape into the 3rd dimension, we see that the volume of a cylinder has a constant ratio to the volume of a box inside the cylinder.

2) That means the biggest cylinder that fits inside a sphere corresponds to the biggest box that can fit inside a sphere. We just need to figure out how that box looks like.  From symmetry, it seems likely that the box must be a cube. But how do we prove that?

3) Let's tackle a simpler problem first. What's the biggest rectangle that can fit inside a circle? From symmetry, it's got to be a square, but how do we prove that? Well, the rectangle's diagonal is the diameter of the circle, and cuts the rectangle into two equal triangles. The area of a triangle is proportional to the product of base and height, so the area is maximized when the height is maximized. The height is maximized if the triangle touches the top of the half-circle arc, so we see that the rectangle with maximum area is indeed a square.

4) Now it's easy to tackle the problem with the sphere and the box. If the base of the box is a non-square rectangle, we can note that it's inscribed in a certain circle. We can change it to a square inscribed in the same circle, without affecting the height of the box, and thus increase the volume. That means if the box already has maximum volume, two of its dimensions must be equal. Since we can do the same with every pair of dimensions, we see that all three are equal. Our intuitions were right, the biggest box that fits inside a sphere is a cube! And the biggest cylinder is the cylinder that's wrapped around that cube.

5) For the finishing touch, let's mentally calculate the cylinder's volume. If the sphere has radius 1, the inscribed cube has vertices at coordinates ±1/√3, ±1/√3, ±1/√3. That means the cylinder has height 2/√3 and the base is a circle with radius √2/√3, which gives a volume of 4π/3√3. Whee!