CSC363 - Notes on assignment #1

Notes on assignment #1

There have been a few recurring themes in the questions that students have asked me, which I'll try to clear up here.

For questions 3 and 4, you only need to give a high-level description of any Turing machines you use. A high-level description does not mention any of the inner details of the TM; it is just a description of an algorithm using pseudo-code constructions like "for" loops and "if" statements, combined with english-language statements (these statements should, however, be precise). See pages 144-145 of the textbook for more discussion and examples. In particular, statements like "run M on input x for j steps" are valid high-level statements.
The language defined in question 3 consists of all the pairs < M, t > where M is a Turing machine, t is an integer, and the number of strings accepted by M is at least t. You are supposed to define a Turing machine that recognizes this language; I would suggest using a symbol other than M to denote this TM, or you may confuse it with its input.
For question 4, it seems that the number of quantifiers is causing some confusion. Here is an example of a specific language L and a corresponding language D such that L is the set of all strings w for which there exist a t such that < w, t > is in D (note that because this is a specific language it will not help you to solve question 4, but it should illustrate what is being asked).
Let L be the set of all strings < P > , where P is a polynomial that has an integer root, i.e. P(n)=0 for some integer n. L is recognizable by a TM that, on input < P >, evaluates P(n) for n=0,1,-1,2,-2,3,-3,... and accepts if it finds an n for which P(n)=0.
Let D be the set of all strings < P, n > , where P is a polynomial, n is an integer, and P(n)=0. Then D is decidable by a TM that, on input < P, n > , evaluates P(n) and checks if P(n)=0.
L and D have the desired relationship: < P > is in L iff there exists an n such that < P, n > is in D.
The hint says to interpret t as a sequence of IDs. Note that t is a binary string, and you can interpret it in any way you desire. In the above example, we interpreted n (a binary string) as an integer. There are other interpretations of t that will also work, so it is not strictly necessary to use the hint.