CS 535
                                                       Fall 2009
                      Assignment #3


Date Due: Thursday, October 22

Reading: None


Problems :

1. Problem 3.3 on page 48

2. Prove a direct that (1) implies (2)  where

(1). There is a computable relation R(x,y) such that
x is in L  iff there exists a y where R(x,y).

(2). L is the range of a partial computable function.

By direct proof I mean do not use other equivalences of a problem being c.e. but 
rather do this directly from what you are given in (1) and (2).

3. Page 70, problem 3.19.

4. Prove that it is undecidable to prove whether a Turing machine halts
on every input string that begins with a 1. 

Hint: Reduce the program termination problem (PT) to this problem. 

5. Page 71, problem 3.31.

6. The twin prime conjecture is an open problem in number theory.
It states that: There are infinitely many pairs of natural number of the 
form n, n+2 such that both n and n+2 are primes. 

For example, 3,5 and 11, 13 are both pairs of twin primes. 
It is not known if there are infinitely many such pairs.

(i) Prove that the set of all twin primes is c.e. 

(ii) Is the set of all twin primes decidable ? Why or why not ? 

7. Show that there is an algorithm to decide, given a fixed integer k, 
whether a TM M on input x halts without ever using more the k tape squares on
M's tape.

More precisely, show that for a fixed number k, 
 {(M,x) | M(x) halts and uses no more than k tape squares}
is decidable.