Five Billion Names — Parallax Forums

# Five Billion Names

Posts: 1,111
edited 2011-06-26 18:59 in Robotics
Introduction

In 1953, Arthur C Clarke published a science fiction short story titled The Nine Billion Names of God. Briefly, the monks at an eastern lamasery believe that by enumerating all the possible names of God, they will have accomplished mankind's purpose and the world will end. See the plot summary at http://en.wikipedia.org/wiki/The_Nine_Billion_Names_of_God.

I have long wished to try this, but didn't want to destroy the forests necessary to actually print the names on paper. Would it be sufficient to simply flash the names, one or more at a time, on an LED or LCD multi-character display? A microprocessor, powered by an uninterruptible supply, could easily be programmed to drive such a display. Each name would be displayed for a few milliseconds, long enough for the display to settle and for God to observe it.

I assembled and started such a machine in June 2010. I expect it will complete the enumeration (and end the world) in October 2021.

How Many Names?

The most difficult task in an engineering project often is obtaining an unambiguous specification. This is no exception. Clarke gives us some clues but leaves much unstated.
How many letters are there in the name of God? This seems clear enough. Clarke writes ' We have reason to believe,  continued the lama imperturbably, that all such names can be written with not more than nine letters in an alphabet we have devised. ' So we base our calculations on names of nine letters.
How many symbols are there in the alphabet? Clarke doesn't say but with some arithmetic we can narrow it down. The table Workbook1.pdf displays, for selected symbol counts, the total permutations and the time required to display them at the rate of 40 per second.

Did Clarke intend an American Billion (One Thousand Million), or a British Billion (One Million Million)? An alphabet of 27 symbols comes out to 7.625 Million Million, so it is tempting to suppose this is what he had in mind. However, at the rate of 40 names per second, this would take 6 thousand-odd years for the program to run. Clearly this is unreasonable.

There is an additional clue in the story. The printers are electromatic typewriters; he doesn't say how many. If we suppose something like a Model 28 Teletype running at 110 baud, that is just about 10 characters or one name (plus a space) per machine per second. They expect to take one hundred days. At 24/7 operation, that works out to 86,400 names per machine per day or 8,640,000 names per machine over the one hundred days. So for an alphabet of 12 symbols, they would have needed about 600 Teletypes (plus spares) to get the job done.

Wow! 600 Teletypes in one lamasery

I chose an alphabet of 12 symbols, which I expected would take just over four years and produces something over 5 billion names. The symbols I chose are A, B, C, D, E, F, G, H, I, J, K, and L.

Which cases must we not display? Since this is really an incantation, we must get it just right or it will not work. Here Clarke provides just one clue.' A rather more interesting problem is that of devising suitable circuits to eliminate ridiculous combinations. For example, no letter must occur more than three times in succession. ' No other examples of ridiculous combinations are given, so that is the only one we will program for.

Hardware

The attached photos show the hardware. Since the incantation must be intoned without breaks or hesitation, and since I live at the end of a very long utility line, I choose to make it battery powered. Each of two banks of six D-cells provides a nominal 9 volts with new batteries, dropping to about 8 volts when they are exhausted. A capacitor provides power for the 1000 or so milliseconds while the switch is being thrown to the alternate bank of cells.

The solderless breadboard contains a Low-dropout 5 volt regulator, a Parallax BASIC Stamp BS-2 microcomputer, a few LEDs, and the connection to a display module. The display is a Scott Edwards BPI-216 Serial LCD Module, with a two line by 16 character alphanumeric display. Once started, this machine runs unattended, except for replacing cells and switching banks periodically.

Power Budget

Getting the current drain low enough to avoid changing batteries frequently was a challenge. Initially I chose a Parallax Serial LCD with a current drain about 20 mA. In addition I used a standard 98L05 voltage regulator with a very high quiescent current of 5 mA and a very high dropout voltage (7.5 V). This resulted in a current drain of nearly 30 mA, which meant changing batteries every 10 days or so. Worse, the high dropout voltage of the regulator meant the storage capacitor could discharge only a few hundred millivolts before the regulator ran out of headroom, resetting the microprocessor and restarting the program.

Changing the display and selecting a modern regulator reduced the current drain to below 5 mA. In addition, choosing an LDO regulator meant the storage capacitor could discharge longer while the switch was selecting the new cells. I expect about 50 to 60 days from each new set of D-cells.

Software

The actual program is appended. The IO pins are defined, as are a few constants and the locations containing the current name. I defined each character individually, even though the programming environment supports arrays. The array is initially set to AAAAAAAAAA (which is not a valid name).

Now for each pass through the code, the right-most letter is incremented. The second putative name is AAAAAAAAB (also not valid). If the resulting letter is greater than L, a carry propagates to the next letter to the left. When any carries have propagated and the new name is selected, we check for violations of the three-letter rule. If any are found, the name is rejected and not displayed. The very first name to be actually displayed is AABAABAAB. The very last name to be displayed is LLKLLKLLK.

A second counter, displayed on the second line of the LCD, keeps track of the trial names. It is updated and displayed whether the name is valid or not.

Expected Completion

In the Table, we assumed 40 names would be displayed per second; this meant a run of just over 4 years. This turned out to be a bit optimistic. In actual operation, the program examines roughly 1.25 million names per day. This suggests a total run time of 4128 days or 11.3 years. Since I started the run in June 2010, I expect it to complete sometime in October 2021 (successful prophets are never very precise).

