The Real Infinity, For Reals

This is the third article in a series called Before I Forget, an exposition for the semi-layman of freaky high-level mathematics. Last time we talked about cardinal numbers: numbers which are used for counting the elements in very large sets. This time I’ll use the compactness theorem to introduce an infinity that you can use in ordinary arithmetic to get ordinary results. Remember limits from calculus? Turns out you don’t need ‘em to do calculus. We’ll see how this time.

This is the first article that will dive into the details of first-order logic. I’m not going to spend the time here to describe first-order logic: it is a deep subject with a rich vocabulary and lots of little nooks and crannys where faulty reasoning can hide. However, I highly recommend that everyone learn its principles and how to use it. It will change the way you think; it will endow you with the ability to approach certain situations with extreme precision, and to clear away bullshit that many authors throw at you. See the wikipedia page, including the external links section, if you’d like to know more. It’s not technically required to understand this article, but it is required to grok this article.

Sexy mathematical models

I will begin by presenting the difference between a model and a set of sentences. Okay, so we have a sentence of first order logic endowed with one extra symbol: S (successor). We will use this to represent the natural numbers. The existence of the number 0 is expressed by the following sentence: ∃x ∀y S(y) ≠ x (there is an x which is not the successor of any number) (remember we’re in the natural numbers, there is no -1). So when we say 0, we really mean to introduce a new variable and that sentence to identify our 0. The important thing is that we can express it though. And now we may represent any natural number using successor and 0. 1 = S(0), 2 = S(S(0)), 3 = S(S(S(0))), etc.

(more…)

Locally Optimal Nanopond Solution

Here is a lifeform which has “solved” nanopond, which evolved after running the simulation for 14 hours; I find it unlikely that any new lifeforms can beat this one:

  15e83eb5e46b5e91ed58ac0f

Translated, that is:

  1
  READG
  SHARE
  WRITEB
  INC
  SHARE
  TURN
  READG
  SHARE
  DEC
  WRITEG
  TURN
  READG
  SHARE
  LOOP
    FWD
    SHARE
    KILL
    READG
    WRITEB
  REP
  XCHG 0
  STOP

There are two things that make this species strong: one, it shares almost randomly with cells around it, so it basically can eat energy from 5 cells around it instead of just the one it’s on; two, it rewrites its first nybble with a random(ish) one (one of its neighbors’ first nybbles minus one), so that nothing can evolve to kill its kind. Recall that to kill a cell you have to have the first nybble of that cell’s genome in your register when you do. Constantly changing your first nybble prevents that.

Darn

Well, you know what they say, some sessions are better than others. This session was definitely one of the others. I don’t really know what went wrong. One of my guesses is that I couldn’t hear Evan well enough (or I could hear him too well—sometimes the bass is so booming that I can’t tell which note is playing!), but I don’t remember. But there was definitely a severe lack of communication on top of the fact that I was just playing like crap in general.

That said, the first two tracks are decent, and our endings were generally clean. Maybe I can pretend that that was just an “ending practice” session. #9 has so much potential, but it seems like the second we got onto something good we’d mess it up the next measure. There were some beginnings of lines that could have had good endings :-). I’m actually not so discouraged, because this was a two part session and we only recorded the first part. If I recall the second set was a lot better. At least it was a lot more unique (we did some of that great classicalish stuff).

Anyway, we have a gig next Friday. I hope the percussion warmup I suggested will work as far as getting us in the flow, and we don’t end up putting on a show like this session…

Oh, look at that, #13 is decent too, and #14 is good save for some sloppy lead playing.

1. 2007-06-13_01
2. 2007-06-13_02
3. 2007-06-13_03
4. 2007-06-13_04
5. 2007-06-13_05
6. 2007-06-13_06
7. 2007-06-13_07
8. 2007-06-13_08
9. 2007-06-13_09
10. 2007-06-13_10
11. 2007-06-13_11
12. 2007-06-13_12
13. 2007-06-13_13
14. 2007-06-13_14

No Shame

Nanopond

Ben Burdette showed Namaste and me a remarkable lifesim program called Nanopond. This program, in relatively few lines of C, gets closer than I ever have to something that I have been trying to do for some time. It is behavioral evolution, by evolving not a neural network on a continuous plane (as I have tried), but by evolving virtual machine code on a discrete grid.

I think I can use almost exactly this genome for my bacteria game. I would like to change a few things here and there. For example, an organism can “eat” a neighboring organism if the value in the register at the end of execution matches the first four bits of the genome of the target. However, the only operations available for changing the value of the register are INC and DEC. So an organism that starts with instruction 0 (RESET) is much more susceptible to attack than one whose first instruction is b (KILL, maybe?). That is, the code for an organism that eats the former kind can be just KILL, where as the latter kind you’d need something like DEC DEC DEC DEC DEC KILL. There’s no reason the latter kind should be harder to eat, and that’s why I don’t think you see many predators in this simulation.

Instead, I’d like to replace INC and DEC with an ADD instruction that takes its next instruction as an argument. So that way everything but instruction 0 is equally easy to eat: ADD n KILL, where n is the signature (first four bits) of the target.

I’d also like to try to add more support for multicellular organisms. I’m not quite sure how to do that, but I’m not sure nanopond’s genome is capable of that. If I’m going to make this a massively parallel simulation a la ElectricSheep (which is my current intent), then I want the genome to be capable of multicellular organisms because we might just get one, which would be amazing. My current idea is to allow cells to trigger execution of neighboring cells.

I’m pretty sure I can code up a proof of concept by GameDev (Tuesday).

The Lesser of Infinitely Many Evils

This is the second post in a series called Before I Forget, which is an exposition for the semi-layman of some freaky high-level mathematics (mostly set theory). This episode is still about infinity, but covers the Cardinal numbers.

