Five Billion Names
tomcrawford
Posts: 1,126
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.
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.
Comments
-Phil
http://forums.parallax.com/showthread.php?124495-Fill-the-Big-Brain
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.
http://www.adishakti.org/mayan_end_times_prophecy_12-21-2012.htm
Enjoy!
Mike
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.
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.
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.
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
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?!
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.
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.