Description

1 Countability and the Halting Problem
Prove the Halting Problem using the set of all programs and inputs.
a) What is a reasonable representation for a computer program? Using this definition, show that the set of all programs are countable. (Hint: Python Code)
b) We consider only finite-length inputs. Show that the set of all inputs are countable.
c) Assume that you have a program that tells you whether or not a given program halts on a specific input. Since the set of all programs and the set of all inputs are countable, we can enumerate them and construct the following table.

p1 H L H L …
p2 L L L H …
p3 H L H L …
p4 L H L L …
… … … … … …
An H (resp. L) in the ith row and jth column means that program pi halts (resp. loops) on input xj. Now write a program that is not within the set of programs in the table above.
d) Find a contradiction in part a and part c to show that the halting problem can’t be solved.
2 Fixed Points
Consider the problem of determining if a function F has any fixed points. That is, given a function F that takes inputs from some (possibly infinite) set X , we want to know if there is any input x ∈X such that F(x) outputs x. Prove that this problem is undecidable.
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.