670 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


Deprecated: Implicit conversion from float-string "1548180189.556" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 796

Deprecated: Implicit conversion from float-string "1548180189.556" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 801

Deprecated: Implicit conversion from float-string "1548180189.556" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 802

Deprecated: Implicit conversion from float-string "1548180189.556" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 803
992
views
2 answers
3 votes
rahul sharma 5 asked Aug 7, 2017
992 views
Check whether the language below is recursive, recursively enumerable but not recursive, or not recursively enumerable?L={⟨M⟩∣ M halts on all palindromes}.How can i...
1.6k
views
2 answers
3 votes
biranchi asked May 24, 2016
1,596 views
Consider the following two decision problemsWhether a Turing Machine takes more than 481 steps on input epsilon?Whether a Turing Machine accepts the null string epsilon?W...
360
views
1 answers
1 votes
Abhipsa asked Jan 22, 2019
360 views
What is the difference between Turing Recognizable and Turing Decidable?Thanks!
496
views
0 answers
1 votes
rahul sharma 5 asked Aug 8, 2017
496 views
L ={ T | e(T) belongs to L(T) } , e(T) is the code for turing machine?The answer given is RE but not REC ,but cant we apply Rice theorem as follow-Tyes={Any machine accep...
Total PHP MySQL Other RAM
Time (ms) % Time (ms) % File count Time (ms) % Query count Time (ms) % Amount %
Setup 3.7 6% 2.2 4% 72 1.5 2% 2 0.0 0% 569k 50%
Control 12.5 23% 1.6 2% 5 11.3 20% 12 0.0 0% 188k 16%
View 1.1 2% 1.1 2% 12 0.0 0% 0 0.0 0% 96k 8%
Theme 32.0 58% 3.7 6% 15 28.4 52% 3 0.0 0% 264k 23%
Stats 5.1 9% 0.1 0% 0 5.0 9% 1 0.0 0% 0k 0%
Total 54.4 100% 8.7 15% 104 46.3 85% 18 0.0 0% 1119k 100%