Q.1 Which of the following best defines a Turing Machine?
A machine that can solve all computational problems
An abstract computational model that manipulates symbols on a tape according to rules
A real computer used in laboratories
A type of finite automaton with limited memory
Explanation - A Turing Machine is a theoretical model used to formalize the concept of computation, consisting of a tape, a head, and a set of rules for symbol manipulation.
Correct answer is: An abstract computational model that manipulates symbols on a tape according to rules
Q.2 Which of the following is NOT a component of a standard Turing Machine?
Tape
Tape head
Control unit
Compiler
Explanation - A Turing Machine consists of a tape, a tape head, a finite set of states (control unit), and a transition function. A compiler is unrelated.
Correct answer is: Compiler
Q.3 What is the significance of the halting problem in Turing Machines?
It can always be solved using a deterministic Turing Machine
It demonstrates the limits of computation
It is used to optimize Turing Machine speed
It allows infinite loops to be avoided
Explanation - The halting problem shows that there is no general algorithm that can determine whether any arbitrary Turing Machine will halt on a given input.
Correct answer is: It demonstrates the limits of computation
Q.4 A non-deterministic Turing Machine differs from a deterministic one in that:
It always halts
It can explore multiple computational paths simultaneously
It has no tape
It cannot accept any language
Explanation - A non-deterministic Turing Machine can have multiple possible moves from a given configuration and accepts if at least one path leads to an accepting state.
Correct answer is: It can explore multiple computational paths simultaneously
Q.5 Which type of language can be accepted by a Turing Machine?
Regular languages
Context-free languages
Recursively enumerable languages
Only finite languages
Explanation - Turing Machines can accept all recursively enumerable languages, which include all languages that can be recognized by some Turing Machine.
Correct answer is: Recursively enumerable languages
Q.6 A Turing Machine that always halts for any input is called:
Deterministic Turing Machine
Universal Turing Machine
Decider
Linear Bounded Automaton
Explanation - A decider is a Turing Machine that halts on all inputs, either accepting or rejecting them.
Correct answer is: Decider
Q.7 What is a Universal Turing Machine?
A Turing Machine that can simulate any other Turing Machine
A Turing Machine with infinite tapes
A machine that can solve the halting problem
A Turing Machine without states
Explanation - A Universal Turing Machine can read the description of any Turing Machine and its input and simulate its computation.
Correct answer is: A Turing Machine that can simulate any other Turing Machine
Q.8 Which variant of Turing Machine has a tape that is infinite in both directions?
Standard Turing Machine
Two-way infinite Turing Machine
Linear Bounded Automaton
Pushdown Automaton
Explanation - A two-way infinite Turing Machine has a tape that extends infinitely to both the left and right, unlike the standard TM which is infinite only in one direction.
Correct answer is: Two-way infinite Turing Machine
Q.9 Which statement is true about multi-tape Turing Machines?
They are more powerful than single-tape Turing Machines
They recognize a different class of languages
They can be simulated by a single-tape Turing Machine
They cannot simulate non-deterministic Turing Machines
Explanation - Although multi-tape Turing Machines can be faster, any multi-tape TM can be simulated by a single-tape TM without increasing the class of languages recognized.
Correct answer is: They can be simulated by a single-tape Turing Machine
Q.10 A Turing Machine can be used to decide whether a string belongs to a:
Regular language only
Context-free language only
Recursively enumerable language
None of the above
Explanation - Turing Machines can decide membership for strings in recursively enumerable languages, covering regular and context-free languages as subsets.
Correct answer is: Recursively enumerable language
Q.11 Which of the following is true about non-deterministic and deterministic Turing Machines?
Non-deterministic Turing Machines are strictly more powerful
Deterministic Turing Machines can simulate non-deterministic ones
Non-deterministic Turing Machines cannot recognize languages
Deterministic Turing Machines require infinite states
Explanation - Every non-deterministic Turing Machine can be simulated by a deterministic Turing Machine, though possibly less efficiently in terms of time.
Correct answer is: Deterministic Turing Machines can simulate non-deterministic ones
Q.12 Which of the following can a Linear Bounded Automaton (LBA) do that a standard Turing Machine can also do?
Recognize all recursively enumerable languages
Recognize context-sensitive languages
Solve the halting problem
Simulate non-deterministic finite automata
Explanation - An LBA is a Turing Machine with a tape bounded by the input length and can recognize context-sensitive languages.
Correct answer is: Recognize context-sensitive languages
Q.13 Which of the following is undecidable?
Checking if a Turing Machine accepts a given string
Checking if a string is in a regular language
Checking if a string is in a context-free language
Finding the shortest path in a graph
Explanation - The problem of determining whether a Turing Machine accepts a particular input is undecidable, related to the halting problem.
Correct answer is: Checking if a Turing Machine accepts a given string
Q.14 In Turing Machine notation, δ(q, a) = (p, b, L) represents:
Move from state q to p, write b, move left
Move from state p to q, write a, move right
Write b in state p without moving
Reject the input in state q
Explanation - δ is the transition function. δ(q, a) = (p, b, L) means that if the TM is in state q reading symbol a, it moves to state p, writes b, and moves the tape left.
Correct answer is: Move from state q to p, write b, move left
Q.15 Which of the following is a key property of a Turing Machine?
It has finite memory
It can perform any computation given enough time
It cannot recognize context-free languages
It is faster than real computers
Explanation - Turing Machines are universal in the sense that they can compute any computable function if given unlimited time and tape.
Correct answer is: It can perform any computation given enough time
Q.16 Which of the following statements is correct about Turing Machine variants?
All variants recognize the same class of languages
Non-deterministic Turing Machines are weaker than deterministic ones
Multi-tape Turing Machines recognize fewer languages
Two-way infinite Turing Machines cannot be simulated by standard TMs
Explanation - Variants of Turing Machines differ in speed or tape structure, but they all recognize recursively enumerable languages.
Correct answer is: All variants recognize the same class of languages
Q.17 Which of the following problems can a Turing Machine solve?
Halting problem for all TMs
Membership in recursively enumerable languages
Finding the shortest route in a city
Predicting the stock market
Explanation - Turing Machines can recognize if a string belongs to a recursively enumerable language but cannot decide the halting problem.
Correct answer is: Membership in recursively enumerable languages
Q.18 What is the main difference between a standard TM and a Linear Bounded Automaton (LBA)?
LBA has unbounded tape, TM has bounded tape
LBA tape is bounded by input size, TM tape is unbounded
LBA cannot recognize any language
TM is faster than LBA
Explanation - An LBA is a restricted Turing Machine where the tape is limited to the length of the input, used for context-sensitive languages.
Correct answer is: LBA tape is bounded by input size, TM tape is unbounded
Q.19 Which of the following is true about deterministic and non-deterministic Turing Machines?
Non-deterministic TMs can solve undecidable problems
Deterministic TMs can simulate non-deterministic ones
Non-deterministic TMs are always faster
Deterministic TMs cannot recognize context-free languages
Explanation - Any computation done by a non-deterministic Turing Machine can be simulated by a deterministic Turing Machine, although possibly less efficiently.
Correct answer is: Deterministic TMs can simulate non-deterministic ones
Q.20 Which of the following is an example of a Turing Machine variant?
Pushdown Automaton
Linear Bounded Automaton
Finite Automaton
Stack Machine
Explanation - An LBA is a Turing Machine variant with tape length bounded by input size, used for context-sensitive languages.
Correct answer is: Linear Bounded Automaton
Q.21 The Church-Turing thesis states that:
All problems are solvable by Turing Machines
Any computation done by an effective method can be performed by a Turing Machine
Turing Machines can solve the halting problem
Finite Automata can simulate Turing Machines
Explanation - The Church-Turing thesis proposes that the Turing Machine model captures all effectively calculable functions.
Correct answer is: Any computation done by an effective method can be performed by a Turing Machine
Q.22 Which of the following cannot be recognized by a Turing Machine?
Recursively enumerable languages
Regular languages
Context-sensitive languages
Some non-recursively enumerable languages
Explanation - Turing Machines cannot recognize languages that are not recursively enumerable.
Correct answer is: Some non-recursively enumerable languages
Q.23 In a Turing Machine, the tape is:
Finite and unidirectional
Infinite and divided into cells
Infinite but without symbols
Finite and two-dimensional
Explanation - The tape of a Turing Machine is conceptually infinite and divided into discrete cells that hold symbols.
Correct answer is: Infinite and divided into cells
Q.24 Which of the following statements about multi-tape Turing Machines is true?
They can solve more problems than single-tape TMs
They are less powerful than single-tape TMs
They recognize the same class of languages as single-tape TMs
They cannot be simulated by single-tape TMs
Explanation - Multi-tape TMs can make computation faster but do not increase the class of languages they can recognize compared to single-tape TMs.
Correct answer is: They recognize the same class of languages as single-tape TMs
Q.25 Which problem is considered undecidable for Turing Machines?
Acceptance problem for Turing Machines
Membership problem for regular languages
Membership problem for context-free languages
String reversal problem
Explanation - The problem of determining whether a Turing Machine accepts a given input is undecidable, as shown by the halting problem.
Correct answer is: Acceptance problem for Turing Machines