1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Turing Machines & Undecidability

  1. Mar 12, 2012 #1
    1. The problem statement, all variables and given/known data

    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?

    2. Relevant equations



    3. The attempt at a solution

    I think L1 is undeciable and L2 is decidable. Since we can have a many-to-1 reduction from halting to L1 and for L2, we can count the number of states in some encoding. And I guess L1 intersect L2 is still undecidable but I can't find a reduction to any undecidable problems.

    Any help will be appreciated!
     
  2. jcsd
  3. Mar 13, 2012 #2
    What do you mean by undecible language, the chomsky hiearchy for languages is given as follows: http://en.wikipedia.org/wiki/Chomsky_hierarchy.
     
  4. Mar 13, 2012 #3
    I mean partially decidable or recursively enumerable.
     
  5. Mar 14, 2012 #4
    Aren't they both regular?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Similar Discussions: Turing Machines & Undecidability
  1. Turing machine problem (Replies: 1)

  2. Turing machine help! (Replies: 0)

  3. Induction Machine (Replies: 3)

Loading...