A Post on Post
Emil Post role in shaping modern computational theory
Emil Post was one of founders of the modern theory of computation. He is famous for his own definition of computing based on string rewriting rules, his Post Correspondence Problem, and many other wonderful discoveries, including the notion of many-one reduction.
Today I want to talk about Post, and his great influence on modern complexity theory.
Until the other day I believed Post was a high school teacher most of his career. For me, it was unimaginable how one could turn out brilliant work, as Post did, and have to teach all day, every day.
The correct story, according to the archives at the American Philosophical Society, is Post had an attack of mental illness—manic depression —and lost a university position in the early 1920’s. He then survived by teaching high school in New York City until 1932, when he moved to a position at the City College of New York (CCNY). He stayed there the rest of his career, even though he suffered many further attacks of mental illness. At CCNY his teaching load was high—16 contact hours per week. Yet he continued to do important research and was one of CCNY’s most popular teachers.
The question of high teaching load reminds me how lucky we are, and I wonder what great other results a brilliant mind like Post’s could have achieved in a different environment. Perhaps he could have solved many more problems—unfortunately we will never know.
In the 1980’s Ravi Kannan was being recruited to come to Georgia Tech: this is when Rich DeMillo was first at Tech as a faculty member, before he returned to be the Dean of the College of Computing. Then, Tech was on the quarter system for teaching. During Ravi’s job interview he met various faculty members for the usual 30 minute slots. One slot was a meeting with a faculty member I will call X. During their meeting, Ravi quickly realized he had little in common with X who was working in systems programming. So rather than talk about research he asked X what was the teaching load at Tech? Faculty X answered it was four. Since Ravi was coming from Berkeley where the load was 2-1-1, and they were also on the quarter system, Ravi answered four courses a year sounded fine. Faculty X said it was four courses per quarter. Ravi said, “you mean the load here is 12?” Finally, faculty X said,
“Look, can’t you do arithmetic. The load is 16 courses a year: there are four quarters and four courses a quarter. Four times four is sixteen.”
Ravi left their meeting a bit shocked: 16 courses a year—what a load. Luckily he immediately ran into DeMillo who explained that faculty X was on a different schedule. For research active faculty the load was indeed 2-1-1. Ravi did not come to Georgia Tech: I do not think this was the reason, but who knows.
Post lost an arm as a child and suffered from mental illness as an adult. Yet, he was able to overcome all this and become one of the founders of the theory of computing. There is a wonderful tribute to Post by Martin Davis, here is a comment on Post’s teaching style:
Post’s classes were tautly organised affairs. Each period would begin with student recitations covering problems and proofs of theorems from the day’s assignment. These were handed out apparently at random and had to be put on the blackboard without the aid of textbooks or notes. Woe betide the hapless student who was unprepared. He (or rarely she) would have to face Post’s “more in sorrow than anger look”. In turn, the students would recite on their work. Afterwards, Post would get out his 3 by 5 cards and explain various fine points. The class would be a success if he completed his last card just as the bell rang. Questions from the class were discouraged: there was no time. Surprisingly, these inelastic pedagogic methods were extremely successful, and Post was a very popular teacher.
It would have been an honor to have met Post.
Post proved many beautiful theorems, but perhaps the most important is the classic theorem:
Theorem: A set is recursive if and only if both and are recursively enumerable.
Recall a set is recursive if there is a decision procedure to decide if an is in or not; the set is recursively enumerable (r.e.) if there is a generator that enumerates all the elements
of the set. The generator can generate the elements with repeats and in any order at all. The modern name is computably enumerable (c.e.): my use of the older term is due to my learning the basics of this work many years ago.
You all probably know the proof of this theorem, but here is a sketch just in case you do not recall it: The interesting direction is suppose and are both r.e. Suppose you wish to test whether or not is in . There is a generator for and a generator for . Simulate both generators at the same time: run for one time step, then , and so on. Eventually must be generated by or . If by , then ; if by , then .
What a beautiful proof. This simple result is one of the cornerstones of modern computation theory. It also established a difference between “recursive” and “primitive recursive,” at a time when the latter was argued by some to be the proper notion of computation.
I have often wished we had a similar theorem in complexity theorem. The best we might hope for is what one could call a “Post++ Theorem”:
“Theorem”: A set is in P if and only if both and are in NP.
Many do not believe this, but it could be true. If it were true it would be quite powerful:
- It would give a proof that primality is in P.
- It would also show that linear programming is in P.
- It would break most crypto-systems.
Even though the first two are known now, Post++ would have supplied a proof long ago: for example, it has long been known that primality is in both NP and co-NP. Unfortunately, there does not seem to be a simple proof or even a complex proof of this theorem.
Post gave a landmark address at the American Mathematical Society in 1944, where he helped set the agenda of computability theory for decades. One of the key questions he raised is:
Is there a r.e. set that is not equivalent to the halting problem?
All “natural” problems seemed to be complete, and Post wanted to know if there were sets between recursive and the halting problem with respect to Turing equivalence. This question became known as Post’s Problem.
In an attempt to solve this problem Post, and others, defined a series of properties of r.e. sets. The idea was to find a property so there were r.e. sets with the property, yet such sets could not be equivalent to the halting problem. This was Post’s motivation for defining the notion of simple sets, for example.
All of these attempts failed. Note, it is not hard to define explicitly a set that is harder than the halting problem: Consider the set of all programs so that the Turing machine defines a total function: thus, is in the set if an infinite number of halting problems are all true. This set can be shown to be harder than the halting problem; it is at level of the arithmetical hierarchy.
Solutions to Existence Problems in General
Post’s problem was to construct a set with given properties. Problems of this type abound in mathematics: construct an object X with properties For example, suppose that we want to show there is a function defined on the interval that is continuous but nowhere differentiable. There are at least three approaches:
Explicit Construction Try and define an explicit function that is continuous and yet at every point fails to have a derivative. Using standard functions like: , , , and so on does not work. A function like,
will never solve the problem.
Limit Construction: Try and use a limiting process. This is the way that such functions were first constructed. Karl Weierstrass, the famous analyst, defined as
where , is a positive odd integer, and
He proved this function was continuous and yet had no derivative at any point.
Random Construction: Try and use a random process. Simply selecting a random continuous function works. The problem with this approach is defining rigorously what it means for a continuous function to be randomly selected. Once this was solved by Norbert Wiener this approach showed “most” continuous functions had no derivatives.
Solutions to Post’s Problem
Let’s see how the three approaches worked on Post’s Problem:
Explicit Construction Post tried to define an explicit property to solve his problem. He failed. Many years later, in 1991, Leo Harrington and Robert Soare showed such a property existed.
Limit Construction: The first solutions to Post problem were found—almost at the same time—by Richard Friedberg (in 1957) and Albert Muchnik (in 1956). Curiously, their methods were almost the same, and they used a limiting process. This process is one of the fundamental tools in computability theory—it is called the priority method.
Actually the method is the finite injury priority method. I will explain, at a high level, the method in a future discussion. The critical insight for us is the method constructs the required set as the limit of a series of finite sets. Very similar in spirit to how Weierstrass constructs his function. Take a look at this article by Robert Soare for a detailed description of the problem, and the various theories stemming from it.
Random Construction: I do not know if there are solutions to Post’s Problem based on this approach.
Prove Post “Theorem,” or disprove it. A very interesting question in this area is the question of whether or not there is a nontrivial automorphism of the sets under the Turing equivalence relationship: do the Turing degrees have an automorphism?
Finally, why do open problems stay open for years and then get solved independently at about the same time? The Friedberg-Muchnik resolution of Post’s Problem is just one of the many examples of this behavior. I wonder why this happens. Any ideas?