Some Obvious Questions

Q. But you are not writing the names down on paper and pasting them into books.
A. Right. And that may invalidate the entire procedure.
Incidentally, at 500 names per 8-1/2 by 11 sheet, it would take 12.5 million sheet or 25,000 packages of Staples 20 lb paper to print them. That's a stack 40,000 inches or almost exactly one kilometer high.

Q. But you are not using the correct script. A, B, C,L is not what God expects.
A. It is a simple substitution. Surely God can solve such a simple encryption.

• Posts: 7,620
edited 2011-06-25 10:58
I remember reading that story when I was about 13 years old, around 1955. At that time a billion here in the UK was one million million.
• Posts: 23,085
edited 2011-06-25 11:43
Leon wrote:
At that time a billion here in the UK was one million million.
I thought that was still the case across Europe and that what we in the U.S call a billion (i.e. a thousand million) was a "milliard." Did that change at some point?

-Phil
• Posts: 7,620
edited 2011-06-25 12:28
I think that most people here assume it is 1000 million. I have done for many years.
• Posts: 5,770
edited 2011-06-25 22:12
If you add more processors to run in parallel, it could accomplish the task sooner. Using prop chips and dividing the chores between cogs and chips, the wait would be far less.

• Posts: 4,776
edited 2011-06-26 05:52
Humanoido wrote: »
If you add more processors to run in parallel, it could accomplish the task sooner. Using prop chips and dividing the chores between cogs and chips, the wait would be far less.

Now this is real spooky ... I've just calculated that if we throw Humanoido's 'big brain' at the task, the world will end around October 21 this year ...

Ross.
• Posts: 5,770
edited 2011-06-26 18:45
RossH wrote: »
Now this is real spooky ... I've just calculated that if we throw Humanoido's 'big brain' at the task, the world will end around October 21 this year ...Ross.
OMG! If you thought that was spooky, when I added in adjustments for the space time quantum effects of all the unseen dark matter hidden within the Spatial Arrays (include all Partitions) and then retained the postulate energy for good measure, it was seen that the world already ended at the turn of the century, October 21st of course.

• Posts: 5,770
edited 2011-06-26 18:59
Actually doing any of these calculations may be unnecessary. Just stick with the Mayan Calendar and its recent interpretations (12-21-2012).

• Posts: 1,111
Half way through. We have done A thru F in just about 69 months. That leaves G thru L. Still looking to Oct 2021 to wind things up.

• Posts: 20,027
Cool project Tom, but please don't end the world. Before October 2021, cut the blue wire!
• Posts: 3,485
no - wait - not the blue one, the red one, cut the red ones!

Enjoy!

Mike
• Posts: 228
No worries about the world ending on account of this undertaking.

The code by definition leaves out "The name that shall remain unnamed", "Yahwey", "Jehovah" and "Oh Great Spirit" and these are just a few contemporary 'names' used to invoke the divine.

Anyway, the batteries will have died long before the task is completed<g>. The lamas could have ended existence by simply drinking the koolaid.

• Posts: 792
RossH wrote: »
Now this is real spooky ... I've just calculated that if we throw Humanoido's 'big brain' at the task, the world will end around October 21 this year ...

• Posts: 1,111

It finished the run; "LLKLLKLLK". 5,159,780,351

The world didn't come to an end. It turns out there was a bug in the program. Clarke's specification included "For example, no letter must occur more than three times in succession." Sadly I rejected cases that had three letters in a row rather than more than three.

Oh, well.

• Posts: 12,200

@tomcrawford said:
It finished the run; "LLKLLKLLK". 5,159,780,351

The world didn't come to an end. It turns out there was a bug in the program. Clarke's specification included "For example, no letter must occur more than three times in succession." Sadly I rejected cases that had three letters in a row rather than more than three.

Oh, well.

Do we have to wait another 11 years after you rewrite? I don't know if I'm going to be around.

• Posts: 23,085
edited 2021-10-27 21:02

Publison, if you're not around, that will be the end of the world as we know it -- here at least!

-Phil

• Posts: 12,200
edited 2021-10-27 21:08

@"Phil Pilgrim (PhiPi)" said:
Publison, if you're not around, that will be the end of the world as we know it -- here at least!

-Phil

LOL! Happy to serve.

• Posts: 1,111

@Publison said:

@tomcrawford said:
It finished the run; "LLKLLKLLK". 5,159,780,351

The world didn't come to an end. It turns out there was a bug in the program. Clarke's specification included "For example, no letter must occur more than three times in succession." Sadly I rejected cases that had three letters in a row rather than more than three.

Oh, well.

Do we have to wait another 11 years after you rewrite? I don't know if I'm going to be around.

Don't know. I am 79 years old. Likely wouldn't survive another run.

Guess the world is going to have to get along as best it can.

tc

• Posts: 1,256

This is amazing. I love the fact that you faithfully replaced the batteries over the years. Forget how many names; how many cells did you go through?!

• Posts: 1,516

I too in the late 70's age catagory. Maybe the test could be rewritten to run on a P2 and cut the amount of time.
Jim

• Posts: 12,200

@RS_Jim said:
I too in the late 70's age catagory. Maybe the test could be rewritten to run on a P2 and cut the amount of time.
Jim

Or a Cray.

• Posts: 792

Exactly 9 letter names?
I get 5_610_940_140 names if I allow 1..9 letters in names.
For not ending evolution, I only let the computer count the names instead of printing or saving.