<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2015-10-04T22:30:14.317Z
2015-10-04T22:30:14.317Z
Joe Bebel
<p>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.</p>

<p>My question is, are all languages with Turing degree $\mathbf{0}'$ Turing-reducible to each other in polynomial time?<br>
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?</p>

<computability><reductions><polynomial-time><halting-problem><undecidability>
Polynomial-time reductions between undecidable languages
Andrew
# Polynomial-time reductions between undecidable languages

(Asked by: username_0 on 2015-10-04)

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?

**Tags:** computability, reductions, polynomial-time, halting-problem, undecidability


---

## 1 answers

### Answer by username_1 on 2015-10-04. Score: 7

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.


---

