+1-315-636-4485
+91 98151-74050 
This quiz contains MCQs on the language of Turing machines and their simulations, Turing machine halting, multi-tape and non-deterministic Turing machines, storage and subroutines.
A Turing machine is a/an
Real machine
Abstract machine
Hypothetical machine
More than one option is correct
A Turing machine operates over
Finite memory tape
Infinite memory tape
Depends on the algorithm
None of the above
Which of the following functions are not performed by the Turing machine upon reading a symbol?
Writes the symbol
Moves the tape one cell left/right
Proceeds to next instruction or halts
None of the above
The ‘a’ in a-machine is
Alan
Arbitrary
Automatic
None of the above
Which of the following problems could the Turing machine not answer when invented?
Can a machine determining the roundness of any arbitrary machine on its tape exist?
Can a machine determining the possibility of symbol printing by any arbitrary machine on its tape exist?
Hilbert’s Entscheidungsproblem
None of the above
Which of the following tools can represent a Turing machine?
Transition graph
Transition table
Queue and input tape
All of the above
Which of the following is an/are false assumption(s) for an abstract machine?
It is a Turing machine
It is the theoretical model of computer
It assumes a discrete time paradigm
All of the above
In the theory of computation, abstract machines are often used in __ regarding computability or analysing an algorithm’s complexity.
Thought experiments
Principle
Hypothesis
All of the above
The RAM model allows random access to indexed memory locations. True or false?
True
False
Multi-tape Turing machines have multi-tapes where each tape is accessed with one head. True or false?
True
False
Are multi-tape and multi-track Turing machines the same?
Yes
No
Somewhat, yes
Cannot tell
Which of the following is a/are equivalent to a basic TM?
Multitrack TM
Multitape TM
Non-deterministic TM
All of the above
Every language accepted by a k-tape TM is __ by a single-tape TM.
Accepted
Not accepted
Generated
Not generated
Can a multi-tape Turing machine have an infinite number of tapes?
Yes
No
The ability of a system of instructions to simulate a Turing machine is called
Turing completeness
Simulation
Turing halting
None of the above
