Polynomial-time reductions between undecidable languages

Question

The Turing degree $\mathbf{0}'$ is defined as all languages Turing-equivalent to the halting problem. In fact any recursively enumerable language is polynomial-time reducible to the halting problem.

My question is, are all languages with Turing degree $\mathbf{0}'$ Turing-reducible to each other in polynomial time?
If not, can the fastest reduction between two $\mathbf{0}'$ languages get arbitrarily slow, and are there known subsets of $\mathbf{0}'$ that are polynomial-time reducible to each other?

Answer 1

Gödel's incompleteness theorem can be thought of as a reduction from the Halting problem to the language $\langle \varphi \mid \varphi \text{ is a true sentence in number theory}\rangle$, and a careful analysis of the running time would show that it is indeed a polynomial time reduction.

Not every such reduction is polynomial time, however. You can observe that a reduction from the Halting problem $\langle i \mid TM_i \text{ halts on input } i\rangle$ to the unary language $\langle 1^i \mid TM_i \text{ halts on input } i\rangle$ has exponential blowup in instance size.