Carmack is Learning to Program, OR: BIT MASKS and The Multiverse


John Carmack is learning to program. A few months ago he posted that he was going to try to start remembering to use preincrement (++i) instead of post (i++). This gives me some hope, because he is already a legendary programmer but there's still stuff he doesn't know.

std::set vs ye olde bitmask

In C you can do something like this:

#define BIT_BOLD 0x0001

@p #define BIT_ITALIC 0x0002

@p #define BIT_UNDERLINE 0x0004

 

And then combine them freely using e.g.,

print_text ("Hello, World", BIT_BOLD);

@p print_text ("This is Very Important", BIT_ITALIC | BIT_UNDERLINE);

 

Carmack noted the other day in a tweet:

Tweets by John Carmack talking about sets: \

And that got me to thinking, is that really right? It seems a bit wrong intuitively; yet, clearly, bitmasks are a kind of set.

@p This AM I figured out what bothered me. There is a real, mathematical difference here.

  • A bitmask is defined conceptually as a set over a small, fixed domain.
  • A set, on the other hand, is defined over an arbitrarily large (infinite) domain.

Consider std::set< int > for example; although int is NOT truly an "arbitrarily large" domain (having "only" 2^32 elements, well-short of arbitrarily large) we do conceptually treat it like that. A bitmask on the other hand always has a well-defined domain. We'd never imagine just inserting bit "599271662758" randomly into a bitmask, and would run out of memory long before we could do it, anyhow.

Ontological Argument

This got me thinking about something that rankled me years ago. I read a newspaper article that said, if the "many universes" hypothesis of string theory were true, it ought to not surprise us that our universe exists since it would pretty much have to, no matter how unlikely (if you are scratching your head, I am too, but there you have it.)

@p Similarily rankling to me are the arguments that people make along these lines: since an infinite number of-- indeed, "all possible"-- universes exist, then somewhere, somehow, there is a you who has lost his left arm, has a larger nose, and so forth, but it is otherwise identical to you.

@p This drives me crazy because it is so obviously wrong.

A student with unkempt hair sits as his/her desk and thinks, There must be SOME universe where I understand transfinite induction...

Grapefrukt

Photo of the new Peace Bridge in Calgary, AB, Canada; photo by Incremental Photo (incrementalphoto on flickr)

The Peace Bridge. Photo by Incremental Photo. Apprently everybody was opposed to this bridge, but on opening day 2000 supporters outnumbered 2 opponents 2000:2. I guess the people who were opposed to the bridge are also too lazy to make use of it? UNSURPRISING. Also: a big part of the opposition was that it was designed by a Spanish Architect. Because it's crazy to think the best architect for a landmark bridge doesn't already live in Alberta, a place known for it's great architecture. Sorry I try to keep sarcasm to an absolute minimum here, but this is a nice bridge.

Humans are bad at thinking about large numbers; for instance I estimated a crowd a few weekends ago at 5000 but "reasonable" estimates seem to have it at 2000-- a pretty big difference when you're talking about people! So I clearly have no idea how big even a smallish number like 2000 is, let alone millions or billions or trillions.

@p It ought not then to surprise us that we are even worse than that when it comes to infinities. And the fact is that there are certain infinities that are larger than other infinities.

@p In fact, some of the largest well-defined mathematical objects are described in terms of sets-- a far cry from our humble workhorse the bitmask. And these sets are incredibly larger than what we typically think of as infinite, that is to say countably ifinite.

@p Back to our original point about the multiverse. The wrongness of this thinking is easy to see if you just think of the set of all natural numbers, { 1, 2, 3, ... } which has an infinite number of things in it (for any natural number N, you can still have N + 1, and that must be in this set, so there's not a finite number of things in it.)

@p So then, does this set of natural numbers contain a grapefruit? Of course not. N + 1 == Grapefruit is provably false for any N.

@p In the same way, an infinite set of all possible universes does not necessarily contain one with a copy of you but just with a longer nose.

 

Imaginary Sets

Of course, we can easily imagine or if you prefer, define such a set of universes; it's quite easy and need only contain universes, { U, W } where "W" is the universe exactly as this one is (= "U") but with you having a longer nose.

@p But this does not mean that whatever precise theory defines the physical laws, or that even whatever infinite set of theories definining all possible physical laws, can allow for such a universe to exist.

@p Just because we imagine something exists in some possible way in some alternate universe somewhere doesn't mean that it can actually be true. It really is going to get down to the specifics of how those infinite sets of infinite universes are defined. Just because there are some variety of infinity of them doesn't mean there is every one of them.

@p I'm going to go out on a limb here and say I can't imagine a universe in which a newspaper article gets the particulars of this right. But I could be wrong!

@p I mean anything's possible amirite?

2012-04-01


◀ Back