(b) f:N N N such that f(a,b) = fa/b] (c) f:N N such that f (n) [log, nl. 7. Define Nondeterministic Turing machines to accept the following languages. (a) {xx|x {0,1}" } (b) X|XE {0,1)* and x = x 8. Define a multiheaded Turing machine, a model in which each tape can have k tape heads. Prove that a Deterministic Turing Machine (DTM) with one work tape can simulate a two-headed Turing machine. 9. Design a Turing machine which computes the function f(n,n,) = minn, n,) for all non-negative integers n, and n. 10. Design a Turing machine which computes the function f(n) = 3 if n 25 and f(n) = 0 if n=0, 1, 2, 3 or 4. 11. Construct a Turing machine which computes the function f(n)=n mod 12. Design a Turing machine which recognizes the set {0"1"2" |n 20%. 13. Design a TM that recognizes the set of all bit strings that contain an even number of 1. 14. Construct a TM that recognizes the set of all bit strings which end with a 0. 15. Design a Turing machine with tape symbols 0, 1 and B that given a bit string as input, replaces all but the leftmost 1 on the tape with Os and does not change any of the other symbols on the tape. 16. Design a TM with tape symbols 0, 1 and B that replaces the first with a 1 and does not change any of the other symbols on the tape. 17. Design a TM that recognizes the set {02"1" |n20}. 18. Show that the recursiveness problem of Type-0 grammars is unsolvable. 19. Show that the problem of determining whether or not a TM over {0,1) will print ever the symbol 1, with a given tape configuration is unsolvable. 20. Show that there exists a TM for which the halting problem is unsolvable