CSC 4170: Homework Assignments


Policy: Homework will not be graded. Using somebody's help when doing homework is not forbidden. However, the quiz problems will usually (90%) come from the homework assignments. Books or notes will not be allowed during the quiz. 


August 27

Material covered: Slides 0.a - 0.h


·        Exercise 0.1 [Note: "N" stands for natural numbers. See page 4]

·        Exercise 0.2

·        Exercise 0.3

·        Exercise 0.4

·        Exercise 0.5

August 29

Material covered: Slides 1.1.a - 1.1.j


·        Exercise 1.1

·        Exercise 1.2

·        Exercise 1.3

·        Exercise 1.4

·        Exercise 1.5(a,b,c,g,h)

·        Exercise 1.6(a,b,d,e,g,i,k,m,n)

September 3

Material covered: Slides 1.2.a - 1.2.h


September 5

Material covered: Slides 1.2.h - 1.2.m


September 10

Material covered: Slides 1.3.a – 1.3.d


September 12

Material covered: Slides 1.3.e – 1.3.p


September 17

Material covered: Slides 1.3.q – 1.3.x


September 19

Material covered: Slides 1.4.a – 1.4.e


September 24

Material covered: Slides 2.1.a – 2.1.g


September 26

Material covered: Slides 2.1.h – 2.1.k


October 1

NOTICE: a) The Oct.3 class cancelled; b) There will be 5 quizzes at once on Oct.8. Today’s material will not be included.

Material covered: Slides 2.2.1 – 2.3.d


October 10

Material covered: Nothing new, just a review.

Assignment: Enjoy your Fall break.

October 22

Material covered: Slides 3.1.a – 3.1.d


October 24

Material covered: Slides 3.1.e1 – 3.1.l


·        Design a fragment of a TM that, from a state “Go to the beginning”, goes to the beginning of the tape and state “Done” (Slide 3.1.j).

·        Design a fragment of a TM that, beginning from the current cell, shifts the contents of the tape 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.

October 29

Material covered: Slides 3.2.a – 3.2.e


·        Design a fragment of a 2-tape TM that swaps the contents of the tapes, from the position where the heads are at the beginning and there are no blanks followed by non-blank symbols (Slide 3.2.c). Tape alphabet: {0,1,-}.

·        State Theorem 3.13 and provide a very brief (half-page or so) yet meaningful and to-the-point explanation of its proof idea. Do not go into (m)any technical details.

·        The same for Theorem 3.16.


October 31

Material covered: Slides 3.2.f – 3.2.h


November 5

Material covered: Slides 3.2.i – 3.3.b


·        The definitions of computing, computability and graph of a function (Slide 3.2.j).

·        Proof idea for the theorem on Slide 3.2.k.

·        For a bit string w, NOT(w) means w with all bits changed. For example, NOT(11010)=00101. Construct a Turing machine with an output that computes function NOT.

·        Exercise 3.6.


November 7

Material covered: Slides 3.3.b –  3.3.f


·        What is encoding? Give examples.

·        What is the Church-Turing thesis all about? (don't just write something like "algorithms = TM"; write a couple of sentences showing that you understand what you are writing).

·        Exercise 3.7.


November 12

Material covered: Slides 4.1.a –  4.1.f


·        Exercises 4.1, 4.2, 4.3.


November 14

Material covered: Slides 4.2.a –  4.2.b.2


November 19

Material covered: Slides 4.2.c – 5.1.a


November 21

Material covered: Slides 5.3.a – 5.3.d


November 26

Material covered: Slides 6.2.a – 6.2.c



December 3

Material covered: Slides 6.2.d – 6.3.b


December 5

Material covered: Slides 7.1.a – 7.2.e (Slides 7.1.c-7.1.g, 7.2.b omitted; the proofs of Theorems 7.8 and 7.11 also omitted)