Responsive Ad Area

Share This Post

test

Using closure results for Turing-decidable languages

I have a language L1 = {w in {0,1}*| w contains the same number of 1’s and 0’s} and i have a TM M that decides L1.

I want to prove that L2 = {w in {0,1}*| w contains more 1’s than 0’s} is Turing-decidable.

I have used the “closed under complement” approach and proven that M’ decides the complement of L1 (~L1).

My question is, can I assume that the ~L1 = (L2 or ~L2) and conclude that since M’ decides ~L1 that L2 and ~L2 are both decidable languages?

Thank you for any advice
(Sorry, haven’t figured out how to use LaTex here yet…)


Using closure results for Turing-decidable languages
Using closure results for Turing-decidable languages
test
{$excerpt:n}

Share This Post

Leave a Reply

Your email address will not be Publishedd. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

Skip to toolbar