Proving Undecidability: Reducing H_0 to H_epsilon

[mathmari]

Hey!

I want to show that the language $H_\epsilon=\{x \mid M_x(\epsilon )\text{ halts } \}$ is undecidable, by reducing $H_0$ to that.

We have that $H_0=\{x\mid M_x(x)\text{ halts } \}$.

Suppose that $H_\epsilon$ is decidable. Then there is Turing machine that computes this language for every input. That means that it is also computed with input $x$, that means that $H_0$ is then also decidable. Contradiiction.

Is this the correct idea for the proof? (Wondering)

 

[Evgeny.Makarov]

I assume that $M_x(w)$ is the result of applying a machine with code $x$ to input $w$.

Suppose that $H_\epsilon$ is decidable. Then there is Turing machine that computes this language for every input.

I don't understand what you mean by "computes this language for every input".

That means that it is also computed with input $x$

Again, what does it mean that a machine "computes with input $x$"? Also, $x$ is undefined so far. In the preceding definitions $x$ was under a quantifier (e.g., "all $x$ such that $M_x(\epsilon)$ halts). If you are using some concrete $x$, you need to properly introduce it.

that means that $H_0$ is then also decidable.

In view of my remarks above, it is not clear where this conclusion comes from.

You need to create an $m$-reduction (that is, a computable function) $f$ from $H_0$ to $H_\epsilon$ such that
\[
w\in H_0\iff f(w)\in H_\epsilon\qquad(*)
\]
for all words $w$. The proof must describe how $f$ works. In this case, $f$ could take a word $w$ and if $w$ is not a code of any machine, $f$ would return $w$. If $w$ is a code of some machine $M$, then $f(w)$ would return the code of the following machine $M'$. Namely, $M'$ erases its input, writes $w$ on the tape and then passes its control to $M$, that is, it calls $M(w)$ as a subroutine. Now try proving (*) (if I did not make a mistake defining $f$).

 

[mathmari]

I assume that $M_x(w)$ is the result of applying a machine with code $x$ to input $w$.

Yes.

I don't understand what you mean by "computes this language for every input".

I mean that when $H_\epsilon$ is decidable, we have that there is a Turing machine that halts on any input. Is this wrong? (Wondering)

 

[Evgeny.Makarov]

I mean that when $H_\epsilon$ is decidable, we have that there is a Turing machine that halts on any input.

Yes, a machine that decides a language halts on every input. I can also take a machine that immediately halts in the accepting state on every input. It is not clear to me how you use the fact that the machine you have in mind decides $H_\epsilon$.

 

[mathmari]

Yes, a machine that decides a language halts on every input. I can also take a machine that immediately halts in the accepting state on every input. It is not clear to me how you use the fact that the machine you have in mind decides $H_\epsilon$.

I got stuck right now... We suppose that $H_\epsilon$ is decidable. Then there is a Turing machine that halts on every input. In this case the input is $\epsilon$ which is independent from $x$. Doesn't this mean that this Turing machine halts also on the input $e=x$ ? Doesn't this machine decides then the language $H_0$ ? (Wondering)

 

[Evgeny.Makarov]

We suppose that $H_\epsilon$ is decidable. Then there is a Turing machine that halts on every input.

Yes, though you should connect the machine about which you say it exists to $H_\epsilon$. Otherwise it's like saying, "We suppose that $m$ is a composite number. Therefore, there exist two numbers $n$ and $k$". Of course they exist: you can take $n=k=1$; they just don't have any relationship to $m$. Similarly, there exists a Turing machine that halts on every input, namely, a machine that immediately accepts. It just has nothing to do with $H_\epsilon$. What you probably mean is that there is a machine that decides $H_\epsilon$; in particular, as every decider, it halts on every input.

In this case the input is $\epsilon$

There is no "the input". The decider $D$ halts on every input, and it accepts that input if it is the code of a TM that halts on $\epsilon$. Note: $D$ takes codes of machines as input and checks what those machines do when given $\epsilon$ as input.

which is independent from $x$.

I repeat:

Also, $x$ is undefined so far. In the preceding definitions $x$ was under a quantifier (e.g., "all $x$ such that $M_x(\epsilon)$ halts). If you are using some concrete $x$, you need to properly introduce it.

In this case, I don't see what you mean by $x$.

 

[mathmari]

You need to create an $m$-reduction (that is, a computable function) $f$ from $H_0$ to $H_\epsilon$ such that
\[
w\in H_0\iff f(w)\in H_\epsilon\qquad(*)
\]
for all words $w$. The proof must describe how $f$ works. In this case, $f$ could take a word $w$ and if $w$ is not a code of any machine, $f$ would return $w$. If $w$ is a code of some machine $M$, then $f(w)$ would return the code of the following machine $M'$. Namely, $M'$ erases its input, writes $w$ on the tape and then passes its control to $M$, that is, it calls $M(w)$ as a subroutine. Now try proving (*) (if I did not make a mistake defining $f$).

I haven't really understood the machine $M'$. Could you explain it further to me? Why does it erase its input? (Wondering)

 

[Evgeny.Makarov]

I haven't really understood the machine $M'$. Could you explain it further to me? Why does it erase its input?

I have the right to define any machine. Any obligation comes from proving its properties. So the question should not be "Why does it do it?", but "Why does a certain property hold?".

Let $\lceil M\rceil$ denote the code of a machine $M$. The idea is to use $M$ to create a machine $M'$ such that $M(\lceil M\rceil)$ behaves in the same way as $M'(\epsilon)$. The procedure that creates $M'$ from $M$ is the reduction function $f$, i.e., $\lceil M'\rceil=f(\lceil M\rceil)$. Then $\lceil M\rceil\in H_0\iff \lceil M'\rceil\in H_\epsilon$.

 

[mathmari]

Let $\lceil M\rceil$ denote the code of a machine $M$. The idea is to use $M$ to create a machine $M'$ such that $M(\lceil M\rceil)$ behaves in the same way as $M'(\epsilon)$. The procedure that creates $M'$ from $M$ is the reduction function $f$, i.e., $\lceil M'\rceil=f(\lceil M\rceil)$. Then $\lceil M\rceil\in H_0\iff \lceil M'\rceil\in H_\epsilon$.

To clarify something... $H_0$ halts only when the input is the same as the code of the machine but $H_\epsilon$ halts always? (Wondering)

 

[Evgeny.Makarov]

$H_0$ halts only when the input is the same as the code of the machine

$H_0$ is a language. It cannot halt. If $\lceil M\rceil\in H_0$, then $M(\lceil M\rceil)$ halts by definition of $H_0$.

but $H_\epsilon$ halts always?

No. Why don't you check the definition of $H_\epsilon$ again?

I assume $\epsilon$ is the empty word, which is represented by the empty tape.

 

[mathmari]

You need to create an $m$-reduction (that is, a computable function) $f$ from $H_0$ to $H_\epsilon$ such that
\[
w\in H_0\iff f(w)\in H_\epsilon\qquad(*)
\]
for all words $w$. The proof must describe how $f$ works. In this case, $f$ could take a word $w$ and if $w$ is not a code of any machine, $f$ would return $w$. If $w$ is a code of some machine $M$, then $f(w)$ would return the code of the following machine $M'$. Namely, $M'$ erases its input, writes $w$ on the tape and then passes its control to $M$, that is, it calls $M(w)$ as a subroutine. Now try proving (*) (if I did not make a mistake defining $f$).

So, we have the following:

Let $w$ be an input for $H_0$. We construct a Turing machine $M'$.
$M'$ with input $f(w)$, where $f$ does the following:
If $w$ is not a code of a machine, then $f(w)=w$.
If $w$ is a code of a machine, then $f(w)$ is the code of the following machine $M'$:
$M'$ erases its input, writes $w$ and simulates $M$ with input $w$.

I haven't really understood the case when $w$ is not a code of any machine... We have then that the machine $M$ doesn't halt, or not? Does this mean that $M'$ neither halts? (Wondering)

 

[Evgeny.Makarov]

Let $w$ be an input for $H_0$.

$H_0$ is a language and not a machine. It does not have input.

We construct a Turing machine $M'$.
$M'$ with input $f(w)$, where $f$ does the following:

The phrase "$M'$ with input $f(w)$" is incorrect. We are in the process of constructing the reduction $f:\Sigma^*\to\Sigma^*$. To remind, the intended property of $f$ is that it is computable and
\[
w\in H_0\iff f(w)\in H_\epsilon\qquad (*)
\]
In the most interesting case, when $w=\lceil M\rceil$ for some $M$, we have $f(w)=\lceil M'\rceil$. After we describe what exactly $M'$ does, the description of $f$ will be mostly done. So $f(w)$ is not an input to $M'$; $f(w)$ is (the code of) $M'$.

If $w$ is not a code of a machine, then $f(w)=w$.

Yes. This is because if $w$ is not a code of any machine, then $w\in H_0$ is false because the language $H_0$ consists of machine codes only, namely, the codes of those machines that halt when given themselves as input. Therefore, the right-hand sides of (*) must be false as well. The easiest way to define $f$ to achieve this is to also make $f(w)$ not a code of any machine. Then $f(w)\notin H_\epsilon$ because $H_\epsilon$ also consists of machine codes.

If $w$ is a code of a machine

We should call this machine, say, $M$ because later you refer to it. Please pay attention that every entity you use in your proof is properly introduced.

then $f(w)$ is the code of the following machine $M'$:
$M'$ erases its input, writes $w$ and simulates $M$ with input $w$.

Yes. In other words, if $w=\lceil M\rceil$ for some $M$, then $M'$ on any input, including $\epsilon$, behaves as $M(\lceil M\rceil)$. This ensures (*).

I haven't really understood the case when $w$ is not a code of any machine... We have then that the machine $M$ doesn't halt, or not?

If $w$ is not a code if any machine, then what is $M$ in this part of the proof?

 

[mathmari]

I got it... Thank you very much! (Smile)