CS181作业代写 数学作业代写

CS181 Winter 2019 – Problem Set #4 Solutions

CS181作业代写 (20 points) Show that the set of three-dimensional coordinates (x, y, z) x, y, z Z has size equal to N.Solution: (x, y, z) x, y, z Z = ZZZ.

1.(20 points) Show that the set of three-dimensional coordinates (x, y, z) x, y, z Z has size equal toN. CS181作业代写

Solution: (x, y, z) x, y, z Z  = Z Z Z.  We show  Z Z Z = N N N = N via a sequence of three bijections.

First we exhibit a bijection from N N N to Z Z Z.  Let f : N Z be the bijection from

N to Z which we defined in class. Let f ^j((x, y, z)) = (f (x), f (y), f (z)). We show that f ^j is a bijection. f ^j is injective: for any two (x, y, z), (x^j, y^j, z^j) such that f ^j(x, y, z) = f ^j(x^j, y^j, z^j), we have that x^j = x, y^j = y and z^j = z by the injectivity of f . Similarly, f ^j is surjective: for any (x, y, z) Z  Z  Z, there is an x^j, y^j and z^j all in N where f (x^j) = x, f (y^j) = y and f (z^j) = z. So f ^j(x^j, y^j, z^j) = (x, y, z).CS181作业代写

Now  we  exhibit a bijection from N N N to N N.

Let  g : N N N be the bijection from N N to N which we defined in class.  Let g^j(x, y, z) = (g(x, y), z).  We show that g^j is abijection.CS181作业代写

g^j is injective: for any two (x, y, z), (x^j, y^j, z^j) such that (g(x, y), z) = g^j(x, y, z) =g^j(x^j, y^j, z^j) = (g(x^j, y^j), z^j),  we  have  that  x^j  = x, y^j = y,  and  z^j  = z  by  the  injectivity  of f .  Similarly,  g^jis  surjective:  for  any(a, z) N N, there is an x^j, y^j such that (a, z) = (g(x^j, y^j)z) = g^j(x^j, y^j, z^j) by the surjectivity of g.

We can combine the bijections f ^j : N × N × N → Z × Z × Z, g^j : N × N × N → N × N, and g : N × N → N to get a bijection from Z × Z × Z to N.

2.(30 points). Let us define Fast-Rewind Turing Machines (FRTM).

They are  similar  to Turing Machines, except that the head of an FRTM is not allowed to move left one cell at a time. Instead, the head of the FRTM must  move  left only all the way  to the left-hand end  of the tape (i.e. the first cell).  The head of the FRTM  can move  right one step at a time,  justlike the usual Turing  The transition function for the FRTM is of the form

δ : Q × Γ → Q × Γ × {R, F IRST }.CS181作业代写

Explain how to convert any Turing Machine into an FRTM. A full proof is not needed, you only need to give an explanation of the intuition behind why your transformation works.

Solution: There are several ways to solve this. Here is one way.

In order to simulate the right side move of a Turing Machine, we don’t need to do any ad- ditional work. The corresponding FRTM can just move one step right whenever the original Turing Machine wants to move right.

The harder direction is getting an FRTM to simulate the left side move of a regular Turing Machine. For an FRTM to simulate an ordinary turing machine’s left moves, we use the following algorithm. Suppose the head wants to move one step left from the cell it is currently on.CS181作业代写

(a)Markthe current  That is, if the current cell had symbol α on it, now make it α.

(b)Move  all the way  left to the first cell of the tape.

(c)Copythe entire tape one cell to the right, except for the mark which is kept on the same tape cell.

(d)Resetagain to move all the way left to the start of the tape.CS181作业代写

(e)Scan right till you find the cell with the mark. This is the cell one step to the left of the original cell. Remove the mark.

At the end of this procedure, the FRTM head ends up one spot to the left of where it originally was without modifying the rest of the tape.

3.(50 points). In class, we showed the existence of two kinds of infinities. Let Σ = {0, 1}and CS181作业代写

L = {L | L ⊆ Σ^∗}.  We showed that |Σ^∗| is not the same as |L|.

We briefly describe the proof below and establish some notation. The proof proceeds by contradiction. Let (s, 0, 1, 00, 01, 10, 11, . . .) be a given enumeration of strings in Σ^∗. We assume for the sake of contradiction that there exists someenumeration (L₁, L₂, L₃, . . .) of languages in . Then we proceed by constructing a language L^DIAG such that i, L^DIAG = L_i via Cantor’s Diagonalization to establish a contradiction.

(a)(10 points) CallL^DIAG

= L^DIAG. Construct another language L^DIAG

ƒ= LDIAG

