Results 1 to 12 of 12

Math Help - Turing machines and decidability.

  1. #1
    Newbie
    Joined
    Nov 2009
    From
    Canada, NWT
    Posts
    20

    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.
    Last edited by girgishf; November 23rd 2010 at 08:27 AM. Reason: Re-titled.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,545
    Thanks
    780
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Nov 2009
    From
    Canada, NWT
    Posts
    20
    Quote Originally Posted by emakarov View Post
    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
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,545
    Thanks
    780
    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 \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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Nov 2009
    From
    Canada, NWT
    Posts
    20
    Quote Originally Posted by emakarov View Post
    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
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Nov 2009
    From
    Canada, NWT
    Posts
    20
    can you please explain the second answer in more detail
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,545
    Thanks
    780
    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.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    Nov 2009
    From
    Canada, NWT
    Posts
    20

    correction to question 1

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

    Can u please re answer it???

    Thanks in advance
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,545
    Thanks
    780
    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.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Newbie
    Joined
    Nov 2009
    From
    Canada, NWT
    Posts
    20
    So B is undecidable, what about A? And what's the relation between both of them?
    Thanks
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Newbie
    Joined
    Nov 2009
    From
    Canada, NWT
    Posts
    20
    So B is undecidable, what about A? And what's the relation between both of them?
    Thanks
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,545
    Thanks
    780
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] complexity theorie, deterministic turing-machines, time complexity
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: December 19th 2011, 06:44 AM
  2. Turing machines with a single tape.
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: November 15th 2010, 06:41 AM
  3. Independent machines
    Posted in the Statistics Forum
    Replies: 1
    Last Post: July 29th 2010, 09:21 AM
  4. function machines
    Posted in the Pre-Calculus Forum
    Replies: 3
    Last Post: February 14th 2009, 01:19 PM
  5. Turing Machines
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 19th 2007, 03:39 PM

Search Tags


/mathhelpforum @mathhelpforum