Thread: Turing machines and decidability.

1. Let SUBSETTM = {<M1,M2> : M1 and M2 are Turing machines and L(M1) L(M2)}. Is
SUBSETTM decidable? Prove your answer is correct.

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

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.

Originally Posted by emakarov

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.

I corrected my post. I spent a lot of time on it, but i didn't get anything

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 is countable). One will eventually learn if the machine accepts two different strings, but may never learn if it does not.

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 is countable). One will eventually learn if the machine accepts two different strings, but may never learn if it does not.

Thanks

can you please explain the second answer in more detail

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 (see, for example, Cantor pairing function), which is computable. Finally, there is a bijection g between 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.

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

Can u please re answer it???

Thanks in advance

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.

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

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

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.