turing-reduction Proof: $A = \{(u,v) | T(M_u) \subseteq T(M_v)\}$ by showing $H_0 \leq A$

Question

i have a hard time understand turing-reductions. This is my first exercise without a solution and I don't know wheter this is the proper solution. (The only thing i know for sure is, that A is indeed undecidable.) It may not be a completely formal proof, because my native language is not english, but i tried to be as specific as possible.

Here are some definitions:

• $M_w$ is the corresponding turingmachine to $w \in \mathbb{N}$. So $w$ just a Turingmachine decoded as natural Number. Also known as the Gödel number.
• $H_0 = \{w | M_w \text{ accepts } \epsilon\}$ The Haltingproblem on an empty tape
• $T(M_w) =$ the accepted language of the turingmachine $M_w$

A language A is defined as: $A = \{(u,v) | T(M_u) \subseteq T(M_v)\}$. Here is my attempt to show $H_0 \leq A$:

Construct a turing machine as follows:

$M_{u'}$: READ(x); IF x = $\epsilon$ THEN HALT ELSE infinite loop;

$M_{v'}$: READ(x); ACCEPT;

now i have to show: $w \in H_0 \Rightarrow w \in A$ and $w \notin H_0 \Rightarrow w \notin A$:

$w \in H_0 \Rightarrow M_{u'} \text{ halts} \\ \Rightarrow M_{v'} \text{ accepts too} \\ \Rightarrow T(M_{u'}) = \{\epsilon\} \subseteq T(M_{v'}) = \Sigma^* \\ \Rightarrow w \in A$

$w \notin H_0 \Rightarrow M_{u'} \text{ never halts} \\ \Rightarrow M_{v'} \text{ accepts} \\ \Rightarrow T(M_{u'}) = \emptyset \nsubseteq T(M_{v'}) = \Sigma^* \\ \Rightarrow w \notin A$

Conclusion: A is undecidable, as shown by the reduction. Are there any flaws?

I hope you can help me a little bit. Turing-reductions are such a hard thing for me to understand :(

Thank you!

Answer 1

What you wrote isn't reduction. Turing-reduction from $A$ to $B$ is constructing an algorithm that solves $A$ if we provide it an oracle that solves $B$. So, in your case, we need an algorithm that takes a Turing machine (encoded in some convenient way) and says if it halts on empty input, and we allow this algorithm to ask if some pair $(u, v)$ is in $A$.

So, we are given TM $w$ and we want to know if $\epsilon \in T(M_w)$. It's simple: let $u_0$ be such that $T(M_{u_0}) = \{\epsilon\}$ (machine $M_{u_0}$ accepts $\epsilon$ and nothing else), then $\epsilon \in M_w$ is equal to $T(M_{u_0}) \subseteq T(M_w)$, which in turn equals $(u_0, w) \in A$. Thus, our algorithm to determine if $w \in H_0$ is simple: ask if $(u_0, w)$ is in $A$ - it it is, say $w \in H_0$, otherwise say $w \notin H_0$.