Trains, Elevators, and Computer Science

A possible method for making systems safe

George Westinghouse was not a theoretician, but was one of the great inventors of the 1800’s. He is most famous, perhaps, for the invention of the train air-brake in 1869. More on this in a moment.

Today I plan on talking about generalizations of Westinghouse’s ideas, and a role that they might play in computer science.

Train Brakes

The first trains were called Wagonways and were used in Germany as early as 1550. The power to move these trains was supplied by horses, until 1804 when Richard Trevithick, funded by Samuel Homfray, used a steam engine to haul 10 tons of iron and 70 men for 9 miles. This was the beginning of modern trains.

Almost immediately a critical problem developed: how to stop a train? Stopping the engine alone was insufficient once trains became long and moved fast; there was too much momentum for the engine, by itself, to stop a train. The first method used was simple: have an operator assigned to each car—they would pull on a hand brake when signaled to do so by the engineer. This quickly gave way to the direct air-brake system. In this system when the engineer wished to stop the train, he opened a valve that sent compressed air to each car—the air forced a brake against the car’s wheels. The train then stopped. Pretty neat.

Almost immediately another critical problem developed: how to stop a train reliably? The direct air-brakes worked well, when they worked. But if the compressed air tank was empty, or the pressure was too low, or there was a leak in the lines, the brakes would fail. Then the train would not stop. This was a problem.

Westinghouse’s genius was to solve this by inventing the reverse air-brake system. His brilliant idea was to use compressed air to make the train go, not to stop the train. Here is how his system worked. Each car had brakes that were held against the car’s wheels by a strong spring. In this position the train could not move. If the engineer wanted the train to move, he released compressed air that forced the brakes away from the wheels of all the cars. This allowed the train to move.

This, I think, is extremely clever. Notice if the compressed air tank was empty, or the pressure was too low, or there was a leak in the lines, the train would stop. The brakes would not fail, since all the brakes will be forced against the wheels by the springs.

This system is still in use today. I was once on an Amtrak train that was going from D.C. to Princeton when it just stopped in the middle of nowhere. It was late at night and we all wanted to get home, so someone asked the conductor, as he walked by us, what had happened? He answered in technical jargon:

The choo-choo she no go.

We later found out the train had broken an air hose and all the brakes were pressed on. We sat there for about an hour until they go a new hose and restored the integrity of the air system.

Elevators

Elevators are even older than trains, they may date back to ancient times. Only in the middle of the 1800’s, as tall buildings became possible, did elevator safety become a critical issue. As long as buildings were six stories or less, safety was not a major issue—although I would not want to be in an unsafe elevator even at this low height. However, in order to build tall buildings, elevators needed to be not only be safe, but to appear to be safe. Otherwise, people would be afraid to use them.

In 1853 Elisha Otis solved the safety problem of elevators. He invented a mechanism that would stop a falling elevator, even if its supporting ropes broke. The key was as long as the rope was taut the elevator’s brake was kept in, but if the rope became slack then the brakes would be released and they would stop the fall.

Otis’ brilliant insight was not an instant success. He finally realized a live demonstration of the braking mechanism would be needed to get the public to feel safe. During the first American world’s fair in 1854 Otis built an open elevator shaft. Several times a day he would get on the elevator, be hoisted up, and then cut the rope. Since the shaft was open in front all the spectators could see him do this. As the elevator began to fall, his mechanism would bring him to a safe, if sudden, stop. He is reported to have said each time:

All safe, gentlemen, all safe.

This live demo to thousands eventually made his company a success, and made tall buildings possible.

The General Principle

I think there is a powerful principle in use in both the train and elevator safety systems. They are both designed so that no positive action is required. Instead the safety is built into the physics of the system:

• In the train case: no air in the line, then springs stop the train.
• In the elevator case: no rope holding the elevator up, then brakes spring out and stop the elevator from falling.

The key principle seems to be: do not rely on an action, but on the structure of the system. Make the default, a passive state, a safe state so that when the system fails, it gets to the safe state by default.

