Theory of Computation MCQ with Answers

Theory of Computation MCQ with Answers

66) Consider an alternate Turing machine model, in which there is an input tape on which the tape head can move in both directions but cannot write, and one or more work tapes, one of which serves as an output tape. For a function f, denoted by DSpace ( f ) , the set of languages that can be recognized by a Turning machine of this type which uses no more than f(n) squares on any work tape for any input string of length n. The only restriction we need to make on f is that f(n) > 0 for every n. The language of

Answer is:

DSpace (1+ ⌈log2(n + 1 ⌉). (⌈ x ⌉) means the smallest integer greater than or equal to x.

67) Which of the following problems is solvable ?

Answer is:

Writing a universal Turing machine

68) Which of the following is not primitive recursive but partially recursive ?

Answer is:

Ackermann's function

69) Turing machine (TM) is more powerful than FMS (Finite State Machine) because

Answer is:

it has the capability to remember arbitrarily long sequences of input symbols

70) If f : N--> N. If L can be recognized by a TM T, so thatτT(n)≤ f (n) for all but finitely many n, then ( Time (f) means Time ( max ( f, 2n +2))).

Answer is:

L ∈Time (f)

11
12
13
14
15
16
17