### CS4123 Theory of Computation  Homework 2 - B 2002

#### By Beth Donovan and Carolina Ruiz

Due Date: Monday, November 11th at 4:30 pm.
Help session: Friday, November 8, 3-4 pm, FL141

#### Problems

1. (32 points) [Taken from Kozen, 1997 and Savage, 1998] Show that each of the following functions is primitive recursive.

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

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

• less_than_or_equal(x, y) = 1 if x less than or equal to y, else 0.

• sign(x) = 1 if x >0, else 0.

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. 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)).

Turn in a printout of your code and a transcript showing the output produced by your implementation of the first three functions on each of the following {x, y} set of inputs:  {7, 2}; {3, 6}; {5, 5}; {9, 8}.  Use 2, -3, 0, and 1 for the last function.

2. (8 points) [Taken from Moret, 1998] Verify that the function f defined as follows:

f(0, x) = g(x)
f(i + 1, x) = f(i, h(x))

is primitive recursive whenever functions g and h are primitive recursive.

3. (20 points) [Taken from Kozen, 1997] Given an arbitrary Turing machine M, does M have at least 481 states? Describe a Turing machine that solves this decision problem.

4. (20 points) Consider the following decision problem: Given an arbitrary Turing machine M, is there a word w for which the computation of M with input w halts in fewer than 481 transitions?
1. Is this problem 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.2 from textbook (page 169).

1. (10 points) Problem 4.7 from textbook (page 169).

#### Homework Submission

• Code and Execution transcript: Submit the files specified below using the turnin program. The name is the assignment under which you should submit is hw2.

Please document your code following the Departmental Documentation Standard, and as part of the documentation, include instructions on compiling, executing, and using your program.

• hw2_prb1.[lastname] containing the program that you wrote to implement each and everyone of the functions required in Problem 1 of this homework. This file should also contained all the auxiliary functions (including the basic ones, PLUS, etc. etc.) that were needed in order to implement the required functions.

The lastname/extension of this file will depend on the programming language you used (eg. it'll be hw2_prb1.c if you wrote your program in C).

• hw2_prb1.transcript containing the results of running each of required functions over the test cases provided.

• Written part: You can submit the rest of the homework assignment in any of the following ways. Make sure you hand it in BY 4:30 pm on Monday, November 11th.
• by submitting an electronic version of your solutions using the turnin system as explain above.
• by handing in your solutions during class on Monday, November 11th.
• by leaving your solutions in my mailbox (CS office FL233). PLEASE MAKE SURE YOU LEAVE YOUR SOLUTIONS IN **MY** MAILBOX (the one UNDER the arrow marked with my lastname RUIZ).