1. Limited time only! Sign up for a free 30min personal 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!

Homework Help: 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
  4. Mar 13, 2012 #3
    I mean partially decidable or recursively enumerable.
     
  5. Mar 14, 2012 #4
    Aren't they both regular?
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook




Loading...
Similar Threads for Turing Machines Undecidability Date
Language that cannot be decided by a TM using space O(log n) Feb 29, 2016
Turing machine depth-first search algorithm Apr 15, 2013
Boolean expressions for Turing Machine Feb 17, 2010
Turing machine help! Jun 3, 2008
Turing machine problem Apr 11, 2007