Can the Halting Problem be Reduced to L?

[evinda]

Hello! (Wave)

I want to show that the language $L=\{ n \in \mathbb{N} | T_n(0) \uparrow \}$ is not recursive.

In order to do so, we could reduct the halting problem $H=\{ (n,x) \in \mathbb{N} \times \mathbb{N}^{<\infty} | \text{ with input } x \text{ the machine } T_n \text{ halts} \}$ to $L$. Right?

But how can we reduct the Halting problem to $L$ ? I have no idea... (Worried)

 

[Evgeny.Makarov]

It's better to reduce $H$ to the complement of $L$ or, rather, to $\{n\in\mathbb{N}\mid T_n(0)\downarrow\}$ (it's not exactly the complement of $L$) and then use the closure of decidable languages under complement. Given $(n,x)$, construct a machine $M$ that erases its input, writes $x$ and then behaves as $T_n$. Thus $M$ on any input (including 0) behaves in the same way as $T_n(x)$.

 

[evinda]

It's better to reduce $H$ to the complement of $L$ or, rather, to $\{n\in\mathbb{N}\mid T_n(0)\downarrow\}$ (it's not exactly the complement of $L$) and then use the closure of decidable languages under complement.

Why can we use the closure of decidable languages under complement given that we reduce $H$ to $\{n\in\mathbb{N}\mid T_n(0)\downarrow\}$ and thus the latter is not recursive? (Thinking)

Given $(n,x)$, construct a machine $M$ that erases its input, writes $x$ and then behaves as $T_n$. Thus $M$ on any input (including 0) behaves in the same way as $T_n(x)$.

So we consider the halting problem $H=\{ (n,x) \in \mathbb{N} \times \mathbb{N}^{<\infty}\mid T_n(x) \downarrow\}$ and we construct $M$ such that $M(x) \downarrow$ if $T_n(x) \downarrow$.
So if $T_n(0) \downarrow$ then $M(0) \downarrow$ and so $M$ accepts the language $\{ n \in \mathbb{N} \mid T_n(0) \downarrow \}$.
Thus having used $(n,x)$ of the halting problem we have constructed a machine that accepts $\{ n \in \mathbb{N} \mid T_n(0) \downarrow \}$ and so we have reduced the Halting problem to $\{ n \in \mathbb{N} \mid T_n(0) \downarrow \}$ ? Or have I understood it wrong?

 

[Evgeny.Makarov]

Why can we use the closure of decidable languages under complement given that we reduce $H$ to $\{n\in\mathbb{N}\mid T_n(0)\downarrow\}$ and thus the latter is not recursive?

We can use the closure under complement in any circumstance because it is a true fact. In this case I suggest using it in a proof by contradiction.

So we consider the halting problem $H=\{ (n,x) \in \mathbb{N} \times \mathbb{N}^{<\infty}\mid T_n(x) \downarrow\}$

It is more customary to consider that $H$ contains codes of machines with a single argument: the whole tape content, rather than an arbitrary number of arguments. You may also assume that the argument is a single natural number.

and we construct $M$ such that $M(x) \downarrow$ if $T_n(x) \downarrow$.

No, we construct $M$ such that $M(0) \downarrow$ iff $T_n(x) \downarrow$. You need to reduce $H$ to the language $\{\lceil M\rceil\mid M(0)\downarrow\}$, don't you? Here $\lceil M\rceil$ denotes the code of a machine $M$.

Suppose that you can answer the question whether any machine halts on 0. Then you need to figure out a way to answer the question whether a given machine $N$ halts on a given input $x$. The latter question has to be reduced to the former. So, given $N$ and $x$ you need to construct $M$ such that $N(x)\downarrow\iff M(0)\downarrow$.

So if $T_n(0) \downarrow$ then $M(0) \downarrow$ and so $M$ accepts the language $\{ n \in \mathbb{N} \mid T_n(0) \downarrow \}$.

This makes no sense.

Please see a similar https://driven2services.com/staging/mh/index.php?threads/88672/ and reading recommendations in post #6.

 

[evinda]

We can use the closure under complement in any circumstance because it is a true fact.

I see...

