More Countability
Given:
• A is a countable, non-empty set. For all i ∈ A, Si is an uncountable set.
• B is an uncountable set. For all i ∈ B, Qi is a countable set.
For each of the following, decide if the expression is "Always Countable", "Always Uncountable", "Sometimes Countable, Sometimes Uncountable".
For the "Always" cases, prove your claim. For the "Sometimes" case, provide two examples – one where the expression is countable, and one where the expression is uncountable.
(a) A∩B
(b) A∪B
(c) Si∈A Si
(d) Ti∈A Si
(e) Si∈B Qi
(f) Ti∈B Qi
1
2 Hello World!
Determine the computability of the following tasks. If it’s not computable, write a reduction or self-reference proof. If it is, write the program.
(a) You want to determine whether a program P on input x prints "Hello World!". Is there a computer program that can perform this task? Justify your answer.
(b) You want to determine whether a program P prints "Hello World!" before running the kth line in the program. Is there a computer program that can perform this task? Justify your answer.
(c) You want to determine whether a program P prints "Hello World!" in the first k steps of its execution. Is there a computer program that can perform this task? Justify your answer.
3 Computability
Decide whether the following statements are true or false. Please justify your answers.
(a) The problem of determining whether a program halts in time 2n2 on an input of size n is undecidable.
(b) There is no computer program Line which takes a program P, an input x, and a line number L, and determines whether the Lth line of code is executed when the program P is run on the input x.
