**CSC 8510-001: Homework Assignments**

**Policy:** Homework will
not be graded, but the weekly quizzes and examination will be mainly based on
your homework. Books or notes will not be allowed during the quiz or exam. Using
somebody's help is OK when doing homework, but not when writing the quiz or
exam.

**[January
16]**

**Material covered:** Slides 0.a-1.2.c

**Assignment:**

- Exercise
0.1 [Note: "
**N**" stands for natural numbers. See page 4.] - Exercise 0.2
- Exercise 0.3
- Exercise 0.4
- Exercise 0.5
- Exercise 0.6
- Exercise 1.1
- Exercise 1.2
- Exercise 1.3
- Exercise 1.6 (a,b,d,e,g,h,i,k,m,n)
- Exercise 1.7 (a,b,d,g)

**[January
23]**

**Material covered:** Slides 1.2.d-1.4.c

**Assignment:**

- Exercise 1.16 (a)
- Exercise 1.18 (a,b,c,d,e,g,k,l,m,n)
- Exercise
1.20 [Note: here Σ stands for
*a*]*∪ b*

**[January
30]**

**Material covered:** Slides 2.1.a-3.1.g

**Assignment:**

- Exercise 2.3
- Exercise
2.4 (in this exercise,
means*w*^{R}read from right to left)*w* - Exercise 2.9 (ignore the question on ambiguity)
- Exercise
3.1
- Exercise
3.5
- Complete
the following definitions: (1) A Turing machine
is a*M*iff ... (2) A Turing machine*decider**M*a language*recognizes*∈Σ*L******iff ... (3) A Turing machine*M*a language*decides*∈Σ*L******iff ... - Construct
a Turing machine (provide a full diagram) for the language
**{#****0**^{n}**>****0**^{m }**|**(note: this is similar to but NOT the same as the example on slide 3.1.f).*n*>*m*}

**[February 6]**

**Material covered:** Slides 3.1.h-3.2.g

- Design a fragment of a TM which, from a state “Beg?”, goes to a state “Yes” or “No”, depending on whether the scanning head is at the beginning of the tape or not, without corrupting the contents of the tape (Slide 3.1.i).
- Design a fragment of a TM which, from a state “Go to the beginning”, takes the scanning head to beginning of the tape and goes to state “Done” (Slide 3.1.j).
- Design a fragment of a TM which, beginning from the current cell, shifts the contents of the tape to the right, typing in the current cell a 0 (Slide 3.1.k). Assume the tape alphabet is {0,1,-}, and that neither 0 nor 1 ever occurs after the leftmost blank on the tape.
- Theorem 3.13 with a brief description of its proof idea (a few lines would suffice, showing your understanding of the essence of the proof; do not go into technical details).
- Theorem 3.16 with a brief description of its proof idea (a few lines would suffice, showing your understanding of the essence of the proof; do not go into technical details).
- The definitions of "
*M**computes*", "*g*is*g*" and "the*computable*of*graph*" (Slide 3.2.g).*g* - For a bit string
,*w***NOT(**means*w*)with all bits changed. For example,*w***NOT(****11010)=00101**. Construct a Turing machine with an output that computes function**NOT**.

**[February 13]**

**Material covered:** Slides 3.2.h-4.2.a

- Prove that a function is computable iff its graph is decidable (Slide 3.2.h).
- What is the Church-Turing thesis all about? (do not
just write something like "algorithms = TM"; write a couple of
sentences showing that you understand what you are writing).
- Exercise 3.7.
- Exercise 4.1(a,b,c,e)
- Exercise 4.3.
- What language does the universal Turing machine
recognize and how does it work? (i.e., state the algorithm that it follows) Answers to both questions are found on Slide 4.2.a
- Theorems 4.1, 4.2, 4.4 with proofs.

**[February 20]**

**Material covered:** Slides 4.2.a-5.3.d

**Assignment:**

- Prove that A
_{TM}, i.e. the acceptance problem for Turing machines, is undecidable (Theorem 4.11)

- Prove that the complement of A
_{TM}, i.e. the non-acceptance problem for Turing machines, is unrecognizable (Theorem 4.23). - Prove that if a
language
and its complement*L*are both recognizable, then__L__is decidable (Hint: the idea is, in fact, already given in the proof of Theorem 4.23. More explicitly, this is Theorem 4.22 of the textbook).*L* - Prove that the halting problem is recognizable (Hint: similar to the theorem on Slide 4.2.a).
- Prove that the halting problem is undecidable (Theorem 5.1).
- The definitions of
"
" and "*mapping reduction*" (Slide 5.3.a).*mapping reducible* - In each case below, find
(precisely define) a particular function that is a mapping reduction
of
to*A*. Both*B*and*A*are languages over the alphabet*B***{0,1}**.

is the language described by*A***1**,^{*}0^{*}*B***01**^{*}0^{*}*A***={***w***|**the length ofis even*w***}**,*B***={**the length of*w*|is odd*w***}***A***=**the length of*B*={*w*|is even*w***}***A***={****0,1}**,^{*}*B***={00,1,101}**

- Prove that if a
language
is mapping reducible to a language*A*and*B*is recognizable, then*B*is recognizable (hint: very similar to the proof of Theorem 5.22).*A* - Describe a particular function which is a mapping reduction of the acceptance problem to the halting problem (this is function f of Slide 5.3.d).