The Right Stuff of Emptiness

How ∅ versus {ε} can be a life-and-death difference

Cropped from source

Jeff Skiles was the co-pilot on US Airways Flight 1549 from New York’s LaGuardia Airport headed for Charlotte on January 15, 2009. The Airbus A320 lost power in both engines after striking birds at altitude about 850 meters and famously ditched in the Hudson River with no loss of life. As Skiles’s website relates, he had manual charge of the takeoff but upon his losing his instrument panel when the engines failed,

“Captain Chesley Sullenberger took over flying the plane and tipped the nose down to retain airspeed.”

Skiles helped contact nearby airports for emergency landing permission but within 60 seconds Sullenberger and he determined that the Hudson was the only option. His front page does not say he did anything else.

Today we tell some stories about the technical content of forms of emptiness.

I am teaching Buffalo’s undergraduate theory of computation course again. I like to emphasize early on that an alphabet need not be only a set of letter or digit symbols, even though it will be or or similar in nearly all instances. The textbook by Mike Sipser helps by having examples where tokens like “REAR” or “<RESET>” denoting actions are treated as single symbols. An alphabet can be the set of atomic actions from an aircraft or video game console. Some controls such as joysticks may be analog, but their output can be transmitted digitally. What’s important is that any sequence of actions is represented by a string over an appropriately chosen alphabet.

I go on to say that strings over any alphabet can be re-coded over . Or over ASCII or UTF-8 or UNICODE, but those in turn are encoded in 8-bit or 16-bit binary anyway. I say all this justifies flexible thinking in that we can regard as “the” alphabet for theory but can speak in terms of a generic char type for practice. Then in terms of the C++ standard library I write alphabet = set<char>, string = list<char>, language = set<string>, and class = set<language>. I go on to say how “” abbreviates object-oriented class notation in which set<State;> Q; and alphabet Sigma; and State start; and set<State> finalStates; are fields and delta can be variously a map or a function pointer or a set of tuples regarded as instructions.

Emptiness

In the course I’m glad to go into examples of DFAs and NFAs and regular expressions right away, but reaching the last is high time to say more on formal language theory. I’ve earlier connected and to Boolean or and and, but concatenation of languages needs explaining as a kind of “and then.” One point needing reinforcement is that the concatenation of a language with itself, written or , equals , not . The most confusion and error I see, however, arises from the empty language versus the empty string (or in other sources).

I explain the analogy between multiplication and concatenation although the latter is not commutative, and that the operation between languages naturally “lifts” the definition of for strings. I then say that behaves like and behaves like under this analogy, but I don’t know how well that catches on with the broad range of students. So not always but a few times when lecture prep and execution has left 6–10 minutes in the period, I wrap a story into an example:

Let denote the alphabet of controls on a typical twin-engine Cessna business jet. I will define two languages over this alphabet—you tell me what they are:

1. represents an appropriate sequence of actions for the co-pilot to initiate if 1 engine fails at 100 meters altitude, and with there is a non-miraculous chance of saving the plane.

2. represents an appropriate sequence of actions for the co-pilot to initiate if 2 engines fail at 2000 meters altitude, and with there is a non-miraculous chance of saving the plane.

After carefully writing this on board or slide, I say, “you have enough information to answer this; it could be a pop quiz.” I let 15–20 seconds go by to see if someone raises a hand amid bewildered looks in silence, and then I say, “OK—I’ll tell a real-life story.”

The Story

My father Robert Regan was a financial reporter specializing in aluminum and magnesium. Once in the 1970s he covered a meeting of aluminum company executives in North Carolina. One of the executives failed to show for the first evening, and the news of why was not conveyed until he appeared in splint and bandages at breakfast the next morning.

He told how his twin-engine crew-of-two jet had lost all power immediately after takeoff. With no time or room for turning back, the pilot spotted the flat roof of a nearby bowling alley and steered for it as little he could. The jet pancaked on the roof and bounced into the mercifully empty parking lot. Everyone survived and could thank the way the force of impact had been broken into two lesser jolts. The end of the executive’s tale and interaction with my father in the breakfast-room audience went about as follows:

Exec: I have never seen such a great piece of quick thinking and calm control in my lifetime of business, to say nothing of the sheer flying skill. That pilot ought to get a medal.

RR: The co-pilot deserves a medal too.

Exec: Why? He didn’t do anything.

RR: Exactly.

Maybe only then the significance of the words “appropriate for the co-pilot to initiate” in my definitions of and dawns on the class, as well as the Boolean and. The appropriate string is in both cases: the co-pilot should not “initiate” any actions.

As witnessed by the stories above, in the case of there is a good chance even if both engines fail, so the second clause is certainly satisfied. Thus . Perhaps the example of Sullenberger and Skiles at 850 meters makes it too pessimistic for me to say is a goner at 2,000 meters, but the point of the example is that an unsatisfied conjunct in a set definition makes the whole predicate false even if the part depending on is true. Thus the intent is .

There it is: the difference between and can be one of life and death. How much the story helps burnish the difference is hard to quantify, but at least much of the class tends to get a later test question involving this difference right.

Zero to the Zero

Whether I tell the story or not, I next have to convey why turns around and becomes . I say that the convention helps make the power law true for all , but why is this law relevant for ? Why do we need to define anyway, let alone stipulate that it equals ?

If I say it’s like in arithmetic, the students can find various sources saying is a “convention” and “controversial.” So I say it’s like the convention that a for-loop

for (int i = 0; i < n; i++) { ... }

