1. Which of the following a Turing machine does not consist of?
a. input tape
b. head
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