CS 70 Discrete Mathematics and Probability Theory Fall 2021
1 Counting Cartesian Products
For two sets A and B, define the cartesian product as A×B = {(a,b) : a ∈ A,b ∈ B}.
(a) Given two countable sets A and B, prove that A × B is countable. (b) Given a finite number of countable sets A1,A2,…,An, prove that
is countable.
2 Counting Functions
A1 ×A2 ×···×An
Are the following sets countable or uncountable? Prove your claims.
(a) The set of all functions f from N to N such that f is non-decreasing. That is, f (x) ≤ f (y) whenever
CS 70, Fall 2021, DIS 7A 1
(b) The set of all functions f from N to N such that f is non-increasing. That is, f (x) ≥ f (y) whenever x≤y.
3 Undecided?
Let us think of a computer as a machine which can be in any of n states {s1,…,sn}. The state of a 10 bit computer might for instance be specified by a bit string of length 10, making for a total of 210 states that this computer could be in at any given point in time. An algorithm A then is a list of k instructions (i0,i2,…,ik−1), where each il is a function of a state c that returns another state u and a number j. Executing A (x) means computing
(c1, j1) = i0(x), (c2, j2) = ij1(c1), (c3, j3) = ij2(c2), … until jl ≥ k for some l, at which point the algorithm halts and returns cl−1.
(a) How many iterations can an algorithm of k instructions perform on an n-state machine (at most) without repeating any computation?
CS 70, Fall 2021, DIS 7A 2
(b) Show that if the algorithm is still running after 2n2k2 iterations, it will loop forever.
(c) Give an algorithm that decides whether an algorithm A halts on input x or not. Does your contruction
contradict the undecidability of the halting problem?
4 Code Reachability
Consider triplets (M,x,L) where
M is a Java program
x is some input
L is an integer
and the question of: if we execute M(x), do we ever hit line L? Prove this problem is undecidable.
CS 70, Fall 2021, DIS 7A 3