CS3331 – Assignment 3
due Nov. 30, 2021
2-day no-penalty extension until: Dec. 2, 11:55pm
(SRA’s cannot be used to extend further)
1. (20pt) Construct a deterministic Turing machine M that, given as input a binary string w, computes
the remainder of w modulo 4. M starts with the initial configuration (s,w) and halts with the
configuration (h,(w mod 4)2). It is assumed that the input, w, is a valid nonnegative number in
base 2, that is, w ∈ {0} ∪ 1{0, 1}∗.
Here are some examples of M ’s behaviour:
(s,0) `∗M (h,0); (s,1011) `∗M (h,11); (s,101) `∗M (h,1).
Describe M using the macro language (such as the ones in Examples 17.8-9, p. 275 of textbook).
2. (40pt) Prove that the following languages are in D (if you need to define TM’s, then clear English
description is sufficient):
(a) L = {|M has 3 states},
(b) L = {|M is a TM and L(M) ∈ SD},
(c) L = {| M halts on the input w in at most 3|w| steps},
(d) L = {| M uses only at most |w| tape cells before and after the input w (maximum
3|w| tape cells in total)}.
3. (20pt) Can you build a Turing machine that enumerates all encodings of Turing machines whose
language is not empty? Explain your answer.
4. (10pt) Given a language L that is not decidable (that is, L 6∈ D) and a context-free language C,
what can you say about the decidability of L ∪ C? Explain your answer.
5. (10pt) Consider the closure, SDc, of SD under complement, union, and intersection. Because SD
is not closed under complement, we have that SD ( SDc. We have obtained therefore a class of
languages, SDc, that is strictly larger than SD. Does this contradict Church’s thesis? Explain your
answer.
READ ME! Submit your solution as a single pdf file on owl.uwo.ca. Solutions should be typed but high-quality
hand-written solutions are acceptable. Make sure you submit everything as a single pdf file.
LATEX: For those interested, the best program for scientific writing is LATEX. It is far superior to
all the other programs, it is free, and you can start using it in minutes; here is an introduction:
https://tobi.oetiker.ch/lshort/lshort.pdf
1

欢迎咨询51作业君