Last Time

Last time I introduced the ordinal numbers, specifically the ordinal ω—the least number greater than all the integers—and things derived from it (like ω × 2, and ω^ωω… an infinite number of times… (ω times, actually :-)). Today we’ll be exploring a parallel concept to the ordinal numbers called the cardinal numbers. Ordinals are used to index positions: the 1st position, 2nd position, ωth position; cardinals are used to measure sizes.

Well-ordering

Okay, let’s step out of the context we’ve been working for just a little while. Numbers are now the numbers you are familiar with: not just the nonnegative integers, but also negatives, fractions, and irrationals. Here is an exercise: come up with a set of numbers which has no least member. This should be pretty easy, but it should be obvious that the set must be infinite.

Got one yet? I want you to come up with one before you continue reading.

One of the most obvious examples is the set of all numbers greater than (but not equal to) 0. How do you know it doesn’t have a least member? Well, suppose it did, and call it x. We know that x > 0, because it was in our set. Well, if x > 0, then x/2 > 0 also, so x/2 is in our set. But of course x/2 < x, so it turns out that x wasn’t the least member after all (but we chose x specifically to be the least member, so this is a contradiction). Our supposition that our set had a least member must have been flawed, and we have thus proved that our set has no least member.

Another example is the set of all integers (positive and negative). It extends infinitely in the negative direction, so it can’t have a least member. (Exercise for the reader: prove formally that the set of all integers has no least member like we did for the real numbers greater than 0 in the last paragraph) There are tons of sets with no least member, and yours could have been quite different from my two examples.

Here’s another challenge: come up with a (nonempty) set of positive integers that has no least member. Got one? No, come on, come up with one. I dare you. Don’t continue reading until you have one.

Yo mama’s fat.

(more…)

An Infinitely Unbounded Stack of Innumerable Infinities

This is the first post in a new series of mine, “Before I Forget”. This series is an exposition of all the awesome (in the British sense), marvelous, haunting mathematics I learned while in college. I’m not sure how often I’ll add to it or when it will end, but I know that I’ve been itching to write about some of this stuff for a while. I’m writing it to be somewhat accessible. I know I have several readers who skip over any math stuff, but I encourage those people to read this anyway if they have the faintest interest. Some of the notation might be confusing, but, if I’ve accomplished my goal, you should be able to understand it anyway because I’ve been redundant enough that you should be able to understand it. :-p Oh, and of course questions and comments are welcome. Without further ado, here is the first article, about Infinity and the Ordinal Numbers (which will form a basis for the rest of the series).

The Real Infinity

While I was a tutor in Calculus 2 (in 2005 I think) I noticed that the students were quite comfortable with the concept of infinity. But their comfort was not well-founded, as it turns out. The first sign of trouble was when they would write constraints like “4 < x < ∞” instead of “4 < x”; not a big deal, but an indication that they were missing the details somehow. Given a problem like: “find lim_{x -> ∞}((x²+x)/(x²+1))”, their reasoning would often proceed “the limit of x²+x is infinity, and the limit of x²+1 is infinity, so the result is ∞/∞ which is… (they look to the little table in the book)… undefined! That’s the answer, undefined!” (Exercise for the reader; why is that wrong?). The main problem is that they were using infinity as a number—a mathematical object—that you could do arithmetic on with the results as defined in the book (much like the IEEE floating point standard or Nullity… shudder).

The problem is that infinity is not a number. It is just a notation which stands for something more precise, depending on context. Saying “lim_{x -> 2} f(x) = ∞” doesn’t mean that the value of the “limit function” is “equal to infinity” there, it means that I can make f(x) get as big (but still finite!) as I want by getting x close enough to 2. You want f(x) to be 1,000,000,000,000,000? If I set x to 2+10^-400 I can do that. That’s what that expression means. More simply, if you say x ε (-∞,6], you’re just saying x ≤ 6.

So infinity is not an object… or rather, it wasn’t, until we started talking about sets.

(more…)

Sunbathing in a Boat

Today’s improvisation. I need to start doing these regularly again so they can the quality that they were back in December when I stopped.

Werepoker bidding

All week I have been trying to program Werepoker and giving up after the first 20 minutes or so. I think that’s partially because it’s needlessly tough networking and threading, and partially because I know there is a high probability that the program would never be used. Well, I want to play werepoker tonight at GameDev, so I want to implement something. I think I will implement the minimal computer assistant necessary for the game to function: the bidding.

The situation: a silent auction. Everyone puts in bids for the roles they want; i.e. how much they are willing to pay for a particular role. Then we assign roles according to the bids. But there are lots of little edge cases to worry about: what to do in case of a tie, what about when someone wins two roles, etc.? The metric we will use to decide these edge cases is fairly obvious, namely to maximize the total amount everyone pays (that’s what you want to do when you’re holding an auction).

Let’s formalize this. For each player p ε P, there is a bid function b_p: R -> $, where R is the set of roles, and $ is the set of nonnegative amounts of money. We’re trying to find an assignment function a: P -> R that maximizes Σ_pb_p(a(p)).

Thanks to Daniel Crumly for pointing me at the Hungarian algorithm to solve this problem.

Hmm, the Hungarian algorithm won’t work for this problem, because it needs to be predictable by players. If you bid higher than anyone else on something, it’s still possible that you won’t get your choice depending on other bids. I’m thinking I’ll use a simple heuristic greedy algorithm.

It goes like this. Sort all bids, highest first. Give the highest bidder his wish, and remove him from the candidates. If there is a tie for the highest bidder, choose the one with the lowest secondary bid (because he is likely to pay more for a different role), or tertiary in case of a tie for that, and so on. Of course, if the bids are identical then just choose randomly.

Pale Panic

Two improvisations today:

• Pale
• Panic