Turing Machines Quiz

A Turing machine that is able to simulate other Turing machines:

• Nested Turing machines

• Universal Turing machine

• Counter machine

• None of the mentioned

Which of the problems are unsolvable?

• Halting problem

• Boolean Satisfiability problem

• Halting problem & Boolean Satisfiability problem

• None of the mentioned

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

• input tape

• head

• state register

• none of the mentioned

The value of n if Turing machine is defined using n-tuples:

• 6

• 7

• 8

• 5

If d is not defined on the current state and the current tape symbol, then the machine ______

• does not halts

• halts

• goes into loop forever

• none of the mentioned

Statement: Instantaneous descriptions can be designed for a Turing machine. State true or false:

• true

• false

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

• Multi tape Turing machine

• Multi track Turing machine

• Register machine

• All of the mentioned

Which among the following is incorrect for o-machines?

• Oracle Turing machines

• Can be used to study decision problems

• Visualizes Turing machine with a black box which is able to decide decision problems in one operation

• None of the mentioned

RASP stands for:

• Random access storage program

• Random access stored program

• Randomly accessed stored program

• Random access storage programming

Which of the following is not true about RASP?

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

• Stores its program in memory external to its state machines instructions

• Has infinite number of distinguishable, unbounded registers

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

• More than two options are incorrect