Countability in C

Act I: The Countable RAM

The year is 2150. Mankind has still not ventured into space, but they have made amazing strides in computer hardware. For better or worse, however, the C programming language has survived. We join two young hackers, Treitan and Aila, who explore the ramifications of their new computers on the programs they can write.

Aila: Trei, you have to see this new box!
Treitan: No way could it be as good as mine.
Aila: Are you kidding? We're talking a 4.8 petahertz quantum CPU with infinitely-precise registers...
Treitan: Yeah, yeah, got that.
Aila: An array of 65536 20 exabyte drives...
Treitan: I have my dog's quota set higher than that.
Aila: But here's what I really had to shell out for: infinite RAM.
Treitan: Infinite RAM?
Aila: Yup! Not only is there a memory cell for every number from 0 up, but every memory cell can hold an infinitely-precise real number.
Treitan: But what good is infinite memory if you can't fill it up?
Aila: Oh, but I can. Check out this code:

int* a = malloc(infinity);
for(int i=0; ;i++)
    a[i] = i;

Treitan: Are you kidding? That program obviously never terminates.
Aila: That's not the point. Name a number.
Treitan: Um, how about 131,072?
Aila: It eventually stores that number into a[131072].
Treitan: Okay, how about a santillion? A googleplex?
Aila: It eventually reaches those numbers too, and stores them into some place in the array a.
Treitan: Hmm, I see your point. It doesn't matter so much that it never terminates, as long as it eventually reaches any number I can name. But does this mean that this program stores all of the natural numbers in your RAM?
Aila: Effectively, yes.
Treitan: Ha! You call that power? You can't even fit all of the integers into your memory.
Aila: Sure I can.
Treitan: No you can't. You already filled it up with the natural numbers alone, how can you hope to fit more?
Aila: How about something (types rapidly) like this?

int* a = malloc(infinity);
a[0] = 0;
for(int i=1; ;i+=2) {
    a[i]   =  i;
    a[i+1] = -i;
}

Treitan: Hrm. So it seems like you're storing all the positive numbers at odd indexes and all the negative numbers at even indexes.
Aila: Works beautifully, doesn't it?
Treitan: So it seems like both the natural numbers and all the integers occupy the same amount of space. Hey, let me try something.
Aila: All right, but don't screw anything up.
(Treitan types a new program)
Treitan: There! Check it out, it writes all of the positive rational numbers, fractions, into the array.

int* a = malloc(infinity);
int i=0;
for(int numer=1; ;numer++)
    for(int denom=1; ;denom++)
        a[i++] = numer/denom;

Aila: (sigh) No, Trei, that's not going to work.
Treitan: C2132 does allow infinitely-precise divides, doesn't it?
Aila: Yes, but that's not the problem. Tell me, how long should I wait before your program stores, say, 2/3 into the array?
Treitan: Er, I guess it would be a long time.
Aila: An infinitely long time. Your inner loop never terminates, so numer is going to be 1 forever.
Treitan: Oh well. I should've guessed there's too many rational numbers to fit into your memory.
Aila: You want a bet? (edits the program) Check this out:

int* a = malloc(infinity);
int i=0;
for(int j=1; ;j++)
    for(int denom=1; denom < j; denom++)
        a[i++] = (j-denom)/denom;

Treitan: Hmm, I see. Now the inner loop always terminates, so j reaches every possible value. But how do I know it stores all the rational numbers?
Aila: That's easy. Give me a rational number.
Treitan: How about... 355/113?
Aila: Just wait until j=355+113 and denom=113.
Treitan: I see. Eventually we have to add every rational number. But how can this be true? You're assigning an index in your array to every rational number in the world. But there have to be more rational numbers than array indexes.
Aila: There's actually not, and this program proves it. It seems like there's a lot more rationals, but we can really assign a natural number to every one of them.
Treitan: Well, you still haven't covered all the rational numbers. What about the negative ones, and zero?
Aila: You were always a pain, you know that? If you insist, it's easy to fix. (types) There, see:

int* a = malloc(infinity);
a[0] = 0;
int i=1;
for(int j=1; ;j++)
    for(int denom=1; denom < j; denom++) {
        a[i++] = (j-denom)/denom;
        a[i++] = -(j-denom)/denom;
    }

Treitan: Oh, yeah. It's the same trick you did with the integers.
Aila: Easy as pie.
Treitan: This is really great. I bet you could fit anything into this computer's memory!
Aila: I'm not sure about that, Trei.
Treitan: Watch this! (quickly types and executes a new program)
Aila: What are you doing now?
Treitan: This program just wrote all of the real numbers between zero and one into your memory.
Aila: I don't believe it. Let me see the program.
Treitan: After the way you tore up my last one? I don't think so.
Aila: Fine, be that way. I can write a program that can prove that your program didn't work.
Treitan: (smugly) I'd like to see that.
Aila: (types) Here, check it out:

real new;
for(i=1; ;i++)
    if (digit(a[i],i) == 5)
        digit(new,i) = 4;
    else 
        digit(new,i) = 5;

Treitan: Hmm. So what is this program doing?
Aila: Simple. It's finding a new real number that your program didn't write into the memory. The digit(r,k) function just extracts the kth digit beyond the decimal point of the number r.
Treitan: How do you know that the new number is really new? You might just end up with a number that's already in the array somewhere.
Aila: But I won't, and here's why: notice that the ith digit of new is different from the ith digit of a[i].
Treitan: I can see that. When the ith digit of a[i] is 5, you assign 4, and when it's not 5 you assign 5. But what's the point?
Aila: The point is, if new has a different ith digit from a[i], it's certainly not equal to it, right?
Treitan: I'll buy that...
Aila: And if that's true for all the indexes i...
Treitan: Of course, I see now. It has to be different from every number in every index.
Aila: Right!
Treitan: Okay, so my program has a bug in it. Let me fix it.
Aila: No, Trei, you don't get it. It doesn't matter how you wrote your program. It could work with divine intervention for all I care. My program will still find a new real number that isn't there.
Treitan: So you're telling me there's no way to store all the real numbers in your memory?
Aila: Hrm. I guess you're right. The real numbers won't fit in my memory. There's just too many of them.
Treitan: So much for your fancy new machine!

Act II: The Continuum RAM

To be continued...

Other Moonflare documents

Moonflare home

All text and images, but not necessarily linked material, on this page ©1998-2006 Derrick Coetzee and Moonflare and may not be reproduced or used for any purpose without prior written permission except where otherwise indicated.