Do exercises 1.1, 1.6, 1.8, 1.9, in the textbook, The Universal Machine.

Due: Tuesday, 9/5, anytime before midnight. (See hand-in instructions below.)

Hand in: Enter all your answers into a text file, using an text editor such as notepad or Lookout. When you're ready to submit your assignment, using a web browser, go to The Student Drop Box for Introduction to Computing. (It's under Student Tools. You may want to use Netscape rather than Iexplorer to access CourseInfo.) Click on the Browse button, then find your file in its folder (if you put it on a floppy disk, it's in A:). When you've selected your file, you should see a directory path to this file next to the Browse button. If it looks right to you, click on the Send File to Instructor button. Then you should see this file listed under Current Files in your DropBox. The Teaching Assistant, Jeff Eynon (jne3), will get this file and grade it.

If you have any questions about submitting assignments or grading, please send email to Jeff Eynon (jne3). (If you can't figure out how to use the Student Drop Box, you may just email the assignment to him.)

Hints:

Exercise 1.1:
I don't expect a very technical explanation of actual and virtual machines or virtual memory. Just review the discussion on pages 2-3 and answer the questions based on what you know now. We'll look at these issues in a bit more detail later in the course.

Exercise 1.6:
Review concepts covered in the preceding pages of the book and/or the multimedia.

Exercise 1.8:
Figure out how many bits you need to distinguish all 26 characters, then use assign a code with this many bits to each character, each one getting a unique binary code.

Exercise 1.9:
I'll trace a different example, to give you some idea what you are supposed to do. Suppose the machine had these three rules (I include rule numbers):

1) if remembering blank remember 0
2) if reading 0 and remembering 0 then write 1; move right
3) if reading 1 and remembering 0 then write 0; halt

The machine starts out with its head empty (remembering blank or ' ') and its tape is 001, looking at the leftmost square, on which is '0'.
Here's a picture of the initial state:
 001
 ^
| |
The ^ represents the head pointing at the first square, holding a 0. The | | represents the head representing a blank (nothing). Here a trace of the machine's activity, as it matches rules:

Rule 1 matches (because the machine is remembering blank), so the head remembers 0:
 001
 ^
|0|
Rule 1 no longer matches, because the head is no longer remembering blank.
Rule 2 now matches (because the head is reading the first 0 and remembering 0),
so write 1; move right. Tape is now 101, head at second position (another '0'), remembering 0:
 101
  ^
 |0|
Rule 2 matches again (because the head is now reading the second 0),
so write 1; move right. Tape is now 111, head at last square (a '1'), remembering 0:
 111
   ^
  |0|
Rule 3 matches, so write 0 and halt. Tape is now 110, head is at end of tape, machine halts:
 110
   ^
  |0|
The tape is now 110 and the machine halts. (This program inverts 1's and 0's up to the first 1.)

For exercise 1.9, the initial state looks like this:
[0110]
  ^
 | |
Trace the rules that match and the changes of state that occur, until the machine halts.

If you have any questions that aren't covered by these hints, send me email, and I may update these hints.

If you have any questions about submitting assignments or grading, please send email with attachments to Jeff Eynon (jne3). (If you can't figure out how to use the Student Drop Box, you may just email the assignment to him.)

Prof. Blank