660 views

2 Answers

0 votes
0 votes

i think it's NOT RE, whether a TM accepts epsilon it itself as an NOT RE problem.

0 votes
0 votes
Now, Consider one Undecidable problem

ATM = {<M,w>|M is a TM and w is string}
Let R is the given problem.
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 an arbitrary TM M2 which reject all input i.e it accept empty language.

     2. Construct TM M1
         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,M2>
     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, the above problem is not  R.E.

Related questions

1 votes
1 votes
1 answer
3
Abhipsa asked Jan 22, 2019
346 views
What is the difference between Turing Recognizable and Turing Decidable?Thanks!