Due: Jan 23 in class.
What is the definition of a decidable set?
If p is a polynomial over a variable x, a zero of p is a number x such that p(x) = 0. For example, 2 is a zero of polynomial x2 - 5x + 6
Let S be the set of all quadratic polynomials of a single variable x with integer coefficients that have two distinct real-valued zeros. For example, x2 - 5x + 6 is in S since p(2) = 0 and p(3) = 0.
Is S a decidable set? Justify your answer.
Let A be the set of all programs p that have the property that, when program p is run on string x, it produces the length of string x as output. Prove that set A is undecidable.