Important! These are all exam-level problems. Do not attempt these problems without a solid foundation in the subject and use them for exam practice.
1. Prove that the set of all programs is countably infinite.
Take any language that is complete. The length of a program in that language is finite, so it can be expressed as a finite bitstring. The set of all finite bit strings is countably infinite, and the set of all programs isn't any bigger than this, so the set of all programs is a subset of this. Hence, the set of all programs is countably infinite. 2. Prove this by a combinatorial argument. ∑ from k=0 to n of k*(n choose k) = n2n-1
The RHS says from n people, pick one person (n options), and then pick some, possibly empty, subset of other people.
The LHS says to first pick k people on the team, and then from the k people, pick the leader from them.
These are two different ways of doing the same thing, and hence, they are equal. 3. Show that the deadcoe problem is undecideable. The problem is: given a program P, an inpux x, and a line n in P, does P on input x ever execute line n?
Let's reduce this to the halting problem. Let's say that given any program, we replace the instruction corresponding to half with go to the the last lien of the program. If we can solve the deadcode problem, we can see if we ever get to this line and, if the problem says we do, we know whether or not the program halts. This would solve the halting problem.
The halting probolem, however, is undecideable, so, the deadcode problem must be undecideable as well.