# Thread: Turing machines and decidability.

1. ## Turing machines and decidability.

1. Let SUBSETTM = {<M1,M2> : M1 and M2 are Turing machines and L(M1) L(M2)}. Is

2. Let L = {<M> : M is a Turing machine that accepts at least 2 different strings}. Is L recognizable?

2. Please resubmit your question: too many typos ("hM1", "M2i", "L(M1) L(M2)").

Edit: Also, you are supposed to make some effort in solving the problem.

3. Originally Posted by emakarov

Edit: Also, you are supposed to make some effort in solving the problem.
I corrected my post. I spent a lot of time on it, but i didn't get anything

4. M1 and M2 are Turing machines and L(M1) L(M2)
It is still not clear what is claimed about L(M1) L(M2). I'll assume it says L(M1) is a subset of L(M2), judging from SUBSETTM.

For 1, the easiest thing is to use Rice's theorem, which says that if you have a nontrivial set of languages, then the set of (codes of) TMs that accept these languages is not decidable. In this problem, however, we have pairs of languages. One trick is to specialize the problem to make it fit Rice's theorem by fixing M2. For example, fix some M2 such that L(M2) is empty. In this case, if SUBSETTM is decidable, then its subset with fixed M2 {<M1, M2> : M1 is a Turing machine and L(M1) is empty} is decidable as well. This, in turn, means that {<M> : M is a Turing machine and L(M1) is empty} is decidable.

2. Let L = {<M> : M is a Turing machine that accepts at least 2 different strings}. Is L recognizable?
One of the equivalent conditions (if not the definition) of recognizable language is that some TM stops on strings in the language and does not stop on strings not in the language. Well, given a (code of a) machine M, one can start running it on all possible strings. One can run it n steps on the m'th string and enumerate pairs (n, m) to try all of them (this is similar to the proof that $\displaystyle \mathbb{N}\times\mathbb{N}$ is countable). One will eventually learn if the machine accepts two different strings, but may never learn if it does not.

5. Originally Posted by emakarov
It is still not clear what is claimed about L(M1) L(M2). I'll assume it says L(M1) is a subset of L(M2), judging from SUBSETTM.

For 1, the easiest thing is to use Rice's theorem, which says that if you have a nontrivial set of languages, then the set of (codes of) TMs that accept these languages is not decidable. In this problem, however, we have pairs of languages. One trick is to specialize the problem to make it fit Rice's theorem by fixing M2. For example, fix some M2 such that L(M2) is empty. In this case, if SUBSETTM is decidable, then its subset with fixed M2 {<M1, M2> : M1 is a Turing machine and L(M1) is empty} is decidable as well. This, in turn, means that {<M> : M is a Turing machine and L(M1) is empty} is decidable.

One of the equivalent conditions (if not the definition) of recognizable language is that some TM stops on strings in the language and does not stop on strings not in the language. Well, given a (code of a) machine M, one can start running it on all possible strings. One can run it n steps on the m'th string and enumerate pairs (n, m) to try all of them (this is similar to the proof that $\displaystyle \mathbb{N}\times\mathbb{N}$ is countable). One will eventually learn if the machine accepts two different strings, but may never learn if it does not.

Thanks

7. I'll show that {<M> : M is a Turing machine that accepts at least 1 string} is recognizable. There is a Universal Turing Machine, which is an interpreter for any Turing machine. Given a code of a TM M and an input w, U can run M on w for any number of steps n and do something depending on whether M stopped within n steps or it didn't.

Next, there is a bijection $\displaystyle f:\mathbb{N}\to\mathbb{N}\times\mathbb{N}$ (see, for example, Cantor pairing function), which is computable. Finally, there is a bijection g between $\displaystyle \mathbb{N}$ and all strings of the alphabet, and it is also computable.

So we build a machine W as follows. Given a code of some M, W goes through n = 0, 1, 2, ... For each n, it computes f(n) = (m, k). Then it runs M on g(m) for k steps. If M accepted within k steps, then W also halts. Otherwise, it chooses the next i and continues.

This way, W searches through every possible input string and every number of steps. It runs M on every input for every possible number of steps. If M accepts at least one string w in k steps, then W will eventually find w and k and halt. Otherwise, W will go on forever.

8. ## correction to question 1

L(M1) is proper subset of L(M2).

9. Suppose A = {<M1,M2> : M1 and M2 are Turing machines and L(M1) is proper subset of L(M2)} is decidable. Then B = {<M> : M is a TM and L(M) is nonempty} is decidable. Indeed, fix some M' such that L(M') is empty. Then for any M, <M> is in B iff <M', M> is in A. Therefore, given an M and asked if <M> is in B, we answer yes iff <M', M> is in A. This way we get a decision procedure for B. However, by Rice's theorem, B is undecidable.

10. So B is undecidable, what about A? And what's the relation between both of them?
Thanks

11. So B is undecidable, what about A? And what's the relation between both of them?
Thanks

12. So B is undecidable, what about A?
Assuming that A is decidable, we obtained that B is decidable in spite of the Rice's theorem, which is a contradiction.

And what's the relation between both of them?
The problem B is reducible to A. This means that A is at least as hard as B. Since B is known to be undecidable, so is A.