Date: Wed, 2 Oct 1996 12:45:25 -0700 (PDT) From: Anthony Spataro
Subject: Godel neither here nor there... To: email@example.com
When I was seven, I read a science fiction story about an interstellar mission from Sol to a nearby star. The starship's crewmembers were supposed to survey the habitable planets in the destination system and start a colony. Since the journey was undertaken at sublight speeds it took quite a long time to reach the system, which gave the crew quite a bit of free time. They spent the sixty years of their voyage learning and doing research. In a small, closed environment where everybody was focused on th ought, they found it very easy to conduct research and were soon sending scientific data back to Earth that were more valuable than the mission itself. As they neared the star their level of technology began to outpace that of Earth and their long-distan ce surveys showed that there were no habitable planets in the system--in fact, there were no planets at all! They knew that the originators of the mission back on Earth knew this from the start. It turned out that the real purpose of the mission had been to isolate the crew and force them to focus on their research. In the final pages of the story the crew created their own habitable planet in orbit around another star, bombed Earth back into the stone age (from a vantage point 50 light years distant!) and sent the survivors an encoded message in the form of an extremely large number. The message contained the coordinates of their new planet, as well as information on faster-than-light travel. The catch was that the number required incredibly sophisti cated technology to decode the information hidden inside it. By the time Earth had developed computers sufficient for the task, they would be mature enough to use the advanced technology of the colonists.
In case you haven't already guessed, the colonists' final message to Earth was encoded using Godel's system of primes raised to the power of primes. Even at that age I found the idea extremely fascinating and saw no end to the practical applications of s uch a technique. Though I didn't know the right words at the time, I realized that compression and encryption would both benefit from the ability to reduce a string of characters into a number and then extract the original string from the number. As tim e passed, I forgot the name of the story, then the author's name, and then the exact technique used to encode the message--I remembered only the name of the mathematician, Godel.
Now I'm a freshman in college, cutting my teeth on the first few weeks of computer science curriculum. This morning I was reading an incredibly dense handout on infinite sets and cardinal numbers when I saw Godel's name mentioned in the text. That old s ci-fi story had such an impression on me that I am reminded of it whenever I hear Godel's name, and on a whim I decided to search the web for information about the encoding technique (it's easy when you've got a fast Ethernet connection instead of a #@$@# ! modem). I found your little tutorial. With the years of experience I've had in math and programming since I last read about the technique, I find it even more intriguing. There's only one catch--factoring out the original message sounds like it's goi ng to be a thoroughly icky and laborious task. I haven't even had calculus yet, but one thing I have learned from algebra and trigonometry is that you should run away when you hear the word "factor," especially in the context of work that *you* are going to have to do. Am I right? Is it a hopeless task, trying to extract the message from the number, or is there a known method to do it? If there is, and it isn't too computationally expensive, then it should be possible to write a program to Godelize and deGodelize streams of data.
All one needs are an arbitrary-precision integer math library (which I've written) and a good long list of prime numbers. I recall hearing of some method to generate new prime numbers from previously known primes, so when t he list runs out you can just start generating new ones.
Even if the program is too slow for today's computers, it will someday be possible to write it.