CS 535
                                                       Fall 2008

                      Assignment #1 

                  Answers to selected problems


Date Due: Tuesday, September 16

Problems :

1. Problem 2.1, part 1 on page 27 - Only use the language 
 {0^n 1^n | n>0} instead of the one given in the problem. 

(Note: For this part you should give the full TM specification and program
as is done with parity in example 2.1, page 24. )

Answer: Will appear here in a couple of days. 

2. Problem 2.1, part 2 on page 27
(For part 2 you can just describe how the TM would work on an
arbitrary input and not give the full detailed program.)

Answer: Will appear here in a couple of days.




3. Prove that an infinite language L which is an infinite set of 
natural numbers is decidable if and only if there is a
one-to-one computable function f which enumerates L's elements
in increasing order.

Answer: 

=> First assume that we have an infinite set L (subset of N) that is decidable 
  i.e. we have a machine ML that halts on every input x of N and
 
  accepts iff x is in L. We will construct f by letting f(1) be the first 

  element in N accepted by ML, f(2) be the second, ... , f(n) 
  be the nth element, and so on. Specifically, to define f(1), run ML on  
  0,1,2,3,... etc. Since ML is a decider we can find the 1st element accepted, 
  the 2nd, 3rd, etc. Notice this function is computable, this is straight from 
  ML being a decider. The function is one to one since L is a subset
  of N, and it is in increasing order since we proceed through N in order.

<= Now assume we have a computable function that is one to one with a
set L and outputs its elements in increasing order. Create machine
ML as follows:

On input w

For i: 1, 2, ...


    compute f(i) if f(i) = w then accept, if get to some f(i) > w then halt and 

    reject. 



4. Problem 2.3,on page 30

This problem concerns a two tape TM, something we haven't discussed yet 
in class, but this is a simple concept and the short discussion of this in the 
textbook should be sufficient. You can also just google "multi-tape Turing
machine" to find other simple examples. 

Answer: In the example of a two tape TM accepting L which is given in the 
textbook, the TM accepts every input string s which reads the same left to right
as it does right to left and which has even length. This last requirement
(of s having even length) is checked directly by the TM. 

If this check for even length is left out then the TM will accept strings of 
odd length as well if they read the same left to right
as from right to left. These string, such as 000 or 1101011 are not in L 
and should not be accepted.

5. Problem 3.15 on page 70
Show that every infinite decidable set has an undecidable subset.

Answer (brief sketch): 

This problem was discussed in class. 

Following the hint given for this problem, let S be a decidable infinite set.
And we assume there is an undecidable language L where L consists of strings 
which are from a finite alphabet A. 

Since S and A* are both countable, and since S is decidable,
we can find a 1-1, onto and computable function f which maps A*
1-1 and onto S. Furthermore f is COMPUTABLE (this is crucial and follows from 
S being decidable).

Now let L' be the image of L under f. Clearly L' is a subset of S.

We can now prove (by contradiction) that L' is undecidable, giving the desired result. 


Proof: Assume L' were decidable via a TM T, then given x in A*, to decide if x is in L,

1. Compute f(x) = x', an element in S.
(Note: Here we need f to be computable.)

2. Run T on x' to decide if x' is in L'.

If x' is in L' then x is in L, and

If  x' is not in L' then x is not in L.