ASSIGNMENT
1. Construct a Turing machine which, given a string over the al- phabet {0, 1}, accepts the following language
{x | x contains the same number of 0's and 1's}.
2. (Problem 3.11 in the textbook) A Turing machine with doubly infinite tape is similar to an ordinary Turing machine, but its tape is infinite to the left as well as to the right. The tape is initially filled with blanks except for the portion that contains the input. Computation is defined as usual except that the head never encounters an end to the tape as it moves leftward. Show that if a Turing machine of this type accepts a language L, then there is a regular Turing machine (as defined in class) which also accepts L.
Hint: Suppose that the two-way infinite tape of the machine contains input a-ma-m+1 . . . a-2a-1a0a1a2 . . . an, for some input symbols ai ∈ Σ, which is preceded and followed by infinitely many blanks to the left and to the right.
Imagine that we "fold" the two-way infinite tape in the fol- lowing way
| a0 |
a1 |
a2 |
... |
| # |
a-1 |
a-2 |
... |
to turn it into two one-way infinite tapes (# is a new symbol, a delimiter.) At the beginning, we may assume that a-1 = a-2 = . . . = a-m = |_|
since we can fold the tape at any position. When the head is to the right of a0 the simulation is on the upper tape; if the head is to the left of a0, the simulation is on the lower tape. Your task is to provide the details. You do not need to write the explicit table of the transition function but define Q, Σ, Γ as precisely as possible and explain how the simulation proceeds.
3. Early on in the course, we mentioned that the problem of de- ciding whether a given positive integer n is prime is solvable in polynomial time but that the proof is highly nontrivial. This is based on the assumption that n is given in base 2, i.e. as a binary string. In this problem, we will see that primality has a much simpler algorithm, if we change the base in which we represent n; so the complexity of a problem does depend on how we represent the input.
Assume that n is represented in unary notation: namely, the string that represents n is 1n (the string of n ones.) In this representation, show that the Eratosthenes' Sieve which checks whether n is divisble by any integer ≤ √n runs in time O(n2) when implemented on a Turing machine. (You may assume that there exists a Turing machine which, given n, computes ⌈√n⌉, the first integer greater than or equal to √n.) The key to solving this is to understand how to check divisibility of one integer by another, if they are both given in unary notation.