CSE 322 Homework Assignment 2.

Note, there is a change to the assignment as of 10/9/97, problems 1.6, 1.8, 1.42 are no longer due on the 10th, they are now due on the 17th of October.

One further change to the assignment as of 10/9/97: Problem 1.13, part f is now due on the 10th. Be sure to give a good argument for why your solution is correct. (Argue from the basic definitions. I.e., no fair quoting theorems we have not discussed in class.)

The following Homework Exercises and Problems should be worked, not at the last minute, but rather as the material is discussed in class.

All exercises and problems are important and are worth doing as the material is discussed in class. Those marked in bold should be written up carefully and submitted for grading. These will be due in class, Friday, October 10. (Watch e-mail announcements for last minute changes.)

Students are encouraged to work together to the extent of discussing exercises and homeworks with each other, but when writing up assignments to be handed in, you are to work alone, without notes or private material that has been discussed or seen by others.

First special assignment. On the first day of class, we presented an argument, which we hoped was convincing, that it was impossible to write a program, or a subroutine, SHORTEST(y) which, when given an integer input m, would produce a shortest program, SHORTEST(m) whose sole output is to write m.

1. Carefully give an equally convincing argument, that, if you had a fixed subrountine Halt(z), which given a program P as input, would decide whether or not P halts, then you could in fact produce the program SHORTEST(y). (You may need to figure out what it would mean to have a subroutine which decides whether or not a program halts.)

 

2. Discuss as carefully as you can whether there can be a program, or subroutine, FASTEST(y), which, when given an integer input m, will produce a fastest program, FASTEST(m) whose sole output is to write m. (The fastest program, for example, might be the one that executes the smallest number of instructions. What might code for such a program look like?)

Assignments from Sipser's textbook:

1.1; 1.2; 1.3

1.4: a, b, c, f, g, h, i, j, k, l

1.5: a, b, c

1.6:b

1.10

1.13 f

1.27 (For this problem, assume that a regular language is one that is accepted by a nondeterministic finite automata.)

1.42 (For this problem, assume that a regular language is one that is accepted by a nondeterministic finite automata.)