No, we construct $M$ such that $M(0) \downarrow$ iff $T_n(x) \downarrow$. You need to reduce $H$ to the language $\{\lceil M\rceil\mid M(0)\downarrow\}$, don't you? Here $\lceil M\rceil$ denotes the code of a machine $M$.

Suppose that you can answer the question whether any machine halts on 0. Then you need to figure out a way to answer the question whether a given machine $N$ halts on a given input $x$. The latter question has to be reduced to the former. So, given $N$ and $x$ you need to construct $M$ such that $N(x)\downarrow\iff M(0)\downarrow$.

So like that :

Given $(n,x)$, construct a machine $M$ that erases its input, writes $x$ and then behaves as $T_n$. Thus $M$ on any input (including 0) behaves in the same way as $T_n(x)$.

we have constructed $M$ such that $N(x)\downarrow\iff M(0)\downarrow$, i.e. we have reduced the Halting problem to the language $\{n \in \mathbb{N} \mid T_n(0) \downarrow \}$ so the latter is not recursive, right?Suppose that $L=\{ n \in \mathbb{N} \mid T_n(0) \uparrow \}$ is recursive. Then the complement of the language is also recursive. But $\{ n \in \mathbb{N} \mid T_n(0) \uparrow \}^C=\{ n \in \mathbb{N} \mid T_n(0) \downarrow \}$. Contradiction, since we have shown that this language is not recursive.

So like that we have shown that $L$ is not recursive, right?

Please see a similar https://driven2services.com/staging/mh/index.php?threads/88672/ and reading recommendations in post #6.

Opening the link, I get this:

View attachment 5941

 

[Evgeny.Makarov]

we have constructed $M$ such that $N(x)\downarrow\iff M(0)\downarrow$, i.e. we have reduced the Halting problem to the language $\{n \in \mathbb{N} \mid T_n(0) \downarrow \}$ so the latter is not recursive, right?

Yes.

Suppose that $L=\{ n \in \mathbb{N} \mid T_n(0) \uparrow \}$ is recursive. Then the complement of the language is also recursive. But $\{ n \in \mathbb{N} \mid T_n(0) \uparrow \}^C=\{ n \in \mathbb{N} \mid T_n(0) \downarrow \}$. Contradiction, since we have shown that this language is not recursive.

Almost, but $\{ n \in \mathbb{N} \mid T_n(0) \uparrow \}^C=\{ n \in \mathbb{N} \mid T_n(0) \downarrow \}$ does not hold exactly. The left-hand side includes integers that are not codes of any machine, while the right-hand side does not. However, the property of being a code of a well-formed Turing machine is decidable. So if $\{ n \in \mathbb{N} \mid T_n(0) \uparrow \}^C$ is decidable, then so is $\{ n \in \mathbb{N} \mid T_n(0) \uparrow \}^C\cup\{n\in\mathbb{N}\mid n\text{ is not a code of any TM}\}$. And $\{ n \in \mathbb{N} \mid T_n(0) \downarrow \}$ is the complement of that set.

Opening the link, I get this:

Sorry, I meant https://driven2services.com/staging/mh/index.php?threads/19327/.

 

[evinda]

The left-hand side includes integers that are not codes of any machine, while the right-hand side does not.

Could you explain it further to me? I haven't really understood what you mean.

However, the property of being a code of a well-formed Turing machine is decidable.

I am sorry but I haven't understood how you use this statement in this case. (Tmi)

So if $\{ n \in \mathbb{N} \mid T_n(0) \uparrow \}^C$ is decidable, then so is $\{ n \in \mathbb{N} \mid T_n(0) \uparrow \}^C\cup\{n\in\mathbb{N}\mid n\text{ is not a code of any TM}\}$.

If a language is decidable, so is its union with any other language, right?

And $\{ n \in \mathbb{N} \mid T_n(0) \downarrow \}$ is the complement of that set.

Why does this hold?

Sorry, I meant https://driven2services.com/staging/mh/index.php?threads/19327/.

Ok, I will take a look at it in a bit.

 

[Evgeny.Makarov]

Almost, but $\{ n \in \mathbb{N} \mid T_n(0) \uparrow \}^C=\{ n \in \mathbb{N} \mid T_n(0) \downarrow \}$ does not hold exactly. The left-hand side includes integers that are not codes of any machine, while the right-hand side does not.

Could you explain it further to me? I haven't really understood what you mean.

