Turing machines and Computability, II

1. Assume f : N → N is computable and X ⊆ N is decidable. Will f(X) = {f(x) : x ∈ X} and f^{−1}(X) = {x : f(x) ∈ X} be decidable?

2. For A, B ⊆ N let A ⊕ B denote {2x : x ∈ A} ∪ {2x + 1 : x ∈ B}. Show: A, B ≤_{m} A ⊕ B. Moreover, if A, B ≤_{m} C then A ⊕ B ≤_{m} C.

3. There are A, B such that A ≰_{m} B and B ≰_{m} A.

4. Is the set of (codes of) TM’s that compute total functions decidable? Is it r.e.?

5. Consider the set of all TM’s {0, 1}^{∗} → {0, 1}^{∗} whose running time on inputs of length n is bounded by 2^{n}. Is it decidable?

6. Show: every regular language is decidable. (^{∗}) What about context-free languages?

7. Acceptor TM’s M and N are called equivalent, if they accept the same language. Is the problem of equivalence of TM’s decidable? What about the equivalence problem for finite deterministic automata?

8. Show that the fragment of FOL (first order logic) in the language with just a single one-place predicate symbol P (x) is decidable.

9. (Huiswerk) Let ϕ_{e} : N → N denote the partial function computable by a TM with a code e. Consider the following two sets:

A = {x : ϕ_{x}(x) = 0}, B = {x : ϕ_{x}(x) = 1}.

Show: (a) A and B are r.e.; (b) there is no decidable set C such that A ⊆ C and B ⊆ N \ C. Such sets are called recursively inseparable.