3. (a) Caesar's cipher is one of the simplest and most widely known encryption techniques, in which each letter in the original text in some alphabet is replaced by a letter some fixed number of positions down this alphabet. For example, in the standard alphabet {a,b, ..., z}, with a shift of 3, the letter a would be replaced by d, b would become e, and so on, the last three letters in the alphabet are replaced by a, b and c respectively. Describe formally (i.e., by means of a transition function) a Turing machine which encrypts (with shift 3) any word in the alphabet ? = {a,b, c, d, e}. [5] (b) Argue that the language {abm|n=0,1,...}U{ba"|n=0,1,...} over the alphabet {a,b} belongs to the complexity class P. You don't need to give a formal but merely an implementation level description of the relevant Turing machine, i.e., show with sufficient detail why such a machine exists, and that its complexity is polynomial. [5] (c) Let L be the language of all equations ao Xd +a_xd-1 + ... + ad-1X + ad = 0, with unknown X and integer coefficients ao, al,..., Ad-1, 2d, which have a solution in the integers. (i) Show that L is semi-decidable by describing, in general mathematical terms, an algorithm that takes an equation ao Xd + a_xd-1 + ... + ad-1X + ad = 0) with ao, Q2, ...,ad-1, ad Z as input and halts exactly when this equation has a solution in the integers. [5] (ii) Using the fact that L is actually decidable, describe an algorithm which for any equation aoXd +ajxd-1 +...+ad-1X + ad = 0 with ao, a2, ..., Qd-1, ad Z, decides whether or not it has integer solutions, and if it does, finds at least one such solution. [5]