Register to reply 
Turing Machines & Undecidability 
Share this thread: 
#1
Mar1212, 08:07 AM

P: 3

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 manyto1 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
Mar1312, 05:00 PM

P: 127

What do you mean by undecible language, the chomsky hiearchy for languages is given as follows: http://en.wikipedia.org/wiki/Chomsky_hierarchy.



#3
Mar1312, 08:15 PM

P: 3

I mean partially decidable or recursively enumerable.



#4
Mar1412, 04:45 AM

P: 127

Turing Machines & Undecidability
Aren't they both regular?



Register to reply 
Related Discussions  
Turing Machines  Calculus & Beyond Homework  4  
Conciousness and Turing undecidability  General Discussion  1  
Uncountably Many Turing Machines  Set Theory, Logic, Probability, Statistics  4  
Turing machines  Calculus  5 