Assignment 6
Prakash Panangaden
COMP 330 Winter 2021 McGill University
Due Date: 8th April 2021
There are 5 questions for credit and two for your spiritual growth. The first spiritual growth
question is not hard, all of you can give it a shot if you have time: however, it will not help
you do well in the course. The second spiritual growth question is deep and difficult. Please
don’t get obsessed with it. It will not help you prepare for the exam.
Question 1[20 points] For each of the following assertions give brief arguments indicating
whether they are true of false. In each case I am talking about sets of positive integers.
a. For each n ∈ N we have a computable set Cn. The set
⋃
n
Cn is computable. We assume
that the collection of computable sets is effectively given: this means that there is an
algorithm that reads a natural number n as input and outputs a description of a Turing
machine that decides the set Cn.
b. For each n ∈ N we have a computably enumerable set Cn effectively given as described
above. The set
⋃
n
Cn is computably enumerable.
Remark: You will find loads of rubbish written about this on the internet. If you copy from
the internet without thinking you will, with high probability, write some nonsense for which
you will get zero.
Question 2[25 points] For this question the alphabet is {a, b}. Suppose that the language
L is CE but not computable; this means that L cannot be CE. We define a new language as
follows:
K = {aw|w ∈ L}
⋃
{bv|v ∈ L}.
1. Show that K is not computable. [5 points]
2. Show that K is not CE. [10 points]
3. Show that K is not co-CE. [10 points]
Question 3[15 points] Suppose that M is a Turing machine and w is a word. Is the question
1
“Does M ever use more than 330 cells on its tape while processing w?” decidable or not.
Prove your answer. Hint: Rice’s theorem will not help you.
Question 4[20 points]
1. Here is a question on regular languages just to get you in shape for the final exam.
Suppose that L is a regular language and w is any word, not necessarily in L. We
define the set
L/w = {x ∈ Σ∗|xw ∈ L}.
Show that L/w is regular. [5 points]
2. Suppose that G is a context-free grammar. Show that the question “Is L(G) regular?”
is undecidable. Here is a possible approach. Let N be some language that is known to
be context-free but not regular (for example, {anbn|n ≥ 0}). Now consider the language
L = (N#Σ∗) ∪ (Σ∗#L(G)), where # is some symbol that is not in L(G) or N . Prove
that L is always context-free but is regular if and only if L(G) = Σ∗. This, by itself,
does not complete the question, so you have to complete all the remaining steps as well
as proving the claim. Also, you should think about why I put part (1) together with
this question? You are free to ignore this hint, but if you do so, I will mark you just
as rigourously as the people who used the hint. [15 points]
Question 5[20 points] You are playing a video game under the following idealized conditions.
The computer memory is unbounded and you have no time limit for finishing the game. The
game board is the set of points in the plane with integer coordinates and time moves in
discrete integer steps. There is a hidden submarine: you do not not know its location, you
do not know its speed and you do not know its direction of motion. The speed and direction
of motion do not change throughout the game. The speed is a natural number and the
direction of motion is either “up”, “down”, “left” or “right”. For example, the submarine
could start at (2, 3) have speed 7 and move right. Then at step 0 it is at (2, 3), at step 1 it is
at (9, 3), at step 2 it is at (16, 3) and so on. At every step you get to zap a point: you enter
the coordinates and if the submarine is at that point, at that time step, you will destroy it.
Of course, there is no point zapping a position before it gets there or after it leaves. Give
a strategy or scheme that is guaranteed to get the submarine at some finite stage. I repeat,
you do not know where it started, you do not not know its direction and you do not know
its speed; you only know that the speed and direction do not change. You get zero points for
this question if your strategy works probabilistically; this question has nothing to do with
probability. Hint: Ask yourself, “why is this on the homework for this class? It is a direct
application of something I have discussed in class.”
Spiritual growth[0 points] Write a program that prints its own source code exactly. You
will find millions of solutions on-line, but try to do it without looking it up. It can be done
in any reasonable programming language.
Spiritual growth[0 points] The Halting Problem and all the problems equivalent to it
are CE complete. This means that for any CE problem P there is a mapping reduction
2
P ≤m HP . All the CE problems that are not decidable that we have seen in class are
CE complete. Are there any problems that are undecidable and CE but not CE complete?
In other words, is there a problem that is undecidable but less difficult than the halting
problem?
3