1.  [10 points]

A Turing Machine (TM) M recognizes the language

L(M) = {1n  j the binary representation of n does not contain any 0’s}:

(1n  is the string of n 1’s.)  Describe M in detail with just English text. Use sentences like, “M goes to the right until it inds a 1.”

2.  [10 points]

Let N+  = {1, 2, 3, . . . }. Let M be a Turing Machine (TM) with

L(M) = {0n 1n  | n ∈ N+ }

whose tape alphabet is Γ = {0, 1, 0(-) ,1(-) ,  }. Draw a state diagram of the

TM M. You may use abbreviations such as 1, 0 → L.  You don’t have to draw the reject state.  The TM rejects if it gets stuck, because the state diagram shows no move to continue.

3.  [5 + 10 = 15 points]

One can claim that in some sense, 2-tape TMs are not more powerful than 1-tape TMs.

(a) We want to know in which sense.  Fill in the box such that the whole line containing the box is a precise formulation of the claim.

Let Mk  be the set of k-tape TMs.

AM 2 M2  9M、2 M1

(b) Argue that the claim is true.

4.  [5 + 10 = 15 points]

Show that the set of functions from N+  ! N+  (with N+  = {1; 2; 3; : : : }) is not countable.

(a) What is the name of the method to show such a result?

(b) Prove this result.

5.  [5 + 2 + 8 + 10 = 25 points]

Assume we know that ECFG  is decidable, and we want to show that EDFA  is decidable with the help of a mapping reduction f.  Give the following details about this mapping reduction.

(a)  From where to where is the mapping reduction?

(b) What is the input of the reduction?

(c) What is the output of the reduction?

(d)  The most essential part of a mapping reduction is an equivalene between a property of the input and a property of the output (= f (input)). Write this equivalence for our case.

6.  [5 + 5 + 5 = 15 points]

The Collatz algorithm is deined as follows.

Input: n (a positive integer)

while n  1 do

if n is even then n = n/2 else n = 3n + 1

It is not known whether there are any n’s for which the Collatz algo- rithm does not halt.

Let L = fnb  j nb  is the binary representation of a positive integer n for which the Collatz algorithm does not haltg.

Answer with  “yes”, “no”, or “unknown” .

(a) Is L regular?

(b) Is L Turing recognizable?

(c) Is L(-) (the complement of L) Turing recognizable?