naturally “falls through” when . Even if the loop is checking for conditions that might force your code to terminate—and even if the body is definitely going to kill your program on entry—if the loop executes 0 times then you’re still flying. It’s a no-op represented by rather than a killing , so the whole flow-of-control analysis is

Thus it comes down to the logical requirement that a universally quantified test on an empty domain defaults to true. Not just they but I can feel this requirement better in programming terms.

To go deeper—usually as notes for TAs if time permits in recitations or as a note in the course forum—I connect to logic and relations. I’ve defined a function from a set to a set as a relation that satisfies the test

Now we can ask:

Is the empty relation a function?

There’s an impulse to answer, “of course it isn’t—there aren’t any function values.” But when the test becomes a universally quantified formula over an empty domain, and so it defaults to true. Thus counts as a function regardless of what is, even if too.

Because , the only possible relation on is . So the cardinality of the set of functions from to is . The notation for the set of functions from a set to a set , namely , is motivated by examples like being the set of binary functions on . There are such functions, and in general

With all this gives . Thus and are needed for the universe of mathematics based on sets and logic to come out right.

Emptiness and Type

The same analysis shows that an empty relation on a nonempty domain is not a function. This means that even when stuff is empty, the type signature of the stuff matters too. One student in my course told me last week that the realization that “empty” could come with a type helped him figure things out.

Real advances in mathematics have come from structure channeling content even when the content is degenerate or empty. There are more hints of deeper structure even in basic formal language theory. I generally encourage the notation for regular expressions over Sipser’s in order to leverage the analogy between concatenation and multiplication, even though equals not any notion of “.” The property does not hold over any field, except for the possibility of the “field of one element” which we discussed some time back.

Now consider the suggestive analogy

What substance does it have beyond optics? The latter equation holds provided even over the complex numbers, and also holds in a sense for . The analogy , works in both equations to yield and . We then find it disturbing, however, that substituting , fails because which is not infinite.

Does it really fail? Perhaps it succeeds in some structure that embraces both equations—perhaps involving ? Our earlier post and its links noted that has an awful lot of structure and connections to other parts of mathematics despite its quasi-empty content.

We know several ways to build a universe on emptiness. In them the supporting cast of structure rather than is the real lead. The new actor in town, Homotopy Type Theory, aims to find the right stuff directly in terms of types and the identity relation and a key notion and axiom of univalence. As related in a recent survey by Álvaro Pelayo and Martin Warren in the AMS Bulletin, the object is to make and other sets emerge from the framework rather than form its base.

Open Problems

Does handling and right take care of everything?

Ada the Amplifier

Plus updated links to our Knuth and TED talks

Ada Lovelace was nuts. Some have used this to minimize her contributions to the stalled development of Charles Babbage’s “Analytical Engine” in the 1840s. Judging from her famously over-the-top “Notes” to her translation of the only scientific paper (known as the “Sketch”) published on Babbage’s work in his lifetime, we think the opposite. It took nuttily-driven intensity to carry work initiated by Babbage several square meters of print beyond what he evidently bargained for.

This month we have been enjoying Walter Isaacson’s new book The Innovators, which leads with her example, and have some observations to add.

Still A Brilliant Idea

An apology and correction

Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith are the inventors of differential privacy, as formulated in their 2006 paper “Calibrating Noise to Sensitivity in Private Data Analysis,” in the proceedings of the 2006 Theory of Cryptography Conference.

Today Ken and I want to talk about differential privacy again.

Cynthia Dwork and a Brilliant Idea

Differential Privacy

Taekwondo source

Cynthia Dwork is a computer scientist who is a Distinguished Scientist at Microsoft Research. She has done great work in many areas of theory, including security and privacy.

Today Ken and I wish to talk about the notion of differential privacy and Dwork’s untiring advocacy of it.

Where Hard Meets Easy

Some hard to compute functions are easy modulo a number

Georgia Tech source

Joseph Ford was a physicist at Georgia Tech. He earned his undergrad degree here in 1952, and after earning his PhD at Johns Hopkins, went to work for two years at Union Carbide in Niagara Falls before joining the University of Miami and then coming back to Tech. He was possibly lured back into academia by considering a paradox studied by Enrico Fermi, John Pasta, Stanislaw Ulam, and Mary Tsingou in the mid-1950s. The paradox is that periodic rather than ergodic motion can often result in complicated systems.

Today we wish to present a simple observation about hard-to-compute functions.

Why is Congruence Hard to Learn?

Gears and rings…

Flickr source:

Denys Fisher was a British engineer and maker of board games and other toys. In 1965 he invented the Spirograph toy. Some speculate that he was influenced by the designs of the artist, composer, and film animator John Whitney, whose opening sequence for Alfred Hitchcock’s 1958 film “Vertigo” is considered the first use of computer graphics in cinema. The Spirograph toy involves drawing with a pen guided by a gear with m teeth going around inside a ring or around a track or other gear with x teeth. The kind of design you get depends on how x relates to m.

Today Ken and I want to talk about a basic notion of mathematics and theory that is simple to define, very useful, and yet seems to be tough for some students to get.

A Computer Chess Analysis Interchange Format

File formats are like watching paint dry…

Source: Chess-programming wiki on Edwards’s “Spector” program.

Steven Edwards is an American computer scientist and chess programmer. Two decades ago he spearheaded the development and adoption of three standards for communicating chess games and their moves.

Today Ken wishes to present a proposed new format for representing computer analysis of chess games and positions.