CSC 364 Tests

CSC 364H Summer 2002

Test #1 Information

Homework solutions:
Several people have asked me about solutions for the assignment. I will not be posting the solutions. But you are welcome to come to office hours, or use the newsgroup and email if you have any questions about solving the problems.

What do I expect you to know for the test?

The test will cover everything up to the end of reducibilities. Greedy algorithms will not be on the test.
I expect that you have solved all the homework in some form (for question 6, solving the write-twice TM is sufficient).
Turing machines: formal definition, creating, proving correctness (induction).
Proving two models of computation equivalent.
Nondeterminism: I expect you to be aware of nondeterminism and what it is, but I will not ask you specific questions about it (yet). So no nondeterministic Turing machines are required, though you are welcome to use it if you want to.
Decidable and semi-decidable languages.
Three methods for proving undecidability: diagonalization, contradiction and reduction.

What is the format of the test?
It will be a series of 5 problems similar to those on the homework, except (hopefully) much easier. Unlike the homework, I will not expect you to come up with new and novel ideas. You will be able to apply the ideas required for the homework to solve the test questions.

How long is the test?
It will be between 60 and 90 minutes long. Time should be sufficient if you have kept up with the homework.

How do I apply diagonalization?
As an example, let us consider how we defined DIAG. Since sigma* is recursively enumerable, we can write each string in a big list (like how we can write each natural number in a list). Let us consider only the strings which describe Turing machines and list them. We will list whether that machine accepts each string in our table (Y means the the machine on the left accepts the string on the top):

TM	Accepts string ...?
TM	<M₁>	<M₂>	<M₃>	...	<M_DIAG>	...
M₁	Y	N	Y		Y
M₂	N	Y	Y		N
M₃	Y	N	N		Y
...
M_DIAG	N	N	Y		?
...

Recall that DIAG = { <M> | <M> is not accepted by M }. But if DIAG was recognizable, then M_DIAG would appear in the list somewhere. But we picked DIAG so that it was different than the language of every machine in the list on at least one string, namely <M>. So DIAG must be different than L(M_DIAG), which is a paradox. So the list of all machines does not include a machine for DIAG, hence no machine recognizes DIAG, and thus DIAG is not recognizable.

To do a proof by diagonalization, list all the machines and languages (or whatever is applicable), and pick a suitable diagonal set (for example, a language which is different than each language in the list). It should be easy to then prove that language is undecidable, since we constructed it to have that property.