Richard Stearns (1936-2026)

Richard Stearns (right) and Juris Hartmanis in May 1963. The main theorem from their seminal paper is on the blackboard. Stearns sent Lance this picture to help celebrate the 50th anniversary of their paper.

Richard Stearns died on August 29, 2026.  Readers of this blog probably know him from the Hartmanis-Stearns paper On the computational complexity of algorithms which appeared in Transactions of the American Mathematical Society in 1965, and his paper with F. C. Hennie that gave the still tightest known separation for the deterministic time hierarchy.

The Hartmanis-Stearns paper first defined DTIME(T(n)) and other classes and named our field and this blog.  That paper has been honored in two ways:

1) The paper was one of the reasons Hartmanis and Stearns won the Turing Award in 1993.

2) Lance Fortnow chose that paper as one of his favorites, see here.

--------

In this post we discuss a different great paper by Stearns. First some background.

Consider the following problems.

1) Find a function \(f\) such that:

If \(L\) is a regular language and has an NFA of size \(n\) then it has a DFA of size \(\le f(n).\)

(Size is number of states.)

That one we know: \(f(n)=2^n\) suffices.

2) Find a function \(f\) such that:

If \(L\) has a CFG of size \(n\) then it has a PDA of size \(\le f(n).\)

(We assume the CFG is in Chomsky Normal Form and size is the number of nonterminals.)

That one we know: \(f(n)=n+O(1)\) suffices.

3) Find a function \(f\) such that:

If \(L\) is a regular language and has a CFG of size \(n\) then it has a DFA of size \(\le f(n).\)

Meyer and Fischer showed that \(HALT \le_T f\). Beigel and Gasarch later improved this to \(INF \le_T f \) and showed that was tight.

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

Is there any pair of devices such that the gap is greater than exponential but not undecidable?

Richard Stearns in the paper A regularity test for pushdown machines showed the following:

If L is a reg lang with a DPDA of size n then it has a DFA of size \( \le n^{n^{n^{O(n)}}}\)

The size of a DPDA is the number of states plus stack symbols.

Leslie Valiant in the paper Regularity and related problems for deterministic pushdown automata improved this to:

If L is a reg lang with a DPDA of size n then it has a DFA of size \( \le 2^{2^{O(n)}}\).

which matches a lower bound in the Meyer-Fischer paper. Both Stearns and Valiant's results are interesting since the blow up is greater than exponential but still computable.

What is a Computer?

Ben Brubaker has a new Quanta essay Does Computer Science Need Computers? 

Despite the title (and authors generally don't choose their titles), Brubaker's essay really addresses the question as to whether computer science is about computers. He starts with Dijkstra's apocryphal quote "Computer science is no more about computers than astronomy is about telescopes."

This is the wrong analogy: computers are not the telescopes, they are the stars. You just have to use a broad definition of computer.

The word "computer" goes back to at least 1613. The etymology

1. Latin com- meant “together.”
2. Putāre meant “to reckon” or “calculate”—and originally “to prune” or “clear up.”
3. English added -er, meaning “someone or something that performs an action.”

The word originally meant one who computes, usually referring to a human performing a computational task. Its meaning as a machine didn't come into wide use until the mid-20th century. 

I start off every undergraduate theory class I teach with the question "What is a Computer", even in my Foundations of Complexity posts. After some discussion we end up with a diagram like this.

A Computer

The computer doesn't need to be electrical, mechanical or biological. You can think of the postal service delivering a letter based on an address, an auction arriving at a price, or even a well that draws water as we pull a rope. 

The Church-Turing thesis says the process can always be represented by a Turing machine, and then we are off to the races.

When theoretical computer science stops talking about computing, it just becomes mathematics and no longer computer science. If we want to keep it computer science, we need a computer at the center, some kind of process.

How about the title "Does Computer Science Need Computers?" No, not for electronic computers, though they've become more helpful, especially in this AI era. But doing research in computing is a process in itself. Alan Turing drew inspiration for his machine from thinking about how a mathematician works. So yes, you need a computer for computer science, and a computer for astronomy and every other discipline, even if that computer is just yourself.