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)