via diagonalization which is also not present in the enumeration (L₁, L₂, L₃, . . .). Thus L^DIAG  would have also proved to us that |Σ^∗| = |L|.CS181作业代写

(b)(15points) Construct an infinite set of languages LDIAG = {L^DIAG, L^DIAG, . . . , L^DIAG, . . .}

1 2 i via diagonalization by providing a description of L^DIAG such that

• ∀j,j ƒ= i, L^DIAG ƒ= L^DIAG.i j

• ∀j,L^DIAG ƒ= L_j.

Formally prove your construction by induction.CS181作业代写

(c)(15 points) Construct one more language L^SUPERDIAG such that

• ∀j,LSU P ERDIAG  ƒ= LDIAG  and
• ∀j,LSU P ERDIAG  ƒ= Lj

Briefly explain why your language satisfies the above properties.

(d)(10points) Construct yet another language L^SUP ERDIAG that is different from L^SUP ERDIAGsatisfying the same properties as part (c). Briefly explain your answer.

Solution:

Lets name the procedure that generates L^DIAG from the sequence (L₁, L₂, . . . , ) as Cantor’s diagonalization.

(a) Intuition: CS181作业代写

Consider the sequence (L^DIAG, L₁, L₂, . . .). Set L^DIAG be the language obtained by 1 2 using cantor’s diagonalization on this sequence.

Details:

Consider the sequence (L^DIAG, L₁, L₂, . . .). We will show that there exists a language L^DIAG that is not part of this sequence using Cantor’s diagonalization.

Consider a matrix M that has the enumeration of all strings in Σ^∗ along it’s columns and the enumeration (L^DIAG, L₁, L₂, . . .) along it’s rows. The entries of the matrix aredefined as follows:  M [i, j] = 1 if string j  belongs to language i and M [i, j] = 0 if string j doesn’t belong to language i. Now, let’s define a language L^DIAG by complementing the diagonal of the matrix M . That is, look at the diagonal. For each element in the diagonal,  if M [i, i] = 1,  then don’t include string i in L^DIAG while if M [i, i] = 0,  then we include string i in L^DIAG.CS181作业代写

Now, we show that such a language L^DIAG doesn’t exist in the list (L^DIAG, L₁, L₂, . . .).

Suppose it did exist in the list.  Let’s say it was  the k^th element in the list.  Let’s look  at  the  entry  M [k, k]. Suppose  M [k, k] = 1,  then  it  means  that  string  k  lies  in  the language L^DIAG by the definition of the matrix. However, by the definition of L^DIAG,if M [k, k] = 1, then string k does not belong to L^DIAG. Similarly, Suppose M [k, k] = 0,then it means that string k does not belong to the language L^DIAG by  the definition of the matrix. However, by the definition of L^DIAG, if M [k, k] = 0, then string k does belong to L^DIAG. Thus, in both cases we arrive at a contradiction.  Therefore, L^DIAG doesn’t exist in the list (L^DIAG, L₁, L₂, . . .)CS181作业代写

(b)Considerthe sequence (L^DIAG, L₁, L^DIAG, L₂, . . . , L^DIAG, L_i, L_i+1, L_i+2 . . .). Let L^DIAG1 2 i i+1 be the language obtained by applying cantor’s diagonalization to this sequence.

We can prove by induction that for all i, L^DIAG satisfies the conditions of the problem. As the base case, L^DIAG = L_i for any i via the original diagonization argument. For the induction step, take the sequence (L^DIAG, L₁, L^DIAG, L₂, . . . , L^DIAG, L_i, L_i+1, L_i+2 . . .)

and assume the following holds:

• ∀j,j ƒ= i, L^DIAG ƒ= L^DIAG.i j

• ∀j,L^DIAG ƒ= L_j.CS181作业代写

We diagonalize on the sequence of languages (L^DIAG, L₁, L^DIAG, L₂, . . . , L^DIAG, L_i, L_i+1, L_i+2 . . .)

as we did in part (a) to obtain the new language L^DIAG. The two properties above still hold, so we are done.

(c)Consider the sequence (L^DIAG, L₁, L^DIAG, L₂, . . .). Set L^SUPERDIAG be the language obtained by using cantor’s diagonalization on this sequence.

(d)Finally,consider thesequence (L^SUP ERDIAG, L^DIAG, L₁, L^DIAG, L₂, . . .) and obtain L^SUP ERDIAG via cantor’s diagonalization.

其他代写：代写CS C++代写 java代写 r代写 matlab代写 web代写 app代写 作业代写 物理代写 数学代写 考试助攻 金融经济统计代写

合作平台：essay代写 论文代写 写手招聘 英国留学生代写