Quiz 05 (March, 1st)
Statistics
There were 3 problems, each worth 10 points.
- Min: 8
- Median: 17
- Max: 30
Problem 1
Given: A is mapping reducible to B, which is mapping reducible to C.
What can you conclude about the decidability og A and/or C if
- B is known to be decidable,
- B is known to be undecidable?
Solution
If B is decidable then anything that reduces to it is decidable, so A would
be decidable. On the other hand a decidable set can reduce to both decidable
and undecidable sets so we cannot conclude anything about C.
If B is undecidable then anything it reduces to has to be undecidable
as well. Thus, C is undecidable. However, as we noticed above, if
something reduces to an undecidable set B then it does not necessarily
mean that it itself is undecidable.
Problem 2
Formally define the meaning of f(n) = o(g(n))
Solution
We say that f(n) = o(g(n)) if the limit, when n
approaches infinity, of f(n)/g(n) is equal to zero. Equivalently, f(n)
is in o(g(n)) if for any constant c > 0 there exists an integer n_0
such that for each n > n_0 we have that cf(n) <= g(n).
Problem 3
Formally define what is meant by TIME(t(n)).
Solution
TIME(t(n)) is a class of languages such that L
belongs to TIME(t(n)) if and only if there is Turing machine that
decides L and for any string x, this machine halts with O(t(|x|))
steps.
April, 5th