Test: Turing Machine: RE, REC & Undecidability- 2 - Computer Science Engineering (CSE) MCQ

Drawing the equivalent turing machine we have 

This is a standard turing machine program for 

The correct statement follows from following theorem:
Theorem: If L₁ and L₂ is a pair of complementary language then either
• Both L₁ and L₂ are recursive.
• Neither L₁, and L₂ are recursively enumerable.
• One is recursively enumerable but not recursive, the other is not RE.
Option (b) is not possible, since if L₁ is recursive, then will also be recursive.

While simulating multi-tape TM on a single tape TM, the head has to move at least 2k cells per move, where k is the number of tracks on single tape TM. Thus for k moves, we get 

which means quadratic slow down. Thus, acceptance by single-tape is slower by 0(n²).

The analysis of transition of TM, M shows that is accepts language 0*10*.

The Turing Machine carries out the functions of ( m - n) in (0^m 10ⁿ).
• When m≥n, the output is difference between m and n.
• when m < n, the output is blank.

L = (0 + 1 )* or {}. A trivial TM which accepts all words or another which rejects all. One of these two TMs will surely accept this language. So L is recursive.

L is recursive iff L is enumerable in Lexicographic order (alphabetic).
It is also known that context free language is a subset of recursive languages.

Single tape turing machine can simulate n-moves of k-tape TM in O(n²).

Hence, not accepted.

Hence, also not accepted.

It can be observed from the image that this machine will accept only those strings which contains even number of 1’s. And strings with odd number of 1 ’s are rejected.

Since 3-SAT problem is NP-complete and 3-SAT is polynomial time reducible to π hence π is is also NP-complete.

P and NP language are closed under union, intersection, kleene closure and concatenation, P is close under complement also while closure of NP under complement is still unsolved problem.

L ∈ NP does not imply that L' ∈ NP. Since closure of NP under complementation is as yet unresolved problem. Also L ∈ NP does not imply L' ∈ P, unless L ∈ P, which may or may not be so.