# Theory of Computation MCQ (Multiple Choice Questions) - SchoolingAxis

1. Which of the following a Turing machine does not consist of?

a. input tape

c. state register

d. none of the mentioned

Ans- d. none of the mentioned

2. Which of the problems are unsolvable?

a. Halting problem

b. Boolean Satisfiability problem

c. Both (a) and (b)

d. None of the mentioned

Ans- c. Both (a) and (b)

3. A turing machine that is able to simulate other turing machines:

a. Nested Turing machines

b. Universal Turing machine

c. Counter machine

d. None of the mentioned

Ans- b. Universal Turing machine

4. Fill in the blank with the most appropriate option. Statement: In theory of computation, abstract machines are often used in _____ regarding computability or to analyze the complexity of an algorithm.

a. thought experiments

b. principle

c. hypothesis

d. all of the mentioned

Ans- d. all of the mentioned

5. Which of the following is false for an abstract machine?

a. Turing machine

b. theoretical model of computer

c. assumes a discrete time paradigm

d. all of the mentioned

Ans- d. all of the mentioned

6. Turing machine can be represented using the following tools:

a. Transition graph

b. Transition table

c. Queue and Input tape

d. All of the mentioned

Ans- d. All of the mentioned

7. The ability for a system of instructions to simulate a Turing Machine is called ___

a. Turing Completeness

b. Simulation

c. Turing Halting

d. None of the mentioned

Ans- a. Turing Completeness

8. Which of the problems were not answered when the turing machine was invented?

a. Does a machine exists that can determine whether any arbitrary machine on its tape is circular.

b. Does a machine exists that can determine whether any arbitrary machine on its tape is ever prints a symbol

c. Hilbert Entscheidungs problem

d. None of the mentioned

Ans- d. None of the mentioned

9. Which of the functions are not performed by the turing machine after reading a symbol?

a. writes the symbol

b. moves the tape one cell left/right

c. proceeds with next instruction or halts

d. none of the mentioned

Ans- d. None of the mentioned

10. A turing machine operates over:

a. finite memory tape

b. infinite memory tape

c. depends on the algorithm

d. none of the mentioned

Ans- b. infinite memory tape

11. Which of the following is not true about RASP?

a. Binary search can be performed more quickly using RASP than a turing machine

b. Stores its program in memory external to its state machines instructions

c. Has infinite number of distinguishable, unbounded registers

d. Binary search can be performed less quickly using RASP than a turing machine

Ans- d. Binary search can be performed less quickly using RASP than a turing machine

12. RASP stands for:

a. Random access storage program

b. Random access stored program

c. Randomly accessed stored program

d. Random access storage programming

Ans- b. Random access stored program

13. Which among the following is incorrect for o-machines?

a. Oracle Turing machines

b. Can be used to study decision problems

c. Visualizes Turing machine with a black box which is able to decide cerain decion problems in one operation

d. None of the mentioned

Ans- d. None of the mentioned

14. Which of the following are the models equivalent to Turing machine?

a. Multi tape turing machine

b. Multi track turing machine

c. Register machine

d. All of the mentioned

Ans- d. All of the mentioned

15. If d is not defined on the current state and the current tape symbol, then the machine __

a. does not halts

b. halts

c. goes into loop forever

d. none of the mentioned

Ans- b. halts

16. The value of n if turing machine is defined using n-tuples:

a. 6

b. 7

c. 8

d. 5

Ans- b. 7