Assignment 7

CS385-Theory of Computation

Assignment 7

Due Thursday, November 15

Problems from the Text

3.1(a,c,d),
3.2(b,c,d),
3.8,
3.7,
3.15(c,d),
3.16(c)

Notes: For 3.1 and 3.2, you work with the "formal description", but for 3.8, use an "implementation-level description" and for 3.15 and 3.16 "high-level" descriptions. That is, for 3.15(c) you are really demonstrating: "if there is an algorithm for determining if a given string w belongs to L, then there is an algorithm for determining if a given string belongs to L*". For decidable languages (3.15) the algorithms eventually terminate regardless of the input, answering either "yes" or "no". For Turing-recognizable (also called recursively-enumerable languages) the algorithms may go into infinite loops when started on some inputs; the language recognized is the set of strings for which the algorithm eventually halts and says "yes".

In 3.7, the kinds of multivariate polynomials being talked about are things like

4xyz+2xy²-3x³z⁴+2xy-7.

You should assume that the coefficients, as in the example above, are all integers. The problem is, really, to show that one can decide whether such a polynomial has a root with integer components, and you're asked to explain why the given solution to this problem is wrong. A good way to answer this is to show how you would make it right (you can even assume, to simplify the problem, that the number of variables in the polynomial is 3, as in this example).

Additional Problem

This concerns the countable and uncountable sets discussed in Chapter 4 and in class.

Consider one-variable polynomials with integer coefficients, like 3x⁴-7x³+2x+5.

(a) Show that the set of such polynomials is countable.

(b) Show that the set of real numbers that are roots of such polynomials, is countable. These numbers are called algebraic numbers, and they include such values as the square root of 2, which is a root of x²-2, as well as all rational numbers (since p/q is a root of qx-p). HINT: A polynomial of degree n can have at most n different roots.

(c) Conclude that there are real numbers that are not algebraic. (These are called transcendental numbers.) Is the set of transcendental numbers countable or uncountable? Explain. (It is rather hard to prove that any given real number is transcendental, even though, in a sense, nearly every real number is transcendental.)