Q.1 Which of the following best describes Quantum Computing?
Computing based on binary states
Computing based on probabilistic automata
Computing based on qubits using superposition and entanglement
Computing based on deterministic finite automata
Explanation - Quantum computing uses qubits, which can exist in multiple states simultaneously due to superposition, and can be linked via entanglement, enabling faster problem-solving.
Correct answer is: Computing based on qubits using superposition and entanglement
Q.2 What is the Church-Turing Thesis primarily about?
Every physical process can be simulated by a probabilistic automaton
Any function computable by an algorithm can be computed by a Turing Machine
All problems are solvable with enough memory
Parallelism always improves computability
Explanation - The Church-Turing Thesis posits that Turing Machines capture the fundamental limits of algorithmic computation.
Correct answer is: Any function computable by an algorithm can be computed by a Turing Machine
Q.3 Which model of computation is explored in DNA computing?
Cellular Automata
Molecular interactions of DNA strands
Parallel Turing Machines
Neural Networks
Explanation - DNA computing uses molecular biology operations on DNA strands to represent and solve computational problems.
Correct answer is: Molecular interactions of DNA strands
Q.4 What is the significance of P vs NP problem?
It deals with memory efficiency
It addresses whether every efficiently verifiable problem can also be solved efficiently
It compares deterministic and nondeterministic automata
It resolves infinite state automata
Explanation - The P vs NP problem questions if problems whose solutions are verifiable in polynomial time (NP) can also be solved in polynomial time (P).
Correct answer is: It addresses whether every efficiently verifiable problem can also be solved efficiently
Q.5 In neuromorphic computation, what is being simulated?
Biological neurons and synapses
Quantum entanglement
Molecular interactions
DNA strands
Explanation - Neuromorphic computation models the brain’s neural structure to develop efficient, adaptive computation systems.
Correct answer is: Biological neurons and synapses
Q.6 Which of the following is a characteristic of Memcomputing?
Uses molecular computing exclusively
Computes through memory and storage elements directly
Based on DNA recombination
Relies on cellular automata
Explanation - Memcomputing uses memory units not only to store but also to process information, merging memory and computation.
Correct answer is: Computes through memory and storage elements directly
Q.7 Which emerging computation model uses spin states of particles?
Neuromorphic computing
DNA computing
Spintronics computing
Cloud computing
Explanation - Spintronics uses the intrinsic spin of electrons to represent and process data in computation.
Correct answer is: Spintronics computing
Q.8 What is the role of automata in Natural Language Processing (NLP)?
To store large dictionaries
To model syntax and grammar as formal languages
To compute neural activations
To optimize hardware memory
Explanation - Automata theory provides the formal foundation for parsing and recognizing grammatical structures in NLP.
Correct answer is: To model syntax and grammar as formal languages
Q.9 Which computing paradigm mimics evolutionary processes?
Quantum computing
DNA computing
Evolutionary algorithms
Memcomputing
Explanation - Evolutionary algorithms mimic biological evolution with processes like mutation, selection, and crossover.
Correct answer is: Evolutionary algorithms
Q.10 What distinguishes quantum algorithms from classical algorithms?
They require infinite time
They use qubits enabling parallelism via superposition
They always give approximate answers
They rely only on deterministic rules
Explanation - Quantum algorithms exploit superposition and entanglement to perform parallel operations on qubits.
Correct answer is: They use qubits enabling parallelism via superposition
Q.11 What does 'Reversible Computing' aim to minimize?
Energy dissipation due to information loss
Memory consumption
Hardware size
Parallel processing errors
Explanation - Reversible computing designs computations so no information is lost, reducing heat and energy dissipation.
Correct answer is: Energy dissipation due to information loss
Q.12 Which of the following is true about Cellular Automata?
They are used only in classical automata theory
They consist of a grid of cells evolving based on local rules
They require DNA to function
They cannot simulate physical systems
Explanation - Cellular automata are grids of cells that evolve over discrete time steps based on simple local rules.
Correct answer is: They consist of a grid of cells evolving based on local rules
Q.13 Which type of automaton underlies Regular Expressions?
Pushdown automaton
Deterministic finite automaton (DFA)
Linear bounded automaton
Turing Machine
Explanation - Regular expressions are equivalent in power to finite automata, especially DFA and NFA.
Correct answer is: Deterministic finite automaton (DFA)
Q.14 Which computational complexity class is associated with problems solvable in polynomial space?
NP
PSPACE
EXP
LOGSPACE
Explanation - PSPACE includes problems solvable by a Turing Machine using a polynomial amount of memory space.
Correct answer is: PSPACE
Q.15 What is an example of a problem in NP but not known to be in P?
Sorting numbers
Traveling Salesman Problem
Matrix multiplication
Binary search
Explanation - The Traveling Salesman Problem is NP-complete, and it is not known if it can be solved in polynomial time.
Correct answer is: Traveling Salesman Problem
Q.16 What do interactive proof systems allow?
Deterministic algorithms only
A verifier to interact with a prover to check proofs
Infinite state automata
Memoryless computation
Explanation - Interactive proof systems allow verifiers to interact with provers to confirm the correctness of statements.
Correct answer is: A verifier to interact with a prover to check proofs
Q.17 Which computational paradigm does 'Approximate Computing' belong to?
Exact algorithm design
Energy-efficient and tolerance-based computing
Deterministic computation only
Formal language theory
Explanation - Approximate computing accepts near-correct answers to save time, energy, and resources.
Correct answer is: Energy-efficient and tolerance-based computing
Q.18 Which theorem shows limitations of formal systems?
Rice's Theorem
Gödel’s Incompleteness Theorem
Pumping Lemma
Cook-Levin Theorem
Explanation - Gödel’s theorem proves that any sufficiently expressive formal system cannot be both consistent and complete.
Correct answer is: Gödel’s Incompleteness Theorem
Q.19 What is a universal Turing machine?
A machine that solves NP-complete problems instantly
A machine that can simulate any other Turing machine
A machine with infinite memory only
A machine based on DNA
Explanation - A universal Turing machine is capable of simulating any other Turing machine’s computation.
Correct answer is: A machine that can simulate any other Turing machine
Q.20 Which area explores the intersection of computation and biology?
Memcomputing
DNA computing
Spintronics
Reversible computing
Explanation - DNA computing uses biological processes to solve computational problems.
Correct answer is: DNA computing
Q.21 What is the Halting Problem about?
Whether a program stops or runs forever
Whether memory is sufficient for a program
How long a program runs
If a program produces output in polynomial time
Explanation - The Halting Problem proves that no algorithm can determine for all programs if they will halt or run infinitely.
Correct answer is: Whether a program stops or runs forever
Q.22 Which computational paradigm uses probabilistic models extensively?
Quantum computing
Probabilistic computing
Memcomputing
Cellular Automata
Explanation - Probabilistic computing uses randomness and probability to model computations, often in algorithms and automata.
Correct answer is: Probabilistic computing
Q.23 Which area studies the boundary of efficient computability?
Complexity theory
Automata theory
Approximate computing
Parallel computing
Explanation - Complexity theory classifies problems based on their computational resource requirements, exploring efficiency limits.
Correct answer is: Complexity theory
Q.24 Which emerging paradigm explores computing with light?
Neuromorphic computing
Photonic computing
DNA computing
Probabilistic computing
Explanation - Photonic computing uses photons instead of electrons, allowing faster and parallel processing.
Correct answer is: Photonic computing
Q.25 Which famous theorem shows some languages are undecidable?
Rice’s Theorem
Pumping Lemma
Gödel’s Completeness Theorem
Church-Rosser Theorem
Explanation - Rice’s theorem states that any non-trivial property of the language recognized by Turing machines is undecidable.
Correct answer is: Rice’s Theorem