1
$\begingroup$

Post's problem, posed in 1944 by Post, was to know if there is a recursively enumerable set, which, being undecidable, was not equivalent to the Halting problem under Turing reducibility. While I've seen the proof that such sets exist (the book Gems of Theoretical Computer Science has a chapter on this), the proof works by (a bit artificially) constructing Turing incomparable sets. So far, I haven't seen an example of a concrete "natural" example of an undecidable set below the Halting problem, which I would like to find.

Here are some notes on Post's problem, with a proof idea of its solution.

My first attempt at coming up with such a set would be to consider somethin like A = {BB(n) : n $\in$ Halt}, because, even if I am supplied with A as an oracle, I can't seem to use it to know if n is in Halt without computing BB(n), which is an uncomputable function (the busy beaver function), but I'm a bit stuck trying to just prove that it is undecidable.

So my question is: do you know examples of concrete undecidable sets, with a lower degree of unsolvability than the Hating problem?

Thanks in advance

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

First, let me show that your proposed $A$ is equivalent to the halting problem after all. Let $a_n$ be the $n$th element of $A$ by size; we have $a_n\ge BB(n)$, and so $A$ computes a function dominating $BB$. Since any function dominating $BB$ computes $0'$, we get $A\ge_T0'$. More generally, any infinite subset of $ran(BB)$ will compute $0'$.

In fact, there are currently no known examples of "natural" sets of intermediate degree, let alone r.e. ones. There are also very few candidate examples, and we have general results ruling out any "too-robust" such constructions. For example, see Lachlan, Uniform enumeration operations or Downey/Shore, There is no degree invariant half-jump. I've also written about this in more detail at MSE.

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.