67) Which of the following problems is solvable ?

Writing a universal Turing machine

Determining of an arbitrary turing machine is an universal turing machine

Determining of a universal turing machine can be written for fewer than k instructions for some k

Determining of a universal turing machine and some input will halt

Answer is:

Writing a universal Turing machine

Theory of Computation MCQ with Answers

For more MCQ's Click Here

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

Carnot's function

Ricmann function

Bounded function

Ackermann's function

Answer is:

Ackermann's function

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

tape movement is confined to one direction

it has no finite state

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

none of these

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))).

L ∈Time (f)

L ∈ Time(cf)

L ∈ Time (h)

none of these

Answer is:

L ∈Time (f)

71) Let s is a step-counting function satisfying s(n) ≥n, and L be a language accepted by a (multitape) TM T. If tape heads of T do not move past square s(n) on any of the tapes for an input string of length n, then T∈

Space(s)

F(n)

Time(f)

Time(h)

Answer is:

Space(s)

Theory of Computation MCQ with Answers

For more MCQ's Click Here

67) Which of the following problems is solvable ?

Writing a universal Turing machine

Theory of Computation MCQ with Answers

Related Theory of Computation MCQ with Answers

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

Ackermann's function

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

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))).

L ∈Time (f)

71) Let s is a step-counting function satisfying s(n) ≥n, and L be a language accepted by a (multitape) TM T. If tape heads of T do not move past square s(n) on any of the tapes for an input string of length n, then T∈

Space(s)

Theory of Computation MCQ with Answers