Sorry, what you are asking is too trivial, so I am not sure what you don't understand. If you know the notations like $T_n(x)$ and the set-builder notation, it should be obvious to you. If you need explanation, please explain what exactly you do and don't understand about my statement. Perhaps the misunderstanding lies in the definition of $T_n(x)$.

However, the property of being a code of a well-formed Turing machine is decidable.

I am sorry but I haven't understood how you use this statement in this case.

I am explaining it later in the previous post.

If a language is decidable, so is its union with any other language, right?

No. See problem 3.15 on p. 161 in Michael Sipser, "Introduction to the Theory of Computation", 2nd edition.

So if $\{ n \in \mathbb{N} \mid T_n(0) \uparrow \}^C$ is decidable, then so is $\{ n \in \mathbb{N} \mid T_n(0) \uparrow \}^C\cup\{n\in\mathbb{N}\mid n\text{ is not a code of any TM}\}$. And $\{ n \in \mathbb{N} \mid T_n(0) \downarrow \}$ is the complement of that set.

Why does this hold?

Every natural number falls in exactly one of the following classes:

1. a code of a machine that does not halt on 0,
2. not a code of any machine,
3. a code of a machine that halts on 0.

 

[evinda]

Sorry, what you are asking is too trivial, so I am not sure what you don't understand.

Could you give me an example of a natural number that belongs to the left-hand side but not to the right-hand side?

No. See problem 3.15 on p. 161 in Michael Sipser, "Introduction to the Theory of Computation", 2nd edition.

I don't have the second edition in english. I will look for it and will read it...

Every natural number falls in exactly one of the following classes:

1. a code of a machine that does not halt on 0,
2. not a code of any machine,
3. a code of a machine that halts on 0.

I see...

 

[Evgeny.Makarov]

Could you give me an example of a natural number that belongs to the left-hand side but not to the right-hand side?

I have already answered this question in the following quote, and I'd rather you explain what you don't understand about it, especially the last sentence.

Almost, but $\{ n \in \mathbb{N} \mid T_n(0) \uparrow \}^C=\{ n \in \mathbb{N} \mid T_n(0) \downarrow \}$ does not hold exactly. The left-hand side includes integers that are not codes of any machine, while the right-hand side does not.

People who ask and people who respond both have to work. So far for this particular question you have only been asking and have not provided any reason for why you think this claim is difficult. Please convince me that it is. I think that it is obvious to anyone who knows the set-builder notation, the definition of $T_n(x)$ and the definition of set complement.

I don't have the second edition in english.

This particular problem says that the union of two decidable languages is decidable. However, the fact that both languages are decidable is essential. This fact is pretty obvious: if you have two assistants who are able confirm or deny two statements, then you should be able to confirm or deny the disjunction of these statements. If, on the other hand, one of the assistants may take indefinite and possibly infinite time to confirm or deny her statement, then you may not be able to resolve the disjunction, either.

 

[evinda]

Almost, but $\{ n \in \mathbb{N} \mid T_n(0) \uparrow \}^C=\{ n \in \mathbb{N} \mid T_n(0) \downarrow \}$ does not hold exactly. The left-hand side includes integers that are not codes of any machine, while the right-hand side does not.

I think that I got it know. We know that the set $\{ n \in \mathbb{N} \mid T_n(0) \uparrow \}^C$ contains integers that are not codes of a Turing machine that halts on $0$. But it contains also integers that are not codes of any Turing machine. Although the integers that belong to the set $\{ n \in \mathbb{N} \mid T_n(0) \downarrow \}$ have to be codes of Turing machines and especially of Turing machines that halt on $0$.

However, the property of being a code of a well-formed Turing machine is decidable.

Given an integer $n$, why can we determine in finite steps if it is the code of a Turing machine, given that there are infinite Turing machines?

 

[Evgeny.Makarov]

Almost, but $\{ n \in \mathbb{N} \mid T_n(0) \uparrow \}^C=\{ n \in \mathbb{N} \mid T_n(0) \downarrow \}$ does not hold exactly. The left-hand side includes integers that are not codes of any machine, while the right-hand side does not.

I think that I got it know. We know that the set $\{ n \in \mathbb{N} \mid T_n(0) \uparrow \}^C$ contains integers that are not codes of a Turing machine that halts on $0$.

