I have heard that there are sets that are not computable, but are lower in degree than the halting problem.

How does this not contradict Rice's theorem? Are there any concrete examples of such sets?

  • 1
    $\begingroup$ And, as far as I remember, all examples of such sets are constructed for that single purpose, so I don't think you find any "concrete examples" of such sets. (See The Priority Method.) $\endgroup$ – Pål GD Sep 11 at 13:28
  • 1
    $\begingroup$ You should explain why you think there is a contradiction. We have too little information to be able to answer, unless you are willing to accept "Nope, there is no contradiction." $\endgroup$ – Andrej Bauer Sep 11 at 19:05
  • 1
    $\begingroup$ In trying to answer that, I realized why there is no contradiction: Rice's theorem is for predicates on Turing machines - our non-computable set that is lower than the halting set will not be a predicate on Turing machines.. it'll have to be something else. Thanks! $\endgroup$ – rain1 Sep 11 at 20:18

This is not an answer, but way too long to be a comment. I just wanted to cite Robert I. Soare's Recursively Enumerable Sets and Degrees, Chapter V: Simple Sets and Post's Problem.

1: Immune Sets, Simple Sets, and Post's Construction

The only r.e. degrees constructed so far are $\textbf{0}$ and $\textbf{0}'$. Post's Problem was to construct other r.e. degrees, i.e., to construct an r.e. set $A$ such that $\emptyset \lt_\text{T} A \lt_\text{T} \emptyset'$. Post's Program for constructing such a set $A$ was to find some easily definable property on $\overline{A}$ (compatible with $A$ being nonrecursive) which guarantees incompleteness ($K \not\leq_\text{T} A$).

Recall (from Theorem II.4.5) that $K$ (and hence any creative set) has an infinite r.e. set (and therefore infinitely many infinite r.e. sets) contained in its complement. Post's idea for constructing $A$ incomplete was to make $\overline{A}$ sufficiently "thin" with respect to containment of infinite r.e. sets so that $\overline{K}$ could not be Turing reduced to $\overline{A}$.

1.1 Definition. (i) A set is immune if it is infinite but contains no infinite r.e. set.
(ii) A set $A$ is simple if $A$ is r.e. and $\overline{A}$ is immune.

1.2 Proposition. If $A$ is simple then:

(i) $A$ is not recursive;
(ii) $A$ is not creative;
(iii) $A$ is not $m$-complete (i.e., $K \not\leq_m A$).

Proof. (i) $\overline{A}$ cannot be r.e., since otherwise it contains an infinite r.e. set (namely $\overline{A}$).

(ii) The complement of a creative set does contain an infinite r.e. set (by Theorem II.4.5).

(iii) If $K \leq_m A$, then $A$ is creative (by Corollary II.4.8). $\Box$

1.3 Theorem (Post [1944]). There exists a simple set $S$.

Proof. Let $A = \{(e,x) \;:\; x \in W_e \;\&\; x > 2e \}$. Now $A$ is $\Sigma_1$ and hence r.e. Let $\psi$ be any p.r. selector function for $A$ (in the sense of Theorem II.1.6) and let $S = \text{rng}\; \psi$. (Intuitively, enumerate $W_e$ until the first element $\psi(e) > 2e$ appears in $W_e$, and then put $\psi(e)$ into $S$.) The following facts give the simplicity of $S$.

(1) $S$ is r.e. ($S$ is the range or a p.r. function.)

(2) $\overline{S}$ is infinite. To see this, note that $S$ contains at most $e$ elements out of $\{0,1,2,\dots,2e\}$, namely $\psi(0),\psi(1), \dots, \psi(e-1)$. Hence $e + 1 \leq \text{card}(\overline{S} \upharpoonright (2e+1))$, so $\overline{S}$ is infinite.

(3) If $W_e$, is infinite, then $W_e \cap S \neq \emptyset$, because $(e,x) \in A$ for some $x > 2e$ and so $\psi(e)$ is defined and $\psi(e) \in S \cap W_e$. $\Box$

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.