NEW
Font size
S
M
L
XL
WorksheetsUnit V Undecidability
Total questions: 50
Worksheet time: 25mins
Name
Class
Date
1.
Which of the following problems is undecidable?
a)
Sorting
b)
Searching
c)
Halting
d)
Matrix multiplication
2.
The halting problem determines whether:
a)
A TM halts
b)
A TM loops forever
c)
A TM accepts all inputs
d)
A TM is deterministic
3.
The halting problem was proved undecidable by:
a)
Turing
b)
Church
c)
Kleene
d)
Gödel
4.
The halting problem is an example of:
a)
Recursive problem
b)
Semi-decidable problem
c)
Trivial problem
d)
Decidable problem
5.
A problem is undecidable if:
a)
It cannot be solved by any algorithm
b)
It requires exponential time
c)
It is non-deterministic
d)
It can be verified in P
6.
To prove a problem undecidable, we often use:
a)
Reduction from halting problem
b)
Mathematical induction
c)
Greedy approach
d)
Divide and conquer
7.
The halting problem is partially decidable because:
a)
TM halts for some inputs
b)
We can simulate all inputs
c)
It can be decided for finite inputs
d)
It is context-free
8.
If a TM halts on some inputs, then the language is:
a)
Recursive
b)
Recursively enumerable
c)
Context-free
d)
Regular
9.
Which of the following is decidable?
a)
Emptiness of regular language
b)
Equivalence of CFGs
c)
PCP
d)
Halting problem
10.
An unsolvable problem is one that:
a)
No algorithm can solve for all inputs
b)
Has no solution
c)
Can be solved using heuristics
d)
Takes infinite time
11.
A recursive language is:
a)
Decidable by a TM that halts on all inputs
b)
Semi-decidable only
c)
Context-free
d)
Regular
12.
Every recursive language is:
a)
Recursively enumerable
b)
Context-free
c)
Finite
d)
Regular
13.
The set of recursively enumerable languages is closed under:
a)
Union
b)
Intersection
c)
Concatenation
d)
All of these
14.
Which operation is not closed for recursively enumerable languages?
a)
Complement
b)
Union
c)
Intersection
d)
Concatenation
15.
A language is recursively enumerable if there exists a TM that:
a)
Halts and accepts when string ∈ L
b)
Rejects otherwise
c)
Always halts
d)
Never halts
16.
Recursive languages are closed under:
a)
All of these
b)
Union
c)
Intersection
d)
Complement
17.
If L is recursive, then its complement L′ is:
a)
Always recursive
b)
RE but not recursive
c)
Undecidable
d)
Context-sensitive
18.
Which statement is true?
a)
All recursive languages are RE
b)
All RE languages are recursive
c)
Both same
d)
Disjoint sets
19.
A recursively enumerable language is decidable iff:
a)
Its complement is also RE
b)
It is finite
c)
It is regular
d)
It is context-free
20.
The emptiness problem for RE languages is:
a)
Decidable
b)
Undecidable
c)
Semi-decidable
d)
Regular
21.
Rice’s Theorem applies to:
a)
Non-trivial properties of Turing machines
b)
Finite automata
c)
Regular languages
d)
CFGs
22.
Rice’s Theorem states that:
a)
All non-trivial semantic properties of TMs are undecidable
b)
All syntactic properties are decidable
c)
All RE languages are finite
d)
All RE languages are finite
23.
Which of the following is a trivial property under Rice’s Theorem?
a)
L(M)=∅
b)
L(M) is regular
c)
L(M) is finite
d)
L(M) is infinite
24.
The proof of Rice’s Theorem is based on:
a)
Reduction from Halting Problem
b)
Reduction to Post’s Problem
c)
Dynamic Programming
d)
Greedy approach
25.
Rice’s Theorem deals with which aspect of TMs?
a)
Language accepted
b)
Transition function
c)
Tape symbols
d)
Input alphabet
26.
Which problem is decidable according to Rice’s Theorem?
a)
None
b)
Whether TM M accepts ε
c)
Whether M halts on input w
d)
Whether M’s language is regular
27.
Rice’s Theorem is an example of:
a)
General undecidability result
b)
Time complexity theorem
c)
Space tradeoff theorem
d)
Recursion theorem
28.
The term 'non-trivial' in Rice’s Theorem means:
a)
Property true for some TMs but not for all
b)
True for no TM
c)
True for all TMs
d)
Depends on syntax
29.
Rice’s Theorem proves that checking if L(M) is regular is:
a)
Undecidable
b)
Decidable
c)
Semi-decidable
d)
Trivial
30.
Rice’s Theorem does not apply to:
a)
Syntactic properties
b)
Semantic properties
c)
Language properties
d)
Computable functions
31.
PCP was introduced by:
a)
Emil Post
b)
Alan Turing
c)
Alonzo Church
d)
Stephen Cook
32.
PCP is an example of:
a)
Undecidable problem
b)
Decidable problem
c)
Regular problem
d)
Context-free problem
33.
A solution to PCP is:
a)
A sequence of tile indices matching top and bottom strings
b)
A grammar rule set
c)
A regular expression
d)
A path in a graph
34.
The Modified PCP (MPCP) differs from PCP by:
a)
Having a fixed starting tile
b)
Unlimited tiles
c)
Different alphabets
d)
Allowing empty strings
35.
MPCP is used to prove:
a)
Undecidability of PCP
b)
Halting problem
c)
P = NP
d)
Context-freeness
36.
PCP is often used to prove:
a)
Undecidability of grammar equivalence
b)
Closure of RE languages
c)
Regularity of languages
d)
Parsing efficiency
37.
PCP involves two lists of:
a)
Strings
b)
Numbers
c)
Functions
d)
States
38.
A language L is recursive iff PCP can be:
a)
Reduced to L
b)
Reduced from L
c)
Independent of L
d)
Independent of L
39.
PCP belongs to which class of problems?
a)
Recursively enumerable but not recursive
b)
Recursive
c)
Regular
d)
Context-free
40.
PCP can be reduced from:
a)
Halting Problem
b)
TSP
c)
Sorting
d)
SAT
41.
Problems solvable in polynomial time belong to:
a)
P
b)
NP
c)
NP-Hard
d)
NP-Hard
42.
NP stands for:
a)
Non-deterministic Polynomial time
b)
Non-Polynomial time
c)
Non-Practical time
d)
Nominal Polynomial
43.
NP problems are:
a)
Verifiable in polynomial time
b)
Solvable in polynomial time only
c)
Recursive
d)
Recursive
44.
If P = NP, then:
a)
All NP problems become easily solvable
b)
All undecidable problems are solved
c)
PCP becomes decidable
d)
None
45.
NP-Complete problems are:
a)
In NP and NP-Hard
b)
Only in P
c)
Only NP-Hard
d)
Decidable
46.
SAT problem is:
a)
NP-Complete
b)
NP-Hard
c)
Decidable
d)
Undecidable
47.
If a problem A is NP-Hard and reducible to B in polynomial time, then B is:
a)
NP-Hard
b)
NP-Complete
c)
In P
d)
NP-Hard
48.
All P problems are:
a)
Decidable
b)
NP-Complete
c)
Undecidable
d)
NP-Hard
49.
Which of the following relationships is true?
a)
P ⊆ NP
b)
NP ⊆ P
c)
NP ⊆ NP-Hard
d)
P ⊆ NP ⊆ NP-Hard
50.
The open problem in theory of computation is:
a)
P vs NP
b)
Rice’s Theorem
c)
Post’s Correspondence Problem
d)
Halting problem
Reset
