God Plays Dice

T. V. Raman, a blind computer scientist who was trained as a mathematician, writes Thinking Of Mathematics —An Essay On Eyes-free Computing.

I think that even sighted mathematicians will get something from this, because the main issues for a visually impaired mathematician are that they cannot read or write in the usual way, and many of us do work in a situation where reading or writing is not available to us. Much of my best work gets done while walking to or from school, which is why I refuse to take SEPTA even though it would be faster. Plus, I get exercise that way. I've often taken to calling my own cell phone and dictating the solution to a problem into my voice mail. But this clearly isn't the same thing, because in the end I write things up in the traditional way.

Not surprisingly, Raman seems to find that the largest difficulties come in trying to communicate with other mathematicians, although this is becoming less of an issue as mathematics moves online, especially with the proliferation of TeX. (But this raises a question for me: often I write TeX that isn't strictly correct, but compiles anyway, and gives the right output on the page. How do systems like Raman's AS TE R (Audio System for TEchnical Readings, his Ph. D. thesis) handle this?

"Open Source 'Sage' Takes Aim at High End Math Software", from Slashdot. (The actual site, sagemath.org, is Slashdotted right now.) Here's the article that Slashdot links to (by the way, the links in that article go to malformed URLs, but they're not hard to fix). The leader of the Sage project is William Stein, who with David Joyner wrote an opinion piece in November's Notices stating that mathematical software should be open source. From what I can tell, SAGE includes both new code written specifically for the project and a lot of old code that's been previously used (it appears to incorporate Maxima, GAP, etc.)

I agree with this; although it may very rarely be practical to check all the work that goes into establishing a mathematical result, it should always be at least theoretically possible. It seems acceptable for the internal workings of mathematical software to be closed when it's just students that are using it, or when the serious researchers are just using it to do experiments. But as we start seeing more and more proofs which reduce to "so I reduced the problem to some finite but very long computation, and then I ran this program, and it said my theorem is true!", it becomes more important that someone can actually verify that the program does what the author claims it does. For comparison, see Wolfram on why you don't need to know what's going on inside Mathematica, which is mildly amusing.

I haven't actually used SAGE, but it certainly seems more in line with the open-information ethos of the mathematical community than the proprietary software that's out there. It's a shame I know Maple pretty well, because that creates a disincentive for me to switch if I wanted to.

From Chris Lomont: An Analysis of the Excel 2007 "65535" bug. (This is the bug that made certain floating-point calculations with results near 65535 or 65536 appear as 100000 or 100001.)

Towards the end, Lomont writes:

[A]n amazing number of people guessed the bug had something to do with the 65536 row limit, showing the flaws in belief in numerology.

Um, it's a power of 2? Somehow it's not surprising that powers of 2 occur in a lot of distinct places with binary computers. (Hence the "correlation is not causation" tag on this entry -- the number of rows didn't cause the bug, nor vice versa, but both were caused by the fact that the internal architecture of the computer is binary.)

From The Geomblog: "Made in the USA" can be Revitalized, in yesterday's San Jose Mercury-News, by Ken Goldberg and Vijay Kumar.

As Suresh puts it, they want to Put the Turing in Manufac-turing" -- to bring manufacturing to a higher level of abstraction, so that manufacturing processes can be understood independent of the particular substrate they lie on.

Eventually figuring out how to manufacture things could become another branch of the analysis of algorithms. And even if it doesn't, thinking at a higher level of abstraction might enable people to conceptualize more complex manufacturing processes -- and manufacturing processes will become more complex in the future.

Finally, it doesn't seem surprising that this article was published in San Jose -- the city that perhaps more than any other was transformed by the abstraction of computing.

p. s. The simplest possible Turing machine is actually universal.

Here's a problem from Feynman Lectures on Computation (which, incidentally, I didn't know existed until I was absent-mindedly wandering in the library a few days ago):

Problem 1.1(c). Most present-day [mid-1980s] computers only have one central processor -- to use our analogy, one clerk. This single file clerk sits there all day long working away like a fiend, taking cards in and out of the store like mad. Ultimately, the speed of the whole machine is determined by the speed at which the clerk -- that is, the central processor -- can do these operations. Let's see how we can maybe improve the machine's performance. Suppose we want to compare two n-bit numbers, where n is a large number like 1024; we want to see if they're the same... [suppose] we can hire n file clerks, or 2n or perhaps 3n; it's up to use to decide how many, but the number must be proportional to n. [How can you get the comparison time to be proportional to log n?]

The proof is by induction. The base case, when n = 1, is clear -- we can check that two 1-bit numbers are the same in one step. We want to show that if n clerks can do this in time t(n), then 2n clerks can do it in time t(n) + c, where c is a constant. But that's easy -- split each of the two n-bit numbers a and b into half: a = a₁a₂, b = b₁b₂. If a₁ = b₁ AND a₂ = b₂, return TRUE; otherwise return FALSE. That's just one more time step once you've figured out if a₁ = b₁ AND a₂ = b₂.

