12.4 Post’s Problem

The halting problem shows that some sets are not computable. Turing degrees refine this by measuring how hard such sets are. A natural question arises: is there any degree strictly between computable sets and the halting problem?

Let:

be the degree of computable sets, and:

be the degree of the halting problem.

Post’s problem asks whether there exists a recursively enumerable set $A$ such that:

In words, is there an r.e. set that is noncomputable but still strictly easier than the halting problem?

Why the Question Matters

At first glance, one might expect only two possibilities:

• computable sets
• sets as hard as the halting problem

If this were true, then undecidability would have a simple structure. Every noncomputable r.e. problem would collapse to the same level.

Post suspected that this picture was incomplete. The goal was to understand whether there are intermediate levels of difficulty.

What Makes the Problem Hard

The difficulty lies in two competing requirements.

We want a set $A$ such that:

1. $A$ is not computable:

2. $A$ is not as powerful as the halting problem:

The first condition requires $A$ to encode nontrivial computational content.

The second condition requires $A$ to avoid encoding too much information. In particular, $A$ must not allow us to solve the halting problem.

Balancing these two constraints is subtle.

Positive Solution

The answer to Post’s problem is yes.

There exist recursively enumerable sets with intermediate degrees.

This result was proved independently by Richard Friedberg and Albert Muchnik using what is now called the priority method.

The construction builds a set $A$ step by step, ensuring that:

• $A$ is not computable
• $A$ does not compute the halting problem

This is done by meeting an infinite list of requirements, each of which enforces part of the desired behavior.

Idea of the Construction

The method organizes requirements in a priority order:

Each requirement ensures something about $A$.

Examples:

• ensure $A \neq W_e$ for each computable approximation $W_e$
• ensure no oracle machine using $A$ can decide the halting set

Requirements may conflict. Satisfying one may disrupt another. The priority method resolves conflicts by giving higher-priority requirements the ability to override lower-priority ones.

Lower-priority requirements may be injured and must recover later.

This leads to a controlled, stage-by-stage construction.

Consequences

The solution to Post’s problem shows that the structure of r.e. degrees is rich.

There are infinitely many distinct degrees between:

These degrees are not arranged in a simple chain. Many are incomparable.

So undecidability does not collapse to a single level. There are many distinct levels of unsolvability even within recursively enumerable sets.

Beyond the First Result

The priority method became a central technique in computability theory.

It has been used to construct:

• incomparable r.e. degrees
• minimal degrees
• sets with specific structural properties

The study of these constructions reveals a complex and intricate ordering of degrees.

Post’s problem marks the point where computability theory shifts from classification of computable versus noncomputable into a detailed analysis of the internal structure of noncomputability.