You probably mean "that are not codes of a Turing machine that diverge on $0$".

But it contains also integers that are not codes of any Turing machine. Although the integers that belong to the set $\{ n \in \mathbb{N} \mid T_n(0) \downarrow \}$ have to be codes of Turing machines and especially of Turing machines that halt on $0$.

Didn't I say this very things a couple of times?

Given an integer $n$, why can we determine in finite steps if it is the code of a Turing machine, given that there are infinite Turing machines?

This requires some experience with constructing Turing machines. After making more and more complex machines, you realize that you can perform all reasonable arithmetic, you can determine if a given number is a code of a sequence, if that sequence consists of valid commands, i.e., 5-tuples $(q_1,a,q_2,b,m)$ where $q_i\in Q$, $a,b\in\Sigma$ and $m\in\{\leftarrow,\rightarrow\}$ and so on. After a while you realize that what can be done on in Java or C can be done by a Turing machine. And one can definitely write a Java program that determines if a string (or its integer code) is a sequence of valid commands.

This is similar to compilers: they can determine if a given text is a well-formed program without syntactic errors. But no compiler can determine if a given program halts, or divides by 0, or accesses an index beyond array boundary, etc.

 

[evinda]

You probably mean "that are not codes of a Turing machine that diverge on $0$".

Didn't I say this very things a couple of times?

Yes, I needed longer time to realize what you meant.

This requires some experience with constructing Turing machines. After making more and more complex machines, you realize that you can perform all reasonable arithmetic, you can determine if a given number is a code of a sequence, if that sequence consists of valid commands, i.e., 5-tuples $(q_1,a,q_2,b,m)$ where $q_i\in Q$, $a,b\in\Sigma$ and $m\in\{\leftarrow,\rightarrow\}$ and so on. After a while you realize that what can be done on in Java or C can be done by a Turing machine. And one can definitely write a Java program that determines if a string (or its integer code) is a sequence of valid commands.

This is similar to compilers: they can determine if a given text is a well-formed program without syntactic errors. But no compiler can determine if a given program halts, or divides by 0, or accesses an index beyond array boundary, etc.

Ah I see... Given the definition of a Turing machine:

View attachment 5997

and given a code $n$ , a Turing machine can determine whether the above properties are satisfied by $T_n$ or not. Right?

 

[Evgeny.Makarov]

Given the definition of a Turing machine:

and given a code $n$ , a Turing machine can determine whether the above properties are satisfied by $T_n$ or not. Right?

I am not sure what exactly you mean by "the above properties are satisfied by $T_n$". The photo lists a definition and not properties. Further, $T_n$ is a function that takes an input string and maps it to the output of the machine with code $n$ on that input. I am not sure how the definition of a Turing machine can be satisfied by this function.

Turing machines are written a finite strings. In particular, the transition function $\delta$ is written as a sequence of 5-tuples. As a result, a TM is written as a string with a clear structure (it's a 7-tuple where the 4th element is a sequence of 5-tuples and so on). It is possible to verify on any universal computer whether a given string has this structure.

 

[evinda]

Turing machines are written a finite strings. In particular, the transition function $\delta$ is written as a sequence of 5-tuples. As a result, a TM is written as a string with a clear structure (it's a 7-tuple where the 4th element is a sequence of 5-tuples and so on). It is possible to verify on any universal computer whether a given string has this structure.

I understand... Thank you very much for your help! (Smile)

 

[evinda]

In order to show that the language $\{ n \in \mathbb{N} \mid T_n(n+1) \uparrow \}$ is not recursive we can use the fact that the language $L=\{ n \in \mathbb{N} \mid T_n(0) \uparrow \}$ is not recursive. Right?
We do it as follows:

Given $n$ we construct a machine $M$ that erases its input, writes $0$ and behaves as $T_n$. Then $M$ on any input ( including $n+1$) behaves is the same way as $T_n(0)$.

So we have shown that $L \leq_{TM} \{ n \in \mathbb{N} \mid T_n(n+1) \uparrow \}$ and so the latter is also decidable.

Am I right?

 

[Evgeny.Makarov]

Yes, you are right.

 

[evinda]

Yes, you are right.

Nice. Thank you! :)