44 views
Consider the following problems and select the problem which is recursively enumerable but not recursive. (MSQ type)
1 . Whether a given Turing machine accepts non-empty language.
2. Whether a given Turing machine accepts finite language .
3. Whether a given Turing machine accepts at most 10 strings
4. Whether a given Turing machine accepts at least 10 strings.
| 44 views
0
Only 1?
+1
1 , 4?
0
answer given is 1 and 4 , can you elaborate the reasons for it
+3

For 2. Tyes={a} Tno=(a+b)*

Tyes$\subset$Tno. (Part 2 Rice theorem https://gatecse.in/rices-theorem/ ) So Not re.