The picture I get in my head of this situation makes me smile. You need n clerks -- n parallel processors. The kth clerk compares the kth bit of the first number with kth bit of the second number; ey returns a 0 if the two bits are different and a 1 if they're the same. (This is, of course, bitwise (削除) exclusive OR (削除ここまで) exclusive NOR (thanks Anonymous!).) Then everything pours into a single node which is at the root of a binary tree of depth log₂ n.

The next subproblem in Feynman is to add two n-bit numbers in logarithmic time by using such parallel processing. (This is harder because you have to worry about carrying!) Again, it reduces to a problem of combining information on words of one length to words of twice that length -- if you have a = a₁a₂ (where a₁ is the "high", or more significant half, and a₂ is the low half), and b = b₁b₂, what is a+b? Breaking it down into its high half and its low half,

a + b = (a₁+b₁+c)(a₂ + b₂)

where c denotes a carry from the addition of a₂ and b₂, and a₂ + b₂ denotes addition modulo 2^k where k is the length of the summands. We assume a₁+b₁, c, and a₂ + b₂ are already known. The problem is... what if a₁+b₁ ends in a bunch of 1's, and c is 1? We have something like

...0111111 + 1

and we want to add the 1, so we think "okay, I'll just change the last bit in the first summand from 0 to 1"... but it's 1... so you change the last two bits from 01 to 10... but no, that won't work either... so you change the last three bits from 011 to 100...

On average this isn't a problem. On average the number of 1s at the end of a₁+b₁ is unity.

But not always. Somebody could be deliberately feeding you numbers that are hard to add. Some sort of sadistic grade school teacher.

edited, 10:48 am: Welcome to those of you who came here from reddit. Be aware that I am not a computer scientist -- I'm a mathematician -- so I might not really know what I'm talking about here.

From today's Foxtrot, you can learn what division really is. It also illustrates quite vividly the inefficiency of unary notation.

Division, of course, is basically just taking things and sorting them into piles of the same size, and then counting the piles; the result usually known as the division algorithm, which is not actually an algorithm but rather an existence theorem, makes this clear. I wonder if children learning arithmetic know this or if they think that "division" is just some magical algorithm that takes a bunch of numbers and pushes them around and spits out another number; it's been a very long time since I learned about division, and I've also learned not to trust my own introspection to tell me how "most people" see a given mathematical procedure. If I were "most people" I wouldn't be a mathematician.

For the most part I don't do arithmetic by the methods one learns in grade school. From just doing a lot of arithmetic (often in the course of experimenting with some combinatorial problem) I've quasi-memorized a lot of the particular arithmetic problems that come up most often. (In my case these seem to usually be products of numbers with small prime factors.) The set of arithmetical facts that I know off the top of my head is idiosyncratic; for example, I wouldn't know 39² or 43² off the top of my head, but I can instantly say that 37² = 1369 because it is in the name of 1369 Coffee House, which I frequented quite a bit during my undergrad years at MIT. But I also wouldn't multiply 37 by 37 by taking a bunch of things and arranging them in a 37 by 37 square and counting them. For one thing, I don't have 1,369 similarly-sized things. Also, I don't have a flat surface large enough for that in my apartment. This is why we invent calculation algorithms that don't directly mirror the definitions at the lowest level.

The grade-school arithmetic algorithms come pretty close to doing that, though, if you accept that you can arrange your objects in piles of 10, 100, 1000, and so on. But these aren't the most efficient methods; for multiplication, Strassen's method for integer multiplication has time-complexity Θ(N log N log log N) for N-bit integers, compared to Θ(N²) for the grade-school method. This paper of Martin Furer supposedly has better asymptotic behavior, although it wouldn't surprise me to learn that it's better only for very large numbers. (Strassen's algorithm, in turn, is only the best known method once the numbers get above 10,000 digits or so.)

The Simulation Argument is discussed at George Dvorsky's sentient developments, after being mentioned in an article yesterday by John Tierney in the New York Times. It's due to Nick Bostrom, whose original paper is available online.

The argument is as follows: "posthumans", that is, the people of the future who have much better computers than we do, will use their computers to run simulations of, well, more primitive humans. These simulations will be so detailed that they include a working virtual nervous system for all the people inside. And you have to figure that they're not going to run just one of these simulations; the future people run these simulations for fun! (This seems reasonable; I've spent way too much time playing SimCity to argue against this.) So we should expect that over the lifetime of humanity there are a very large number of such simulations being run, and that it is therefore very unlikely that we live in the "real world".

