CS4123 Theory of Computation  Homework 2 - B 2004

Due Date: Tuesday, November 16th at 12:00 noon.
NO SUBMISSIONS WILL BE ACCEPTED AFTER 12:05 PM.

Problems

1. (32 points) Show that each of the following functions is primitive recursive.

• div(x, y) = x/y using integer division.

• log(n,b) = "integer logarithm in base b of n". For instance log(10,2)=3 because 2 to the 3rd power is 8, and 2 to the 4th power is 16; and log(81,3)=4 because 3 to the 4th power is 81.

• maxk(n1,n2,...,nk) = "the maximum among n1,n2,...,nk". For instance, max7(2,6,9,3,9,1,6) = 9.

Hint: There are several ways to show that this function is primitive recursive. Here are two possibilities:

• Show that for each k = 2, 3, 4, .... the maxk function is primitive recursive. That is, show that max2(n,m) = "maximum between n and m" is primitive recursive. Then show that max2 can be used to show that max3 is primitive recursive, and in general, maxi can be used to show that maxi+1 is primitive recursive. Or,

• Define maxk(n1,n2,...,nk) = max_auxk(n1,n2,...,nk,k), where max_auxk(n1,n2,...,nk,i) = "the maximum among n1,n2,...,ni" for i <= k, and show that max_auxk is primitive recursive.

• averagek(n1,n2,...,nk) = "(n1 + n2 + ... + nk)/k".

Note: The PLUS function was defined in class for only 2 arguments. If for your solutions for this part you need a more general PLUSk(n1,n2,...,nk) function, make sure to define it and to prove that it is primitive recursive.

For each one of them:

1. (4 points each) Write down a proof that the function is primitive recursive. That is, show that the function can be computed from the basic functions or previously shown primitive recursive functions (in class or handouts) using composition and primitive recursion definition.

2. (4 points each) Implement the function using a high level programming language. For the case of maxk and averagek, take k=5. That is, implement max5(n1,n2,...,n5) and average5=(n1,n2,...,n5). Your program should satisfy all the following conditions:
• (i) The only constant used is 0 (zero)
• (ii) The only functions used are
• incrementing a value by one (succ)
• functions that you have previously coded using this set of conditions. For instance, if you need to use the function PLUS defined in class, you need to implement this function, following the definition given in class as part of your code.
• (iii) It can use composition of functions
• (iv) It can use recursion (i.e. a function can invoke itself), following a definition by primitive recursion.
• (v) You cannot use anything not described by the previous items. That is, you CAN ONLY use constants/functions/techniques described in (i) to (iv).

For instance, if you need to use a constant, say 2, different from 0, then you will express it as succ(succ(0)).

Submit a file with your code and a transcript showing the output produced by your implementation on the following set of inputs:

• For the div(x, y) and log(n,b) functions use inputs:
• (15,3)
• (3,15)
• (0,0)
• (16,4)
• For the maxk(n1,n2,...,nk)
• (15,3,8,4,6)
• (3,12,0,1,2)
• (0,0,7,6,7)
• (6,4,4,6,12)

Hint: See the code provided for the solutions of HW2 in D-term 2002, and the code provided for the solutions of HW2 in B-term 2002.

2. (8 points) Show that the function root(c0,c1,c2) = "smallest natural number root of the quadratic polynomial c0 + c1*x - c2*x2" is mu-recursive.
Hints: Here are a couple of comments on this:

• Note that there is a formula to solve the quadratic equation c0 + c1*x - c2*x2 = 0, or equivalently -c0 -c1*x + c2*x2 = 0. The formula is:
root(c0,c1,c2) = "[1/(2*c2)]*[c1 +- sqrt((c1*c1) + 4*c0*c2)]"
If you apply that formula, two solutions can be obtained. HOWEVER, those solutions are not guaranteed to be integer numbers (not even real numbers as they may be complex numbers containing an imaginary part).

• Hence, the suggested procedure is to:
• use mu-minimization, checking if 0 is a root; if not trying 1; if not, trying 2; etc.
• show that this minimization is "bounded" that is, that there is an upper bound for the number that needs to be tried. In other words, that the procedure above (trying 0, 1, 2, ...) doesn't need to go for ever, and that there is a number, say u, such that it is enough to try 0, 1, 2, ...., u and if none of those numbers are roots of the equation, then there are no integer roots for the equation.

You should compute that upper bound explicitly in terms of c0, c1, and c2. For inspiration on how to do so, see problem 3.18 on p.149 of your textbook.

3. (20 points) Show that the following language is decidable by constructing a Turing machine (pseudo-code is enough) that decides it:
L = { <G,s,t> | G is an undirected graph G=(V,E); s and t belong to V; and there is a path from s to t in G}.

4. (20 points) Consider the following language:
L = { <D,k> | D is a DFA and D doesn't accept any word of length k}.
1. Is this language decidable? Is it semi-decidable?
2. Explain your answer to Part 1. That is, if you said that the problem is decidable, construct a TM that decides it. If you said that the problem is semi-decidable, construct a TM that semi-decides it. If you said that the problem is not decidable AND not semi-decidable, prove that it is so.

5. (20 points) Exercise 4.16 from textbook (page 170).