I have always liked these systems, and have often wondered if we could use the same type of passive methods to build better computing systems. Could we, for example, make a system that is safe from worm attacks and uses a passive system? Is there a formal model of passive vs active systems that we could use to reason about whether such systems are even possible?

Open Problems

Is there any way to exploit the power of the passive methods used by Westinghouse and Otis to solve computer questions?

A 2010 Algorithm for the Knapsack Problem

An improved exponential time algorithm for the knapsack problem

Nick Howgrave-Graham and Antoine Joux are experts in the area of computational number theory and cryptography.

Today I plan to talk about their new algorithm for the knapsack problem. It is an exponential time algorithm with a much smaller exponent than any previous algorithm. The knapsack problem is one of my favorite problems, and their improvement is clever and surprising.

Climbing Mountains and Proving Theorems

The parallels between climbing great peaks and solving open problems

Edmund Hillary is not a theoretician, but is world renowned for the first successful ascent and descent of Everest. He did this with Tenzing Norgay in 1953.

Today I want to talk about the connection between mountain climbing and solving mathematical problems. By mountain climbing I mean climbing Everest or K2 or one of the dozen other 8,000 plus meter peaks; by solving mathematical problems I mean solving hard open problems.

Happy Birthday to Gödel’s Lost Letter

Happy Birthday

An Educational Extinction Event?

Could universities become extinct in the next twenty-five years?

Bud Peterson is the president of Georgia Tech—he is the boss of the boss of the boss of my boss.

Today I plan to talk about the role of Georgia Tech (GIT) in the world of 2035—that is 25 years from now. Peterson started, right after he arrived at Tech last spring, a project on strategic planning. It is an ambitious strategic planning process that is asking the question: “What should Georgia Tech look like in the year 2035?”

Programming Turing Machines is Hard

Two classic Turing Machine simulation theorems

Patrick Fischer is one of the founders of complexity theory. He played a critical role in starting the field, in proving some of the early results, and in making theory as vibrant an area as it is today. We owe him a great deal of thanks. The picture is of his wife, Charlotte Froese Fischer, who is a research professor of Computer Science—I could not find one of him.

Today I would like to talk about two central results of complexity theory. They are old, they are important, and they have not been improved for years. I believe that the time may be right to finally make progress on them.

Definitions, Definitions, Do We Need Them?

The role of definitions in mathematics and theory

Alfonso Bedoya was not a theoretician, but an actor. He is perhaps most famous for uttering the lines:

“Badges? We ain’t got no badges. We don’t need no badges. I don’t have to show you any stinking badges!”

He played Gold Hat, in the The Treasure of the Sierra Madre.

Today I want to talk about definitions.

Are The Reals Really Uncountable?

A discussion of Cantor’s famous diagonal method

Georg Cantor discovered his famous diagonal proof method, which he used to give his second proof that the real numbers are uncountable. In an earlier discussion I have given the first proof that Cantor discovered years earlier.

Today I want to talk about what I plan to cover this week in my complexity class: the diagonal method of Cantor.

A Limit of First Order Logic

A limit of first order logic concerning function definitions

Sam Buss is a logician who works in proof theory, and is one of the world’s experts on bounded arithmetic. He has proved some quite neat theorems—I will discuss his work in more detail in the future, since proof theory is closely related to the P=NP question.

Today I want to talk about a much simpler problem from logic. I hit upon it while trying to prove a theorem. I failed in proving my theorem—so far at least—but I discovered an interesting limitation of first order logic. This limit is not new, but I do not think it is as widely known as it should be.

A Course on Complexity Theory

What should a course on complexity theory cover?

Alan Cobham is a famous theorist who was a theorist before there was theory. Does that make sense? He is usually credited, along with Jack Edmonds, for creating the most important complexity class—polynomial time. The picture is of Jack, not Alan: there seems to be no picture available of Cobham.

Today I plan to discuss what I should teach in my spring complexity theory class. I would like your input. I will of course teach what polynomial time is.