It is well known by now that there exists r.e sets which are not recursive but weaker than the halting problem, yet, no explicit example is known (I think). Are there (mathematical) reasons to believe this is "hard" or even impossible?
To make an analogy, finding a problem which is NP-intermediate would yield a solution to P vs NP, and thus, is probably quite hard, and (if P = NP) not possible. And even for this problem there are some "candidates" like the graph isomorphism problem, or the factoring of primes. Is there any known candidates for an explicit solution to Post's problem?
To put an example, take the famous Post Correspondence Problem (no to be confused with Post's problem in the title), but let's fix the number of tails/dominoes, let us say $n$ of them. It is known that if $n=2$, then the problem becomes decidable, and for $n\geq 5$ the problem was proved undecidable by reducing the Halting problem to it, but as far as I'm aware, it is still open for $n=3,4$: wikipedia article. Could it be that for $n=3$ or $n=4$, the problem would yield an intermediate degree? That is, to be an undecidable problem for which the halting problem cannot be reduced to?
Thanks!