Are there any known noncomputability proofs that do not rely on the halting problem?

Question

I have looked around and thought of this for a while, and I have not found or been able to construct any proof that a problem is not decidable, without said proof being fundamentally equivalent to showing that an algorithm for solving the problem yields an algorithm for solving the halting problem. Is anyone aware of an undecidability proof (for a problem, not a theorem) that does not rely on drawing a contradiction through solving the halting problem?

EDIT: I forgot to mention, as became clear in the answer given below, that I am interested in problems of the form "determine if x is a member of S", where S is a recursively enumerable set. The standard proof of the halting problem itself is a diagonal argument, and so other proofs using that technique are likely. However, as far as I know, the technique has not been used on recursively enumerable sets. I work so exclusively with recursively enumerable sets that it did not even occur to me to mention this condition.

Answer 1

No natural example of a noncomputable set of degree strictly below that of the halting problem is known - let alone an r.e. example.

However, it is known that such examples exist, if we drop the "natural" requirement:

There are r.e. sets A, B such that neither is Turing reducible to the other.

This is the Friedberg-Muchnik theorem. Moreover, the proof is constructive. So perhaps that provides an example.

Optimistically, there is always the possibility that such a natural degree exists, which we just don't know about. While this seems extremely unlikely, there's nothing really ruling it out - for example, it's possible that Hilbert's 10th problem, over $\mathbb{Q}$, provides such an intermediate degree! (Over $\mathbb{R}$ it is computable - this is due to Tarski - and over $\mathbb{N}$ it is of course the halting problem in disguise - Matiyasevich/Robinson/Davis/Putnam)

---

On the other hand, there are several results that suggest that there is no natural intermediate degree. For instance, there is no Turing functional $\Phi_e$ which is Turing invariant ($A\equiv_TB\implies \Phi_e^A\equiv_T\Phi_e^B$) and satisfies $X<_T\Phi_e^X<_TX'$ for all $X$.

Moreover, it is conjectured (Martin's conjecture) that every Borel Turing-invariant function is "essentially an iterate of the Turing jump" in a precise sense; and that, under the Axiom of Determinacy, every Turing-invariant function is essentially an iterate of the Turing jump.

Answer 2

Consider the set $S$ of all one-argument integer functions computed by Turing machines under some protocol. (Like “The input and output are in base 2,” etc.) The set of all machines is enumerable, so the subset that calculate integer functions is enumerable. Enumerate $S$, and let $f_i$ be the function calculated by the $i$th machine in $S$. Then

$$g(n) = f_n(n)+1$$ is not computable.