1,069 views
1 votes
1 votes
From rice theorem, I know that it is not recursive. But can someone prove that ? Or atleast give some intuitive proof?

1 Answer

1 votes
1 votes
Let be the problem of accepting Epsilion problem.

R = {<M>| M is a TM which accept Epsilion}

Now, Consider one Undecidable problem

ATM = {<M,w>|M is a TM and w is string}

Now we reduce ATM  problem to R'(complement of the given problem).

Let F be the Reduction function for that.

 F = "On input M,w "
     1. Construct TM M
         M1 = "On input <M,w>
              a. for each x
              b.   if(x != w) "reject"
              c.   if(x==epsilon) "reject"
              d.   else RUN M on W. if M accept then accept , M reject then reject else loop.
     [ M1's language contain either w or nothing ]
     3. RUN R TM with input<M1>
     4. If R' accept then "accept"
     6. If R' reject then "reject"

So, ATM <m R'
==> ATM' <m  R

As ATM' is not Turing reconizable language so, R is not Turing reconizable.
[we know ATM is undecidable language but Turing Reconizable language so ATM' is not R.E]

So, R is not  R.E.

Related questions

2 votes
2 votes
2 answers
1
Akriti sood asked Jan 15, 2017
3,471 views
L={<M : M is a TM that accepts all even numbers }is it recursive/R.E??
3 votes
3 votes
1 answer
2
3 votes
3 votes
1 answer
4
rahul sharma 5 asked Aug 1, 2017
1,931 views
Semidecidable means RE or only but NOT REC? Can i say every semi decidable is undecidable?