MHB Proving Undecidability: Reducing H_0 to H_epsilon

  • Thread starter Thread starter mathmari
  • Start date Start date
  • Tags Tags
    Language
AI Thread Summary
The discussion centers on proving the undecidability of the language H_epsilon by reducing H_0 to it. The key argument is that if H_epsilon were decidable, it would imply that H_0 is also decidable, leading to a contradiction. A computable function f is proposed to transform inputs from H_0 to H_epsilon, ensuring that the behavior of a constructed machine M' aligns with the properties of the original machine M. Clarifications are made regarding the definitions of the languages and the roles of inputs, emphasizing the importance of correctly defining machine codes and their relationships in the proof. The conversation concludes with a better understanding of the reduction process and the implications of machine codes in the context of the proof.
mathmari
Gold Member
MHB
Messages
4,984
Reaction score
7
Hey! :o

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)
 
Physics news on Phys.org
I assume that $M_x(w)$ is the result of applying a machine with code $x$ to input $w$.

mathmari said:
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".

mathmari said:
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.

mathmari said:
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$).
 
Evgeny.Makarov said:
I assume that $M_x(w)$ is the result of applying a machine with code $x$ to input $w$.

Yes.
Evgeny.Makarov said:
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)
 
mathmari said:
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$.
 
Evgeny.Makarov said:
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)
 
mathmari said:
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.

mathmari said:
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.

mathmari said:
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$.
 
Evgeny.Makarov said:
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)
 
mathmari said:
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$.
 
Evgeny.Makarov said:
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)
 
  • #10
mathmari said:
$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$.

mathmari said:
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.
 
  • #11
Evgeny.Makarov said:
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)
 
Last edited by a moderator:
  • #12
mathmari said:
Let $w$ be an input for $H_0$.
$H_0$ is a language and not a machine. It does not have input.

mathmari said:
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'$.

mathmari said:
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.

mathmari said:
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.

mathmari said:
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 (*).

mathmari said:
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?
 
  • #13
I got it... Thank you very much! (Smile)
 

Similar threads

Replies
2
Views
2K
Replies
5
Views
2K
Replies
17
Views
4K
Replies
1
Views
1K
Replies
6
Views
2K
Replies
4
Views
2K
Back
Top