1. Suppose we want to write a TM program to decide the language of strings of the form ww over the alphabet {a,b}.

a) Describe an algorithm that works with a conventional (deterministic) TM. You don't have to give details about each state, just describe the process in broad terms like "move to the right end of the string" etc.c

b) Describe an algorithm that works with a nondeterministic TM and makes use of the nondeterminism. Hint: "guess" where the last character of the first w is.

2. Consider the language L of TMs that halt when given a blank tape as input.

a) Let's assume for the moment that L is decidable and decided by some TM N. Now, suppose we want to determine whether or not a particular TM M will eventually halt when given input s. How can we modify M slightly to obtain a TM M', such that acceptance of M' by N will imply that M halts on s? Hint: The code for M' will need to have s "hardcoded" into it.

b) What does Part a) suggest about the decidability of L?

3. Suppose that languages L1 and L2 are Turing recognizable. Is L1 union L2 always Turing recognizable? Justify your answer.

4. Consider the language L of TMs that recognize some nonempty language. Is L Turing recognizable? Justify your answer.

5.Using a regular expression, describe the language decided by the TM program below (Assume input alphabet = {a,b} and that the tape head starts just to left of first nonblank.)

1,_,2,_,>

2,_,R,_,<

2,a,3,a,>

2,b,4,b,>

3,a,3,a,>

3,b,3,b,>

3,_,5,_,<

5,b,A,b,>

5,a,R,a,>

4,a,4,a,>

4,b,4,b,>

4,_,6,_,<

6,a,A,a,>

6,b,R,b,>

6) True or false

a) Every regular language is decidable

b) Every finite language is regular

c) The empty language is decidable.

d) Some languages are decidable but not Turing recognizable.

e) There is a TM that recognizes the language of (TM M, input s) pairs such that M halts on s.

f) Every context free language is decidable.

g) The number of Turing machines is uncountable.

e) There is a TM that recognizes the language of (TM M, input s) pairs such that M loops on s.

7) Is the set of Turing decidable languages closed under complementation? Why or why not?

8) Is the set of recursively enumerable languages closed under complementation? Why or why not?

9) Write a TM program that decides the language of strings of length 1, where the input alphabet is {a,b} and the tape alphabet is {a,b, blank}. Assume that the tape head starts on the blank square just to the left of the first nonblank character (if there is a nonblank character).