Theoretical Computer Science (M21276)
Part B/4: More undecidable problems
(Dec 6 – Dec 10, 2021)
Question 1. Clearly state one undecidable problem. What are inputs/outputs of the problem? Give examples of input instances.
Copyright By PowCoder代写 加微信 powcoder
Question 2. Explain on an example of a polynomial equation with one variable/two variables why Hilbert’s tenth problem is partially decidable.
Answer: If we take f(x) (a computable function), we can use a TM to evaluate f(0), f(1), f(−1), f(2), f(−2), …and if there exists z such that f(z) = 0 we find it!
Question 3. For each of the following instances of the Post correspondence problem, find a solution or state that no solution exists.
a) {(a, abbbbb) , (bb, b)} over the alphabet {a, b}
Answer: The sequence of indices (1, 2, 2, 2, 2, 2) works since we then get: a bb bb bb bb bb =
abbbbb b b b b b.
b) {(10, 100) , (0, 01) , (0, 00)} over the alphabet {0, 1}
Answer: There is no solution since there are more digits in each of the right side than in the corresponding left side — 100 has more digits than 10, 01 more than 0 and 00 more digits than 0. Hence it will never be possible to generate two strings with the same number of digits.
c) {(ab, a) , (ba, b) , (a, ba) , (b, ab)} over the alphabet {a, b} Answer: The sequence of indices (1, 3, 2, 4) works, giving ababab.
d) {(1, 111), (0111, 0), (10, 0)} over the alphabet {0, 1} Answer: The sequence (2, 1, 1, 3).
e) {(ab, aba), (ba, abb), (b, ab), (abb, b), (a, bab)} over the alphabet {a, b} Answer: The sequence (1, 5, 2, 3, 4, 4, 3, 4) works.
Question 4. Show that for |Σ| = 1, the Post correspondence problem is decidable. That is there is an algorithm that can decide whether or not an input instance over a single- letter alphabet has an solution. Characterise the instances with a negative answer and in other cases describe how we can obtain a solution.
Answer: If |ti | > |si | or |ti | < |si | for all i, then clearly there is no solution. If this condition doesn’t hold, then either |ti| = |si|, for some i, which has a trivial solution, or there must exist a j and a k such that |tj| > |sj| and |tk| < |sk|. In the latter case, the PCP has a solution trjtqk, where r = |sk| − |tk| and q = |tj| − |sj|.
Question 5. Explain the difference between bounded and unbounded tiling problem. Why the bounded tiling problem is decidable? Why we can’t use a solution for the bounded tiling problem to solve the unbounded tiling problem.
Question 6. Show how the solvability of the Halting problem would imply the solution of the conjecture about perfect numbers: n is perfect if it is equal to the sum of its divisors (except itself), e.g. 6 = 1 + 2 + 3, 28, . . . . There is the conjecture there are no odd perfect numbers.
Answer: We could create a program which would check every perfect number starting from 6. It would only stop if it found a perfect number which is odd. Thus it would stop if our conjecture was false, and run forever if it was true. If we could determine whether this program halts, using a halting problem solution, we would know whether the conjecture was true or false.
Question 7. The number of all computable functions is countable (give a reason for that!). However, one student didn’t realise that and tried to prove that it is uncountable! Find a problem in his arguments.
Suppose we have the following effective enumeration of all the computable functions that take a single argument:
f0,f1,f2,...,fn,....
For each of the following functions g, explain what is wrong with the following diagonal- isation argument claiming to show that g is a computable function that isn’t in the list. “Since the enumeration is effective, there is an algorithm to transform each n into the function fn. Since each fn is computable, it follows that g is computable. It is easy to see that g is not in the list. Therefore, g is a computable function that isn’t in the list.”
a) g(n) = fn(n) + 1.
Answer: g(n) is not computable because fn(n) may not be defined.
b) g(n) = if fn(n) = 4 then 3 else 4.
Answer: g(n) is not computable because fn(n) may not be defined.
c) g(n) = if fn(n) halts and fn(n) = 4 then 3 else 4.
Answer: g is not computable because if fn(n) does not halt, there is no way to discover
the fact and output the number 4.
Question 8. Show that the following problem is decidable: Is there a computable function that, when given a computable function f, m, and k, can tell whether f halts on input m in k units of time?
Answer: Start a clock to count to k units of time, and simultaneously start the evaluation of f on input m. If the evaluation stops before the clock reaches k, then halt and return 1. Otherwise halt when the clock reaches k and return 0.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com