COMP 598

Assignment 4

Question 1[20 points] Suppose that M is a Turing machine and w is a

word. Is the question “Does M ever use more than 598 cells on its tape

while processing w?” decidable or not. Prove your answer. Hint: Rice’s

theorem will not help you.

Question 2[10 points] Show that L(G1) ∩ L(G2) = ∅ is co-CE but not

computable (decidable). Here G1 and G2 are context-free grammars.

Question 3[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,

1

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.

Question 4[30 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, {a

n

b

n

|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. [25 points]

Question 5[20 points] Suppose that L is a context-free language and that R

is a regular language. One of the following questions is decidable and one is

undecidable. Which one is which? For the decidable one give an algorithm

to decide it and for the undecidable one give a proof.

1. R ⊆ L

2. L ⊆ R

Question 6[0 points] Write a program that prints its own text exactly. You

will find millions of solutions on-line, but try to do it without looking it

up.

2

Question 7[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 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