BPSC TRE – TOC: Turing Machines, Computability & Decidability

Question 91

MCQ · Single Correct 1 mark

What is a Universal Turing Machine (UTM)?

A A machine with infinite computational speed B A Turing machine that can simulate any arbitrary Turing machine M on input string w when given <M, w> C More than one of the above D A Turing machine that solves all NP-hard problems in O(1) time E None of the above

Question 92

MCQ · Single Correct 1 mark

Which language hierarchy correctly lists inclusion from smallest/most restrictive to largest/least restrictive?

A Regular ⊂ Context-Free ⊂ Context-Sensitive ⊂ Recursive ⊂ Recursively Enumerable B None of the above C Regular ⊂ Context-Sensitive ⊂ Context-Free ⊂ Recursive ⊂ Recursively Enumerable D Context-Free ⊂ Regular ⊂ Recursive ⊂ Context-Sensitive ⊂ Recursively Enumerable E More than one of the above

Question 93

MCQ · Single Correct 1 mark

Which problem regarding Context-Sensitive Languages is DECIDABLE?

A Universality problem (Is L(CSG) = $\Sigma *?)$ B None of the above C More than one of the above D Membership problem (Is string w ∈ L(CSG)?) E Emptiness problem (Is L(CSG) = ∅?)

Question 94

MCQ · Single Correct 1 mark

In Reduction techniques (A <=p B), if problem A is NP-Hard and A reduces in polynomial time to problem B, then problem B is:

A In Class P B More than one of the above C Decidable D None of the above E NP-Hard

Question 95

MCQ · Single Correct 1 mark

What is the tape alphabet restriction in a 2-tag system or Counter Machine compared to a standard Turing Machine?

A Eliminates state transitions B Reduces computational power to Finite Automata C Bounded memory access mechanisms (like stacks/counters) that maintain computational equivalence to TMs when >= 2 counters exist D More than one of the above E None of the above