# Turing machines and decidability.

• Nov 22nd 2010, 04:36 PM
girgishf
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?
• Nov 22nd 2010, 10:11 PM
emakarov

Edit: Also, you are supposed to make some effort in solving the problem.
• Nov 23rd 2010, 09:05 AM
girgishf
Quote:

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 :(
• Nov 23rd 2010, 11:14 AM
emakarov
Quote:

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.

Quote:

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 $\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.
• Nov 23rd 2010, 06:49 PM
girgishf
Quote:

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 $\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
• Nov 24th 2010, 05:13 PM
girgishf
• Nov 25th 2010, 10:35 AM
emakarov
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 $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 $\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.
• Nov 29th 2010, 11:41 AM
girgishf
correction to question 1
L(M1) is proper subset of L(M2).

• Nov 29th 2010, 12:02 PM
emakarov
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.
• Nov 29th 2010, 12:13 PM
girgishf
So B is undecidable, what about A? And what's the relation between both of them?
Thanks
• Nov 29th 2010, 12:15 PM
girgishf
So B is undecidable, what about A? And what's the relation between both of them?
Thanks
• Nov 29th 2010, 12:38 PM
emakarov
Quote:

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.

Quote:

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.