I have a question - if the axiom of choice is such a good idea, what's wrong with the negation of the axiom of foundation? Don't they both state the existence of absurd things? Aren't they both very far removed from practical mathematics? ZF is intuitively bothersome this way - it allows for some unreasonably powerful statements, and has axioms to undermine those statements enough to make it reasonable.

A lot of the pro-AC propoganda people are taught in undergrad school involves things which can be straightforwardly constructed without AC, hence the seeming intuitiveness of the common statement of AC - it strongly intuitively implies a bunch of things about the sets involved which would make AC not necessary. Things which need AC tend to be along the lines of the Banache-Tarski, which is completely absurd.

Really Big Numbers

Scott Aaronson sent me mail a while ago, which promptly got lost in the disaster area known as my inbox. I just found it, so I'll comment on it now.

Who can name the biggest number? is, as I commented earlier, an interesting game. Large numbers loosely correlate with busy beaver machines which can use oracles corresponding to large infinite numbers. The problem with this is that we don't, and can't know which large cardinal axioms are consistent, especially when we're trying to be aggressive about naming the largest possible one.

The next step, at least to my mind, is to talk about 'the largest consistent large cardinal axiom which can be expressed with less than a million symbols'. This is analagous to, but more well-defined than, Aaronson's 'The biggest whole number nameable with 1,000 characters of English text', which suffers from a self-referential Russel-style paradox. Numbers named using this technique have an astounding level of inaccessibility, almost like we said 'The largest number which can be imagined by a human mind plus one'. We can contemplate the existence of such a number, but by definition we cannot imagine it.

I sure like picking on Wolfram

Scott also reviews ANKOS and points out a number of outright errors in the book. In particular Wolfram's comments about rule 110 being 'NP-complete' are unsubstantiated, since the construct used involves an exponential number of steps, and hence computing it isn't in P.

However, it is true that we now know that rule 110 isn't computable, once you deal with the encoding issues of computing starting at what state and what you want to know if the output finally does.

That said, my earlier comment about there being computable but nontrivial rulesets analogous to Presburger arithmetic wasn't flippant. I've spent a fair amount of time playing with Wolfram's rule sets and a definite category which he never mentions emerges. Many of the rules produce very messing looking output on random input, but any vaguely simple input results in obvious non-repeating but still simple patterns. In ANKOS Wolfram himself talks about one of the most complex-looking ones of these and says that he ran two million simple inputs and they all resulted in straightforward patterns. Somehow he completely avoids even speculating that this rule is less strong that fully general computation. Maybe he's in denial.

I'd very much like to see it proven that many of Wolfram's automata are computable. Partially because any such proof would be very deep and interesting, but also because I don't like Wolfram's attitude and would very much like to see his central thesis thoroughly debunked.

Public Key Cryptography

This paper gives a public key cryptosystem very similar to the one I came up with, and they manage to prove some solid results about the difficulty of their primitive, while I merely conjecture at the difficulty of mine.

I'm quite happy to have come up with a public key cryptosystem, despite it being comically impractical. Almost everyone can come up with a symmetric cipher which they themselves can't break, but designing any public key encryption algorithm at all which can't be broken trivially is quite difficult.