Classical

Theory Of Computation MCQ - Recursively enumerable sets and Turning machines

21:  

 Next move function δ of a Turing machine M = (Q, Σ  , Γ, δ, q0, B, F) is a mapping

A.

δ : Q x Σ  --> Q x Γ

B.

δ : Q x Γ ---> Q x Σ x {L,  R}

C.

δ : Q x Σ ---> Q x Γ  x {L, R}

D.

δ  : Q x Γ  ---> Q x Γ x {L, R}

 
 

Option: D

Explanation :

Next move function δ of a Turing machine M = (Q, Σ ,Γ,δ, q0, B, F) is a mapping

'>
22:  

 If L can be recognized by a TM T with a doubly infinite tape, and τt = f, then L can be recognized by an ordinary TM with time complexity

A.

O(f)

B.

o(f)

C.

O(h)

D.

o(h)

 
 

Option: A

Explanation :

If L can be recognized by a TM T with a doubly infinite tape, and τt = f, then L can be recognized by an ordinary TM with time complexity

'>


Suggest an improvement