

Gödel's Lost Letter and P=NP
source link: https://rjlipton.wpcomstaging.com/2010/03/23/its-ada-lovelace-day/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

It’s Ada Lovelace Day
This is my contribution to Ada Lovelace Day
Ada Lovelace is, perhaps, the world’s first programmer of an actual computer. Others wrote about algorithms much earlier—think Euclid and the famous GCD algorithm—but she wrote a program for a specific computing machine. The machine was Charles Babbage’s Analytic Engine, and her notes look like a program to most.
Today I plan on joining over a million other bloggers in discussing women in science, and more specifically computing. The event is named after Ada Lovelace, and is happening all over the web.
Okay, I exaggerated about the number of bloggers, it is closer to 100,000 than a million—actually it is closer to 1,700. The number is not important; what is important is: we need more women administrators, educators, and researchers in all areas of computing. Further, more women who already have done great work in computing need to be recognized and given the awards and accolades they deserve. This has not always happened.
I am honored to be a tiny part of this special day, and I hope I can help in some way to make the event a success.
What To Do?
I am honestly unsure what I should do. For starters I am not a woman, and cannot really understand their issues. But, I have been in the computing field for over thirty years and perhaps I can add some small insights. I will try.
When I was first at Princeton we worked very hard to hire Andrea LaPaugh from MIT, where she got her Ph.D. We were successful, and for quite a while she was the only woman in all of engineering at Princeton. Later, she been the first tenured woman in engineering at Princeton. The balance is not perfect now, but I am happy to say today she is not the only tenured professor in engineering.
One day I was talking with a colleague from another engineering department. He asked me, “How many women did we have in Computer Science?” I immediately answered one—Andrea. Then, I asked the obvious question, “How many do you have in your department?” My colleague thought a long time—I guessed he must be adding up women faculty. Finally he said, “None.”
I am telling this story to show how subtle the issues can be concerning women in science. I gave him a very hard time: I said, you can take a long time to add up the cardinality of a big set, but you cannot take any time to figure out the cardinality of the empty-set. What was he thinking?
The Two Rule
One rule is the two rule. I learned this rule from my wife, Judith Norback, who is a Ph.D in psychology from Princeton. Often in an attempt to create balance—especially in academia—one woman will be placed on each committee. A woman. One. It is good to have women on committees, but putting one on does not usually work well.
The difficulty is a lone person on any committee is hard pressed to speak out and really make a difference. A lone person of any minority—the principle is the same for other minorities—is not in general the right choice. There are exceptions to this rule, but studies show one person, from a minority, is not nearly as effective as two. This is the rule of two. If possible always place two women on a group or a committee. They will be immensely more effective, if there are two.
Of course in order to make this happen the academic organization needs to have at least two women—another argument for more diversity. I do not claim to completely understand the reason the “two rule” works, but it does. Try it.
The Out Rule
Another rule is the out rule. This I learned from long experience watching fellow computer scientists operate—especially in academia. In the old days when wagon trains were attacked, they were taught to “circle the wagons.” In computer science we still do this, as do most other areas of science and academia.
However, in computer science the joke—unfortunately all too true—is we shoot the wrong way. We shoot in, not out. Hence, the rule of out: when attacked remember to shoot out, not in toward each other.
With all due respect, I have long noticed women on various committees often ignore this simple rule. They shoot in toward their fellow women. I have been on many committees of all kinds—award, hiring, program, and other types—and have noticed the women on the committee are often the hardest on women candidates. I have often argued for a women candidate for something, and noticed the other faculty were generally supportive. However, the women faculty in the room would frequently agree with me on the big points, yet attack the candidate on some minor points. Do not shoot in, shoot out.
I am not arguing for a decrease in standards. Never. I am arguing for both male and female faculty to be sure they are as objective as possible. I certainly am far from perfect, but I do think more attention should be paid to being aware of the out rule.
The Zero Rule
I am trying to be constructive and not writing a “moral with a tale,” but one last rule is critical in my mind. The zero rule is just this: there must be zero—no—tolerance for any jokes, comments, stories, of any kind that put down women. I have heard many of them over the years, and have always immediately complained about them. I believe such statements cause many women to go into other areas of science. We must be intolerant of any comments of this kind.
Ada As The First Programmer
It seems to me clear Lady Lovelace was more than the first programmer: she had great insight into what a computing device could or could not do. Here is a direct quote from her—it could have been written the other day. It would be interesting to see what she would think about computing today—she wrote this in 1842.
It is desirable to guard against the possibility of exaggerated ideas that might arise as to the powers of the Analytical Engine. In considering any new subject, there is frequently a tendency, first, to overrate what we find to be already interesting or remarkable; and, secondly, by a sort of natural reaction, to undervalue the true state of the case, when we do discover that our notions have surpassed those that were really tenable.
The Analytical Engine has no pretensions whatever to originate anything. It can do whatever we know how to order it to perform. It can follow analysis; but it has no power of anticipating any analytical relations or truths. Its province is to assist us in making available what we are already acquainted with. This it is calculated to effect primarily and chiefly of course, through its executive faculties; but it is likely to exert an indirect and reciprocal influence on science itself in another manner. For, in so distributing and combining the truths and the formula of analysis, that they may become most easily and rapidly amenable to the mechanical combinations of the engine, the relations and the nature of many subjects in that science are necessarily thrown into new lights, and more profoundly investigated. This is a decidedly indirect, and a somewhat speculative, consequence of such an invention. It is however pretty evident, on general principles, that in devising for mathematical truths a new form in which to record and throw themselves out for actual use, views are likely to be induced, which should again react on the more theoretical phase of the subject. There are in all extensions of human power, or additions to human knowledge, various collateral influences, besides the main and primary object attained.
To really appreciate her brilliant mind, read all her comments here. This is the front piece to the document:
Open Problems
The main open problem is continue to try and increase the number of women in all aspects of science, especially computing. I think there are already many good ideas on how to do this—perhaps what we need is to execute the best of these ideas. In any event have a happy Ada Lovelace Day. It would have been a great privilege to have met her.
Like this:
Recommend
-
12
Quantum Supremacy and Complexity April 22, 2016 An AMS article by Gil Kalai updates his skeptical position on quantum computers Gil Kalai is a popularizer of mat...
-
23
Summer Reading in Theory July 16, 2019 Some formative books in mathematics and computing theory Norman Biggs is the author of the wonderful
-
10
Art, history, and controversy Jemma Lorenat is an assistant professor at Pitzer College in Los Angeles. She teaches and does research on the history of mathematics. Today I thoug...
-
13
P < NP In Our Stockings? December 24, 2020 Brute force wins—sometimes Santa Claus is on the way to visit those of us who have been good. Tonight is Chr...
-
11
A Vast and Tiny Breakthrough October 26, 2020 Christofides bound beaten by an epsilon’s idea of epsilon Anna Karlin, Nathan Klein, and Shayan Oveis Gharan have mad...
-
14
Complexity 2022 July 18, 2022 Weaving patterns of proof and the accepted papers for this week’s conference
-
5
Legal Complexity September 4, 2022 Formal logical methods may be needed to represent the Donald Trump documents case Monica Palmirani is a
-
8
The Gift of Nonconstructivity — Gödel’s Lost Letter and P=NP curi56
-
13
Traces of strings, plus ways of tracing accepted papers Anindya De was at Northwestern University and is now at the University of Pennsylvania—see here. ...
-
8
STOC 2023 is the 55th Annual ACM Symposium on Theory of Computing. It will be held on June 20-23, 2023 in Orlando, Florida. Perhaps the best paper ever at STOC was by Stephen Co...
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK