Computers Don't Want

I read through the new book If Anyone Builds It, Everyone Dies by Eliezer Yudkowsky and Nate Soares. "It" refers to Artificial Super Intelligence (ASI). A very short version of the authors' argument: You can view advanced AI as though it has its own desires and agencies, its needs will be incompatible with those of the human race, and AI has the capabilities to eliminate the humans even without the killer robots.

I have no doubt that a crafty sentient AI hellbent on destroying humanity could do so. But let's look at the first part of the argument, should we reason about AI as though it has agency and preferences? The authors make a subtle argument in their Chapter 3, that while AI doesn't have its own wants and desires, we can reason about AI as though it does. In the following chapters, the authors go all in and think of ASI as though it has preferences and acts in its own self interest.

I think of computing as a Turing machine, a device that follows a set of simple instructions, interacting with input and memory, and producing some output. The machine does not have wants or desires, all it does is follow its instructions.

But we also realize the immense complexity that can arise from such simplicity. We have Rice's Theorem that says we can't understand, in general, anything about a Turing machine's output from the code of the machine. And there's a reason why we can't prove P ≠ NP or even have a viable approach, we have no idea how to bound the complexity of efficient algorithms. But we shouldn't confuse complexity and our inability to understand the algorithm as evidence of agency and desires. Even if AI seems to exhibit goal-oriented behavior, it's a property of its training and not evidence of independent agency. 

I worry less about AI developing its own hostile agency than about how humans will wield it, whether through malicious misuse or misplaced trust. These are serious risks, but they're the kinds of risks we can work to mitigate while continuing to develop transformative technology. The "everyone dies" framing isn't just fatalistic, it's premised on treating computational systems as agents, which substitutes metaphor for mechanism.

Clyde Kruskal talks about his Father Martin on Martin's 100th birthday

Martin Kruskal was born Sept 28, 1925 and passed away on Dec 26, 2006, at the age of 81 (we did two posts for his memorial, here  and here). Today, Sept 28, 2025, is his 100th birthday. His son Clyde Kruskal wrote today's blog post as a tribute to his father.

We note that Clyde did a blog for his Uncle Bill's 100th Birthday, here, and plans on doing one for his Uncle Joe in two years. 

-----------------------------------------------------------------------------------------

My father, Martin Kruskal, was a mathematician and physicist, best known for his early work in plasma physics, the discovery (independently of George Szerekes) of Kruskal-Szerekes coordinates, the modern discovery with Norman Zabusky of solitons, and the discovery with Clifford Gardner, John Greene, and Robert Miura of the inverse scattering transform.  He had an incredible willingness to tackle interesting, seemingly small problems\(-\)some of which later turned out to be highly influential.  Here, in chronological order, is a list of some of his more esoteric and/or less well-known contributions, not necessarily research contributions (besides me).


1. Random Mappings

Renowned mathematicians Nicholas Metropolis and Stanislaw Ulam (inventors of the Monte Carlo method) posed the problem of determining the expected number of components in a random mapping from \(N\)  to \(N\). Framing this as a random graph problem: Construct a graph on \(N\) vertices by choosing, for each vertex \(i\) (from 1 to \(N\)), a random vertex \(j\) (also from \(1\) and \(N\)), and create the undirected edge \((i,j)\). If \(i=j\), no edge is created (or equivalently, a self-loop is created).  The question is: What is the expected number of connected components in such a graph?  In 1954, in his first paper after graduate school, he showed that this value is asymptotically \((1/2)(\ln(2N) + C) + o(1)\), where \(C=0.5772\ldots\) is Euler's constant. For the paper see here.

2. Computer Chess

My father was a strong chess player and, in 1956, arguably became the first person to play a game of chess against a computer.  When I learned about this in junior high school, I figured that this must be his most significant achievement.  Because the MANIAC 1 computer was slow and had little memory, the game was played on a 6×6 chessboard without bishops and simplified rules.  My father gave the computer queen odds. Spoiler alert: He won.  For more details, including the full game, see this explanation on Wikipedia here.


3. The Card Game Delphi

In 1956, Bob Abbott invented Eleusis, a card game involving inductive inference.  While the game itself was highly original, the scoring system was somewhat arbitrary.  In 1962, my father devised the game Delphi, which, according to Martin Gardner, made several important improvements, including a much more logical scoring system.  While it solved the scoring problem, Delphi turned out to be less fun to play than Eleusis.  Later, Bob Abbott created an improved version of Eleusis called New Eleusis, which, unfortunately, still did not completely solve the scoring problem.
For the rules to Delphi, see this article in Denexa Games here.

4. The Kruskal Count

My father invented a card trick, called the Kruskal Count, with the unique characteristic that the magician never touches the deck of cards during the performance.  To make this plausible, he would claim to the audience that he was psychic.  There are various YouTube videos demonstrating and discussing it.  Shortly after devising the trick, my father, brother, and I visited a young married couple.  My father performed the trick several times on the husband, who kept accusing his wife of secretly colluding with him.  She was insulted and kept denying it\(-\)truthfully. Finally my father said to the wife, Well, the cat’s out of the bag.  You have been in on it all along, and you can admit it now. (She hadn’t.) My brother and I (both teenagers) thought it was hilarious; I doubt the couple did.

The trick turned out to have serious applications: According to Wikipedia, the underlying phenomenon has applications in cryptography, code-breaking, software tamper protection, code self-synchronization, control-flow resynchronization, design of variable-length codes and variable-length instruction sets, web navigation, object alignment, and others. There are various YouTube videos demonstrating and discussing it.

The Kruskal Count was featured in an episode of NUMB3RS, which Gasarch blogged about here.

5. Surreal Numbers

My father had a lifelong fascination with infinity starting in childhood, which deepened when he read Donald Knuth’s introductory book on surreal numbers.  For more about his interaction with Knuth after reading the book, see this blog entry here.  Wikipedia provides a concise explanation on my father’s webpage about surreal numbers and his contributions.  The entry highlights important results\(-\)both positive and negative\(-\)by Ovidiu Costin, Philip Ehrlich, and the mathematical logician Harvey Friedman (see here and here for the papers).

Martin's website has the following passage, which captures the issue beautifully.

Surreal numbers, which are defined constructively, have all the basic properties and operations of the real numbers.  They include the real numbers alongside many types of infinities and infinitesimals. Kruskal contributed to the foundation of the theory, to defining surreal functions, and to analyzing their structure.  He discovered a remarkable link between surreal numbers, asymptotics, and exponential asymptotics. A major open question, raised by Conway, Kruskal, and Norton in the late 1970s, and investigated by Kruskal with great tenacity, is whether sufficiently well behaved surreal functions possess definite integrals.  This question was answered negatively in the full generality, for which Conway et al. had hoped, by Costin, Friedman, and Ehrlich in 2015.  However, the analysis of Costin et al. shows that definite integrals do exist for a sufficiently broad class of surreal functions for which Kruskal's vision of asymptotic analysis, broadly conceived, goes through.  At the time of his death, Kruskal was in the process of writing a book on surreal analysis with O. Costin.

6. Alpha-Beta Search

While in graduate school, I came across Donald Knuth and Ronald Moore's paper on alpha-beta search (see here).  They posed the question of what is the expected branching factor in a game tree with \(c\) children per node and depth \(d\), and uniformly distributed values at the leaves.  They gave a partial solution.  Gerard Baudet found a recurrence for this value and improved the bound (see here).  This was the kind of asymptotics that my father excelled at, so I asked him if he could solve the recurrence.  He solved it by finding an asymptotic value for the number of leaves evaluated.  Right after that Judea Pearl published the asymptotic value for the branching factor (see here).

At the time I figured that the original question had been answered by Pearl, so the stronger result was not interesting.  A more mature version of me might have pursued it.  In reality, answering the original question is interesting, but for a number of reasons any further improvement is not particularly interesting, so I was probably right to drop it even if for the wrong reasons.  Unfortunately it was in the file drawer lost during the move to our new building, but if anyone cares I think I remember the exact high order term.

7.  Public Key Crypto

When he learned about public key cryptography, he invented his own system based on quadratic mapping just to understand how it works.  He gave a talk on it in 1983. He showed it to Ron Rivest who said that it was not secure. Oh well.

Self-Driving Cars

A few weeks ago I took an Uber to a regional airport and was picked up by a Tesla. The driver used FSD, so-called Full Self-Driving, never touching the steering wheel during the entire trip. Should you tip a driver who just sits there? In the end I gave my usual tip and five-star rating. I figured the driver had to be there or the car wouldn't drive and he probably ponied up his own money for the FSD. I give five stars to any driver who gets me from point A to point B without major incident. Remember when five stars meant "above and beyond". Grade inflation gets us all.

But you can't tip Waymos. Last fall during a trip to San Francisco, I took my first Waymo ride. At one point a couple of people jaywalked in front of the Waymo and the Waymo promptly stopped. The car behind us started honking. Who are you honking at? It's a Waymo. It did drop me off at the wrong hotel but that's on me, who thought there would be two Hyatt Regency's in San Francisco.

In both cases the driving felt safer than the average Uber driver. It really is safer. About 40,000 people die in human-driven traffic crashes per year in the United States. But even a single accident could be devasting to a self-driving car company so they are designed to drive on the safer side. I have friends who see self-driving as the ultimate safety upgrade, especially as they lose fast reflexes as they age. 

With new technologies (to paraphrase Hemingway), things generally move gradually than suddenly. Waymo and its rivals are expanding into several cities in the US  (but not Chicago 😞) and robotaxis are all over China and across Asia. Cities like Shenzhen and Beijing have thousands of robotaxis operating daily, is the US falling behind? And why are we not seeing plans for self-driving cars in the midwest? Is it the weather, or just the usual blind spot technology companies have to this part of the country? 

Nevertheless, I suspect we'll see the vast majority of ride-share as robotaxis by the end of the decade and cars without a steering wheel soon after that. 

We can find more papers on the web than we used to. Are we reading them?

 

STUDENT: What did you do before the web to find papers?

BILL: We went to the library and copied papers to read later.

STUDENT: Did you read them later?

BILL: Well,  uh,hmm,  ...

BILL to a professor in his 80's: What did you do before copy machines?

PROF: We went to the library, took the journal off of the shelf, and read the article. We may also have taken notes on paper on the article. 

Back to 2025: I do the following sequence of events with a branch point at the end.

1) Get interested in some problem. 

I give an example:

 Rado's Theorem for equations  with a constant. Short summary:

Rado's Theorem: Let \(a_1,\ldots,a_n\) be integers. The following are equivalent

--For all finite colorings of \(N^{\ge 1}\) there is a monochromatic solution to \(\sum_{i=1}^n a_ix_i= 0\)

--Some subset of \(a_1,\ldots,a_n\) sums to 0.  

My interest: What if we look at equations which replace 0 by some other constant? AND what if you just want to look at (say) 2-colorings? 

2)  Assemble a website of papers on the topic.

I assembled a website of papers on the Rado question. I did that. The website is   here. 

3)  I then read the papers and understand them. Or not. 

I intend to do the following: 

a) Read the paper with pen and pad and take notes, draw diagrams, do examples. I may create some  handwritten notes. The benefit of the notes is from making them. The actual notes are terrible. 

b) Type in the notes and while doing that polish them. I might work with a student on this.

c) If needed make slides out of the proof for presentation.

I sometimes go straight from the paper to the slides. I've stopped doing that since it is valuable to first go through the Understanding the proof  phase before going to the Best way to present the proof phase.

----------------------------------------

Step 3 can be a problem. I have many website of papers that I never got around to reading. The key for me is to strike while the iron is hot that is, SOON after assembling the papers READ them.

 For Rado's Theorem with constants I have not gotten around to reading any of the papers yet. 

There is some benefit to having to read a paper in the library since then you actually read it. I am NOT saying  things were better when I was a kid. The lesson is more of how to combine current technology with the helpful constraints of a prior era. 

Another approach: go to the library and look through journals to find something interesting. I've done this a few times with success. I blogged about one of them  here

What is "PhD-Level Intelligence"?

When announcing Open-AI's latest release last month, Sam Altman said "GPT-5 is the first time that it really feels like talking to an expert in any topic, like a PhD-level expert." Before we discuss whether GPT-5 got there, what does "PhD-Level intelligence" even mean?

We could just dismiss the idea but I'd rather try to formulate a reasonable definition, which I would expect from a good PhD student. It's not about knowing stuff, which we can always look up, but the ability to talk and engage about current research. Here is my suggestion.

The ability to understand a (well-presented) research paper or talk in the field.

The word "field" has narrowed over time as knowledge has become more specialized, but since the claim is that GPT-5 is an expert over all fields, that doesn't matter. The word "understand" causes more problems, it is hard to define for humans let alone machines.

In many PhD programs, there's an oral exam where we have previously given the candidate a list of research papers and they are expected to answer questions about these papers. If we claim a LLM has "PhD-level" knowledge, I'd expect the LLM to pass this test.

Does GPT-5 get there? I did an experiment with two recent papers, one showing Dijkstra's algorithm was optimal and another showing Dijkstra is not optimal. I used the GPT 5 Thinking model and GPT 5 Pro on the last question about new directions. A little more technical answers than I would have liked but it would likely have passed the oral exam. A good PhD student may work harder to get a more intuitive idea of the paper in order to understand it, and later on extend it.

