# CS代写 CS 70 Discrete Mathematics and Probability Theory Fall 2021 – cscodehelp代写

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