For me, this bears a superficial similarity to Pascal's Wager, although the mathematics is different; for one thing, Pascal's Wager involves an infinite payoff and there are no infinities here. But it's probably useful to think of there being effectively an infinite number of these simulations, in which case the probability that we're living in the "real world" turns out to be essentially zero. (Bostrom doesn't go this far; he says he feels there's about a 20 percent chance we're living in a computer simulation, which basically means he figures there's a 20 percent chance that civilization gets to the simulated-reality stage, if you neglect the probability that there are simulated realities but we're in the real one.) I suspect the real reason this reminds me of Pascal's Wager is because it seems natural to equate the runner of the simulation with "God".

What's especially strange, at first, is the idea that the simulations could have simulations within them. This reminds me of a cosmological theory that universes "evolve" by spouting black holes; in this theory, black holes are connections to other universes, where the various physical constants are slightly different than in the parent universe; thus there's a sort of Darwinian selection for universes, where the selective pressure is towards making lots of black holes. (Then why don't we live in a universe with lots of black holes?) As to the simulations within simulations -- if you carry this to the logical extreme, we are likely to live in some very deeply nested simulation. The problem is that infinite nesting probably isn't possible. And does the level of nesting even matter? My first instinct is to think that nested simulations would necessarily be of "lower fidelity" than first-level simulations, but since everything is digital this need not be true, as Bostrom himself points out. However, he also points out the disturbing fact that since a posthuman society would require more computing power to simulate -- you've got to simulate what all the computers are doing quite well -- if we head towards being posthuman we might be shut off! Personally I would like to think that the ethics of these simulations require the Simulator to not just shut us off. Presumably the person running the simulation could get on some sort of loudspeaker and let us know what was going on. (Although that might raise other ethical questions -- do simulated realities have some sort of Prime Directive, where you're not supposed to interfere with them?)

The mathematics of the argument seems so simple, though, that I'm almost inclined to throw it out on those means alone, along with other things likes Pascal's Wager and the Copernican principle. Surely proving the existence of God (and that's what this is, although people don't put it this way) can't be so easy!

On Monday I wrote that the Rubik's cube can be solved in 26 moves, where a move is defined as a half-turn or a quarter-turn of any face.

I'd forgotten that number, which I got from Wikipedia.

Then I came across this article at MathTrek, claiming 26 moves. The strategy was basically as follows: find the positions from which one could get to the starting position by making only half-turns, and no quarter-turns (call this set S); it turns out that from any of these, one can get to the starting position in 13 moves, and there are about 15,000 of them. Then the remaining items were put into sets such that the members of any such set only differed by half-turns; this roughly means that it's enough to reduce a single member of each set to some member of S. There are 1.4 trillion such sets, which sounds like a lot but is only one part in 30,000 of all the configurations of the cube. It turns out that a member of each such set can be reduced to a member of S in 16 moves, and 13+16 = 29. But the algorithm implied here solves most configurations in 26 moves or less; those that weren't, they solved by a brute-force computation.

Now, this sort of two-stage computation could probably be made better if the two stages were roughly equal in "size", that is, if 15,000 and 1.4 trillion (the product of which is roughly the number of configurations of the Rubik's cube) were equal. This is since the computation time is roughly proportional to the sum of these. If we have the constraint that the product of two numbers x and y is a known constant k, then we can minimize the sum of those numbers by taking x = y = k^1/2. Of course, in the case of the Rubik's cube there might not be some natural class of configurations with size roughly the square root of the total number of configurations.

Similarly, if we had a problem with k possible configurations and a three-stage reduction, you'd ideally want to reduce the number of possible configurations by a factor of k^1/3 at each stage.

But this is probably all useless, because if there were two intermediate subgroups you could reduce to, you'd probably want to take both of them even if you weren't lucky enough to have them at sizes k^1/3 and k^2/3 as would be ideal.

From Slashdot: Alexander Ratushnyak has won the second Hutter prize. This is a prize for compressing the first 100 megabytes of Wikipedia to a small size. The size that he achieved is 16,481,655 bytes; in March of 2006, before this prize was announced, the best possible was 18,324,887 bytes.

Hutter claims that "being able to compress well is closely related to acting intelligently" -- this is based on the thesis that the way to compress data well is to have a good idea of what's coming next, and the way to do that is to understand the structure of the data. So far, so good. But does it follow that understanding the structure of the data requires intelligence on the part of the compression algorithm? I don't think so. The MP3 algorithm, for example, compresses music for the most part by relying on psychological information about how humans perceive sound, and it required intelligence on the part of the inventor -- but I wouldn't ascribe intelligence to the algorithm.

Supposedly there is a proof that "ideal lossless compression" implies passing the Turing Test: the e-mail there by Matt Mahoney states

The second problem remains: ideal lossy compression does not imply passing the Turing test. For lossless compression, it can be proven that it does. Let p(s) be the (unknown) probability that s will be the prefix of a text dialog. Then a machine that can compute p(s) exactly is able to generate response A to question Q with the distribution p(QA)/p(Q) which is indistinguishable from human. The same model minimizes the compressed size, E[log 1/p(s)].

This may be true -- I'm not competent to evaluate the proof. But it does not follow that a compression method which is 1% short of ideal lossless compression is 1% away from passing the Turing test. And we don't know what the ideal even is! It is possible to estimate the entropy of natural language, but the estimates seem to be good to, say, one decimal place.

Dan has pointed out at my post secret messages in human DNA? that general-purpose compressors don't work in all data. If you gzip the human genome, it gets bigger. In fact, it's not possible to write a program that will losslessly compress all input strings, for the following reason: say we can write a program which losslessly compresses all strings of length up to N bits. There are 2^N+1-1 such strings, but only 2^N-1 strings of length N-1 bits or less; therefore there will be collisions among the strings of length N-1 or less, and we won't be able to properly uncompress the data.