You could ask for far more--getting a PhD requires significant original research, and LLMs for the most part haven't gotten there (yet). I've not had luck getting any large-language model to make real progress on open questions and haven't seen many successful examples from other people trying to do the same. 

So while large-language models might have PhD-level expertise they can't replace PhD students who actually do the research.

``I'm on vacation so I won't be checking email'' will sound funny soon. Maybe it already does.

 "I'll be on vacation so I won't be checking email.''

"I can't be at the meeting since I will be out of town''

Technology has made it so that:

a) You really CAN get email when you are on vacation.

b) You really CAN go to a meeting if you are out of town (if the meeting is on Zoom which is becoming more and more common).  (My proofreader tells me that Zoom is spelled with a capital Z.  I did not know that! The phrase I  Googled is formally correct, though I googled is acceptable. I have never seen anyone say or write I Binged  or I binged  for searching, though I have seen I binged watched Babylon Five  for example.  I have never seen  I Yahooed or I yahooed  for search or for any other reason. Fun fact: the term Yahoo was coined by Jonathan Swift for use in the book Gulliver's Travels.) 

Caveats:

1) You are on vacation! You DO NOT WANT to answer email!

2) You are out of town at a conference and the meeting is at the same time as a talk you want to go to.

3) There are too many meetings so it's good to have an excuse to not go to some. 

Personal:

This is one issue where I may be LESS of a Luddite than Lance:

When Lance is on vacation, he DOES NOT get email.

When I am out of town, I DO get email, and respond to it. This first struck me when I was on a riverboat cruise in France and I got an email from my chairman asking if I would be on some committee (I said yes).  I was more `in contact' than people on campus who don't respond to email. 

How we talk about things: My advisor told me he would be giving a talk in Zurich. I azoomed he meant a talk on Zoom. He actually meant in person. Fortunately it was recorded so I didn't have to get up at 5:00 a.m.  to see it. (My spellcheck thinks azoomed is not a word. It is correct. For now.)

Is the Prob Method `Just Counting'- I say no and HELL NO

(After I wrote this post Lance tweeted a pointer to a great talk by Ronald de Wolf with more examples, and also examples of quantum proofs, see here.)

I was teaching the prob method for lower bounds on Ramsey Numbers (see my slides here).

As often happens, a student said:

That's not a new technique--- you're just counting.

My response

1) For this example, it can be rephrased as counting, but there is no advantage in that. 

2) There are other examples where either 

a) You could rephrase it as counting but it's MUCH EASIER to use probability, or

b) You really CANNOT rephrase as counting.

And I came prepared-I presented the following result (see my slides here):

Theorem: Let \(G\) be a graph on \(n\) vertices where every vertex has degree \( \ge d \). Then \(G\) has a dominating set of size 

\( \le n \frac{\ln(d+1)+1}{d+1} \). 

The proof uses that \( E(X+Y)=E(X)+E(Y) \). I cannot see a way to make the argument into a counting argument. Clearly 2a is true. It may even be that 2b is true, though that would be hard to formalize.

The student admitted that yes, the Dom Set Theorem either could not be rephrased as a counting argument or it would be hard to do so. 

Can you make it into a counting argument? Would you want to bother? 

A Restless Soul

When I first became a professor I had it all planned out, I would do research, teach and supervise students, get tenure and do more research, teach more courses, and supervise more students for the rest of my life. But once I got tenure, instead of feeling very excited, I felt kind of depressed. I achieved the main goal I put out for myself. Would I really just do the same stuff for the rest of my career?

I even went to a career counselor who gave me a personality test. I'm a classic INTJ, a perfect fit for a scientific researcher. But I just couldn't keep doing the same and tried to mix it up in different ways. I had children, did a sabbatical in Amsterdam, changed jobs multiple times. A colleague called me "a restless soul."

I took service roles in the field, started this blog, wrote survey articles and a popular science book. In my research for a while I kept doing complexity though trying to focus on applying it to other disciplines such as economics. But I found myself often working on problems that few others cared about.

Eventually I became a department chair and a dean, during an incredible transformation in computing as we moved towards the data-driven future we now inhabit. Now that I've returned to the professoriate I lack the excitement and probably the skills to go back to complexity, which has become more of a mathematical field mostly ignoring the changes we've seen in computing.

In an interview for an administrative job I did not get, I gave a vision talk emphasizing growth and impact. Afterwards when I met with the faculty in small groups, one of them, a CS theorist whom I’ve known for decades, looks at me and says “You’ve changed". Yes. And they hadn't. Two responses to the same restlessness, perhaps. Or maybe they were never restless at all.