Thoughts and links about programming, by


Debugging the Universe
Posted on Wednesday, January 23, 2008.

Every programmer knows what debugging is. Given a program that isn't behaving as expected, you slowly refine your understanding of both the program and the anomalous behavior until you understand exactly why the two aren't in agreement. Sometimes the bug is in the program, other times in your understanding of the program. Then you fix it.

Physicists debug the universe. When the universe doesn't behave as expected, they debug it, trying to reconcile their understanding of the universe and what they are seeing. The difference is that the bug, by definition, is always in their understanding and never in the universe.

During the development of the Global Positioning System (GPS), the physicists and programmers had to debug general relativity. To tell the story, you need to know a tiny bit about how GPS works.

Each GPS satellite broadcasts a known pseudo-random number sequence. A simple GPS receiver has its own pseudo-random sequence generator that is synced with the satellites. By timing how far “behind” the satellite sequences appear to be compared to the receiver's time, the receiver can determine how far away they are. Using the known positions of and distances to three satellites, a GPS receiver can triangulate its position in three-dimensional space. If the GPS receiver's clock is not exactly in sync with the satellites, it can use readings from four satellites to triangulate its position in four-dimensional space-time, synchronizing its clock in the process.

All this assumes that the clocks in the satellites are running at the same speed as the clocks on the Earth, but the satellites are literally running circles around the Earth; at those speeds, relativity kicks in and unexpected behaviors emerge. This was actually something the GPS engineers had to consider. Peter Galison tells the story better than I can:

According to relativity, satellites that were orbiting the earth at 12,500 miles per hour ran their clocks slow (relative to the earth) by 7 millionths of a second per day. Even general relativity (Einstein's theory of gravity) had to be programmed into the system. Eleven thousand miles in space, where the satellites orbited, general relativity predicted that the weaker gravitational field would leave the satellite clocks running fast (relative to the earth's surface) by 45 millionths of a second per day. Together, these two corrections add up to a staggering correction of 38 millionths (that is, 38,000 billionths) of a second per day in a GPS system that had to be accurate to within 50 billionths of a second each day. Before the first cesium atomic clock launch in June 1977, some GPS engineers were sufficiently dubious about these enormous relativistic effects to insist that the satellite's atomic clock broadcast its time “raw.” Its relativity-correction mechanism idled onboard. Down came the signal, running fast over the first twenty-four hours almost precisely by the predicted 38,000 billionths of a second. After twenty days of such gains, ground control commanded the frequency synthesizer to activate, correcting the broadcast time signal. Without that relativistic correction, it would have taken less than two minutes for the GPS system to exceed its allowable [daily] error.

(From Peter Galison, Einstein's Clocks, Poincaré's Maps pp. 288-289.)

I heartily recommend Galison's book, a history of the development of the physical concept of time throughout the twentieth century. Galison has doctorates in both physics and the history of science; using his dual expertise he makes the material accessible to dual laymen.

For a more technical account, the book's endnotes cite Neil Ashby, “General Relativity in the Global Positioning System

(Comments originally posted via Blogger.)

  • Russ Cox (January 23, 2008 4:41 AM) A more detailed endnote to that section reads:

    Corrections are of many sorts, and include effects due to the motion of satellites, the lower gravitational field at the height of the satellites, and the rotatory motion of the earth. The relativistic component of the Doppler shift is v^2/2c^2, which for satellite velocities is about seven millionths of a second per day. Because the speed of light is so much faster than the speed of the satellites, most of general relativity need not be taken into account, but the equivalence principle that is part of general relativity is significant. (The equivalence principle says that there is no way to distinguish the physics of a freely falling box from the same box without a gravitational field.) A more rigorous analysis would take into account (inter alia) that the satellites' orbit is not always in the same gravitational field, that the earth observer may be moving on the surface of the earth, that the earth's gravitational field is not the same everywhere on the earth's surface, that the sun's gravitational field affects the earth clock and the satellite clock differently, and that the apparent velocity of light is altered by the earth's gravitational field.