Assignment 3 - due Monday, October 18th, 5PM, by email

Please do work on your own - no group work. If you are stuck, contact me. Collaborating on this assignment will be viewed as cheating.

Important Note

I want you to email me your assignment this week. You can either zip together a set of files, or send them separately. My address: fickas@cs.uoregon.edu.

Problem 1

Read chapter 31 (thirty-one) in Dewdney. There is material in this chapter that you can skip over for now. What I want you to understand is how a Turing Machine operates. You can skip the pieces about multi-tape machines. And you can skip the last paragraph on page 211 until the end of the chapter. The material you are skipping is interesting from a theoretical point of view. Right now I just want you to understand how a TM operates.

The problems at the end of the chapter are quite difficult, and I am going to ignore them for now. Instead, I'll give you some problems to gain some experience in programming a TM. To do that, we will use a pretty cool tool that simulates a TM. To download the tool, right-click on the following and then save-as xTuringMachine.jar: xTuringMachine.jar. Be careful that windows does not make it a zip file. Make sure it is saved exactly as stated.

Now to run the tool, double-click on the xTuringMachine.jar file. You should see a window pop up with the tool in it.

Note that the format of a quintuple is different in Dewdney and the tool.

Dewdney: q0,x,q1,y,L = if in state q0 and read an x, then write a y, move L and go to state q1 Tool: 0,x,y,L,1 = if in state 0 and read an x, then write a y, move L and go to state 1 Dewdney: crossed b = blank Tool: # = blank Dewdney: direction S = stop, circled state = halting state Tool: state h = halting state (actually stored as -1 state on file) Tool: other = powerful mechanism to avoid expanding states; matches input if no other quintuple matches. same = goes along with other; writes out whatever input was.

With the tool, you can enter a new program directly by using the Make Rule button. You can also replace an existing rule or delete a rule. You can then test your program and when you are happy with it, you can store it as a txt file. The format of the file that is written is as follows:

1st line: name of the program (header for the file) 2nd line: characters the program understands, and max number of states the program can support. (also part of header for the file) 3rd line: 3 numbers regarding the tape (start position of symbols on tape, visual position of tape, position of touring machine on tape) 4th line: These are the symbols on the tape to start with. 5th line: The number of rules. All other lines are the rules.

Here is an example from Mystery.txt:

xTuringMachine File Format 1.0 #$01xyz* 25 -3 5 -3; yxyzzyxxy 28; 0 # # R -1; ...

Part a. I want you to run a program someone else wrote. You can find the program here: Mystery.txt. Download it to your computer. Then start the TM tool and load the file. Watch it run. Tell me, in words, what it does. Then tell me, at a conceptual level, how it does it.

For the next two problems, you are asked to write TM programs. Here is the way I would tackle each:

  1. Work out a general strategy on paper.
  2. Test your strategy on a couple of examples, on paper.
  3. Now write the program, as a file. You have a choice here of actually trying to follow the xTuringMachine file format above, or just using the file you write as a scratch pad for your program. I would recommend against the former: do not try to write in xTuringMachine format. Too easy to make syntactic errors that are hard to debug.
  4. Now start the tool and begin entering your program, rule by rule.
  5. When you have your program entered, you can test it. You can actually test it at any time. For instance, if you have written some rules that move the head to the first blank on right, you can test those rules as soon as you enter them. Make sure they do the movement. Then move on to other rules. It's called divide-and-conquer in programming: do a little bit, then test, then do a bit more, etc. The opposite is big-bang testing: you code everything and then test. This is a generally bad approach.
  6. To test it, you will need to type in a test string on the tape, position the head, and set the initial state to start. Then click Run or Step.
  7. When you are happy with what you have, and have tested it on various strings to make sure it works, then you are almost ready to save it (using the Save button).
  8. When you click Save, it will save your rules *and* the string currently showing *and* the head position and state currently showing. You may want to clear the tape and type in a fresh string. And also reset the head to starting position and state. Then type Save.
  9. Note that you eventually have to Save as part of the turn-in for this assignment.
Ok, on to programming.

Part b. As a warm-up, write a TM program that writes a 1 on the right side of the tape if the input tape contains all x's and a 0 otherwise. For instance,

xxxxxxxx ^ will produce xxxxxxxx 1 ^ xxxxyxxx ^ will produce xxxxyxxx 0 ^ You can also place the 0,1 at the end of the string (without a space like I have above). Hint: you should be able to program this by always moving right.

Part c. Write a TM program that copies a sequence of $'s. For instance,

$$$ ^ will produce $$$$$$ $$$$$ ^ will produce $$$$$$$$$$ I will accept variations on the above , e.g., you can leave a space between the original and the copy, as long as you double the $'s on the tape.

Hint: this is a challenging problem. You will definitely have to move both left and right to solve it. Your biggest challenge will be keeping track of how much of the original string you have copied (and how much remains to be copied). Remember, that you can introduce new characters that are not part of the input string, e.g., marker characters, by simply writing them on to the tape.

Turn-in: for part a, your written description; for parts b and c, your program in xTuringMachine format (as two separate files). I want to be able to load and run your programs on my machine. I will do the final test to make sure they work.

Problem 2

I think problem 1 will be fairly challenging, so I am not going to introduce much new Java. But I would like to review some things. In particular, the data conversion is a non-trivial concept so I think it is worth some practice.

Part a. Study the code below.

int i = 10; int j = 21; double x = 3.2; double y = 8.75; /** There are two questions to ask about each line below: 1. What is the final value on the right-hand side of the assignment? 2. Is the assignment a widening or narrowing conversion (or neither)? If it is a narrowing conversion, it will not compile without casting. **/ int result1 = i/j; //line 1 double result2 = i/j; //line 2 int result3 = j/i; //line 3 double result4 = j/i; //line 4 int result5 = i/x; //line 5 double result6 = i/x; //line 6 int result7 = y/x; //line 7 double result8 = y/x; //line 8 int result9 = i/j*x; //line 9 double result10 = i/j*x; //line 10 int result11 = x*i/j; //line 11 double result12 = x*i/j; //line 12 Now answer the questions:
  1. What is the value of the right hand side of line 1?
  2. What is the value of result1?
  3. What is the value of the right hand side of line 2?
  4. What is the value of result2?
  5. What is the value of the right hand side of line 3?
  6. What is the value of result3?
  7. What is the value of the right hand side of line 4?
  8. What is the value of result4?
  9. What is the value of the right hand side of line 5?
  10. What is the value of result5?
  11. What is the value of the right hand side of line 6?
  12. What is the value of result6?
  13. What is the value of the right hand side of line 7?
  14. What is the value of result7?
  15. What is the value of the right hand side of line 8?
  16. What is the value of result8?
  17. What is the value of the right hand side of line 9?
  18. What is the value of result9?
  19. What is the value of the right hand side of line 10?
  20. What is the value of result10?
  21. What is the value of the right hand side of line 11?
  22. What is the value of result11?
  23. What is the value of the right hand side of line 12?
  24. What is the value of result12?
Turn-in: answers to the 24 questions above (as part of your electronic submission).