Reference no: EM132868713

Question 1.(a) Show that {A, B, C, D}∗ is enumerable by describing a listing of all its elements that qualifies as an enumeration by the definition in the lecture notes

(b) Based on the listing you provided in question (a), give an ordering on the set {A, B, C, D}∗. That is, define mathematically when a strings from {A, B, C, D}∗ appears before another string s' from {A, B, C, D}∗.

(c) Assume that in dictionary ordering, A comes before B which comes before C which comes before D and hence A B C D comes before B A A A, etc. Is the listing of A, B, C, D ∗ in dictionary ordering an enumeration according to the definition in the lecture notes? Justify your answer.

(d) Give an encoding function for A, B, C, D ∗. (Hint, you could use the Fundamental Theorem of Arithmetic and prime numbers.)

(e) Show that the function you gave in question (d) above is indeed an encoding of {A, B, C, D}∗.

(f) Give the encoding of each of the strings ABCD and BAAA according to the function you gave in question (d) above and calculate the resulting number.

(g) Give a Gödel numbering of {A, B, C, D}∗. Fully justify your answer.

Question 2. Consider the Turing machine M whose graph is given in the attached DATASHEET.

(a) Give the formal definition of this Turing machine.

(b) Consider the following tape contents t:

Remember that we always start at location 0. Does the Turing machine M halt with input tape t? If it does not, explain in detail why not. If it does, give all the computation sequence (i.e., all the computation configurations from initial to last) and clearly specify the final configuration.

(c) For machine M and input tape t of question (b), give the output tape.

(d) Repeat questions (b) and (c) for tape contents t' where t' is:

(e) Say what the Turing machine actually does when given one single input as a unary number.

(f) Show that the function g from N to N is Turing-Computable where:

g(n) = n - 1 if n ∈ N and n > 0
g(n) =  0 otherwise

(g) Let pre be the function from N² to {0, 1} such that

pre(n, m) = 1 if n, m ∈ N and n = m - 1

pre(n, m) = 0 Otherwise

Is the decision problem pre solvable or unsolvable? Fully justify your answer.

Question 3. We Gödel number the possible moves by a Turing machine as follows:

GN_m(R) = 0 GN_m(L) = 1 GN_m(0) = 2.

We Gödel number an action A = ((q_i, s_j) ›→ (q_k, s_l, X)) of a Turing machine as follows:

GNa(A) = 11ⁱ × 7^j × 5^k × 3^l × 2^GN_m(X) .

For a Turing machine TM with action table A₁, A_2, • • • A_n, we calculate GNa(A_i) for each 1 ≤ i ≤ n and then order the GNa(A_i)s (which are all natural numbers) in descending order B₁ > B₂ > • • • > Bn and use these to Gödel number the Turing machine TM as follows: GN (TM ) = p₁^B1 × p₂^B2 × .... p_n^Bn where p₁ is the first prime (it is 2 and not 1), p₂ is the second prime (it is 3), p₃ is the third prime (it is 5), p₄ is the fourth prime (it is 7),
etc.

(a) Give the graph of a Turing machine M' that takes a number given in unary notation, and returns the number and its triple (again in unary notation) separated by a blank space. Here is an example of an input/output of machine M^':

(b) Show that the problem q given below is related by the reducibility relation to a decision problem you have already seen in this paper and decide whether q is solvable or not justifying your answer.

Instances of q: every pair (i, j) ∈ N²
Question of q: Is j = i + 1?

(c) Use GN_m, GN_a and GN to Gödel number the Turing machine M given in your DATASHEET showing all the steps of numbering the moves, the actions and the machine itself.

(d) For each of the numbers 21 and 13, state whether it is the Gödel number by GN_a of an action and if so give the action. If not state why not.

(e) For each of the numbers 16²¹ and 4³, state whether it is the Gödel number by GN of a Turing machine and if so give the Turing machine. If not state why not.

Attachment:- DSA.rar