Results 1 to 5 of 5

Math Help - Turing Machines

  1. #1
    Newbie
    Joined
    Dec 2011
    Posts
    4

    Turing Machines

    I have a question regarding undecidable languages.
    Let L1 = { M | M is an encoding of a Turing machine that accepts any input} and L2 = { M | M is an Turing machine with at most 100 states}. Is L1 intersect L2 decidable?
    I think L1 is undeciable and L2 is decidable. And I guess L1 intersect L2 is undecidable but I can't find a reduction to any undecidable problems. Any help will be appreciated!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Sep 2008
    Posts
    95

    Re: Turing Machines

    I agree that L1 is undecidable, because there is an easy reduction from it to the Halting Problem, which I assume you've already figured out. L2 is also clearly decidable; you just design a machine which takes the encoding of M as an input and counts the number of states. I think there is another easy reduction to show L1 intersect L2 is undecidable - essentially the same reduction as for L1 from the Halting problem, except that you also add 100 redundant states in order to satisfy L2. What do you think?

    Edit: I misread less than 100 states for more than 100 states. In this case, we still use the reduction for L1 combined with a simulation to ensure using less than 100 states. Sorry, if I've confused you.
    Last edited by StaryNight; March 20th 2012 at 04:51 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Dec 2011
    Posts
    4

    Re: Turing Machines

    Thank you very much for your reply! I feel like my mind is trapped somewhere since I just don't see the reduction. I read the language as {M | M is a machine with less than 101 states and accepts any input}. For L1, I got a reduction:

    We know the halting problem "given a machine M and input x, does M halt on x". Now construct a new machine M': if the input = x, then run M on x, if it halts, accept. If input != x, accept the input. We can see M' accepts any input iff M halts on x. And M' doesn't accept everything iff M does not halt on x. So we got the reduction. L1 is undecidable. Now I got this gap since the number of states in M is unbounded. If we put limit on the number of states in M', then essentially we are reducing from 100-State-HALT instead of the original HALT. For example, M is with 1000 states and M' will be rejected regardless whether M halts on x or not.

    Like I said, I hope I'm just mistaking something so there is an easy reduction. Would you please elaborate your idea:
    Quote Originally Posted by StaryNight View Post
    we still use the reduction for L1 combined with a simulation to ensure using less than 100 states.
    Any comment will be appreciated! Thank you StaryNight
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Sep 2008
    Posts
    95

    Re: Turing Machines

    Quote Originally Posted by crazyautomata101 View Post
    Thank you very much for your reply! I feel like my mind is trapped somewhere since I just don't see the reduction. I read the language as {M | M is a machine with less than 101 states and accepts any input}. For L1, I got a reduction:

    We know the halting problem "given a machine M and input x, does M halt on x". Now construct a new machine M': if the input = x, then run M on x, if it halts, accept. If input != x, accept the input. We can see M' accepts any input iff M halts on x. And M' doesn't accept everything iff M does not halt on x. So we got the reduction. L1 is undecidable. Now I got this gap since the number of states in M is unbounded. If we put limit on the number of states in M', then essentially we are reducing from 100-State-HALT instead of the original HALT. For example, M is with 1000 states and M' will be rejected regardless whether M halts on x or not.

    Like I said, I hope I'm just mistaking something so there is an easy reduction. Would you please elaborate your idea:

    Any comment will be appreciated! Thank you StaryNight
    I don't follow your reduction from the Halting Problem to L1, so let me try and write my own formalisation:
    Assume L1 is decidable. Then there exists a machine M, that accepts the encoding of all machines that accepts any input.
    Construct H to decide the halting problem as follows:
    Take input (c,x), where c is the encoding of a Turing Machine and x is an input.
    Construct c' as the code of the machine that clears the input tape, writes x and runs program c.
    Run M on c'. It is not hard to see that H accepts (c,x) iff machine c halts on input x.

    As I suggested, there is a very similar reduction for L1 intersect L2. Are you familiar with the Universal Turing Machine?
    It is possible to construct a Turing Machine, which given the code of another Machine, is capable of simulating it.
    Importantly for this problem, this machine requires much less than 100 states, which effectively means that any Turing Machine
    that uses >100 states can be rewritten to use <100 states. If you combine this with the reduction above, you can show L1 intersect L2 to be undecidable.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Dec 2011
    Posts
    4

    Re: Turing Machines

    Thank you very much! You're good! I didn't know that UTM can have so small no. of states. Problem solved!
    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, 07:44 AM
  2. Turing machines and decidability.
    Posted in the Discrete Math Forum
    Replies: 11
    Last Post: November 29th 2010, 01:38 PM
  3. Turing machines with a single tape.
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: November 15th 2010, 07:41 AM
  4. Independent machines
    Posted in the Statistics Forum
    Replies: 1
    Last Post: July 29th 2010, 10:21 AM
  5. Turing Machines
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 19th 2007, 04:39 PM

Search Tags


/mathhelpforum @mathhelpforum