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

#### PROF. CAROLINA RUIZ

Due Date: Tuesday, April 2nd at 5 pm.
Help session: Monday, April 1st, 1-2 pm Room: AK219
Late Policy: No late homework will be accepted

#### Problems

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

• f(n) = 2*n + 3

• half(n) = the integer part of n divided by 2
hence, half(7) = 3 and half(22) = 11.

• even(n) = 1 if n is an even number, and 0 otherwise.

• perfect_square(n) = 1 if n is a perfect square, and 0 otherwise.
n is a perfect square if n = m*m for some integer m.

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 each function on each of the following inputs: 5, 8, 9, 12.

2. (10 points) The purpose of this exercise is to show that definition by cases preserves the property of being primitive recursive. More precisely, consider the function f: NxNxN -> N defined by cases as follows:
```               /
| g(k,m,n),        if p(k,m,n)=1
f(k,m,n) := |
| h(k,m,n),        if p(k,m,n)=0
\
```
where g and h are functions from NxNxN -> N, and p is a function from NxNxN -> {0,1}.

Prove that if g, h, and p are all primitive recursive functions, then f as defined above is also primitive recursive.

3. (20 points) (Adapted from Sudkamp, p. 347) Given an arbitrary Turing machine M and input string w, will the computation of M with input w halt in fewer than 100 transitions? Describe a Turing machine that solves this decision problem. In other words, show that the following language L is decidable:
L = { < M,w > | M halts on input w in fewer than 100 transitions}

4. (20 points) Exercise 4.10 from textbook (page 169).

5. (20 points) Exercise 4.12 from textbook (page 169).

1. (10 points) Problem 4.13 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 5 pm on Tuesday, April 2nd.
• by submitting an electronic version of your solutions using the turnin system as explain above.
• by handing in your solutions during class on Tuesday, April 2nd.
• by handing in your solutions during John's office hour on Tuesday, April 2nd, 4-5 pm.
• 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).