Turing Machine

Learning Objective(s)

1. Demonstrate proper use and understanding of Java classes
2. Be able to work on part of program that someone else has done the other part of
3. Better understand the design/code steps

Overview of the Challenge

One very good way to get a basic understanding of a Turing machine is to refer to its Wikipedia article. There are two different types of programming that can be associated with a Turing machine:

1. Programs that a Turing machine can execute. Writing these programs (esp. ones that do anything significant) can be VERY challenging).
2. A program that simulates a Turing machine. Because a Turing machine is a very simple machine (in terms of its actions), this is a much easier program to write.

You are to complete the development of a Turing machine. Some code will be provided for you. You must implement the rest.

Specifics:

• Classes Provided. You are provided with three classes:
  • TMDriver.java : For this one you are given the source code. It creates a Turing machine (given data in a file), causes it to run and then reports the results.
  • Instruction.class : For this one you are just given the compiled byte code. The methods are as follows:
    • Constructor : Arguments (in order):
      • int: current state
      • char: current character
      • char: new character
      • int: direction to move tape (-1, 0, 1)
      • int: new state
    • Constructor : Argument: String in form of a,b,c,d,e where
      • a is an integer representing the current state
      • b is a character representing the current value read by the tape head
      • c is the new character to be written to the tape
      • d is the direction to move the tape
      • e is the new state
    • equals : This methods returns a boolean indicating if it matches the passed state and character. Arguments(in order):
      • int: current state
      • char: current character
    • getNewState: returns an int representing the new state
    • getNewChar: returns a char representing the new character to be written to the tape
    • getDirection: returns the direction (-1, 0, 1) indicating which direction to over the tape read/write head
    • toString: returns a string representing the instruction
  • Tape.class : For this one you are just given the compiled byte code. The methods are as follows:
    • Constructor : Argument:
      • String : a string that is the initial value for the tape
    • readTape : returns a char that is current under the read/write head
    • writeTape : Argument:
      • char: character to be written at the location of the current read/write head location
    • moveHead : Moves the head left one space (-1), stays put (0), or right one space (1). Will automatically adjust if more space is needed on either side. Argument:
      • int: direction to move the head
    • toString: returns a string representing the tape (the tape and the position of the read/write head)
• Tasks, etc.
  • Implement the Instructions class. This is a homogenous collection of Instruction
  • Implement the TuringMachine class.
  • The data file is a follows:
    • first line: The initial value for the tape (with the read/write head at 0)
    • one line per instruction (eof signaling the end of data): Sample line: 1,b,c,0,1 (first is current state, then current character, then next character, then direction, then new state → no spaces, only , separating them)
• Necessary components.
  • Handle file I/O exceptions
  • You are NOT to implement your own driver, Instruction, or Tape. One of the goals of this class is to learn to use other's code.

Design components

Refer to the software design/development report for additional details not specific to a Turing machine. For the design component of this lab, pay special attention to:

• A quality set of UML diagrams for your two classes. Include pseudo code for any non trivial routine
• A quality set of testing data. You want to make sure that your tape can go all directions and can easily grow on each side. There are other items that should be tested. Make sure you include test cases for things that can go wrong. Your program may end up not handling them but you should not what could cause a problem. Start with simple cases. For example: a program that reads a 0 and keeps the head in the same position, writes a 0 and goes to the accepting state. Then make it so it changes a character.. Make simple programs that each test a small feature.
• Try to have a somewhat accurate estimate of how long you think it will take to code your design.

Optional improvements

Any/all of these can be added to your program for extra credit. But do not attempt them until your program (including the write up) is complete and receiving at least a 90%. Extra credit will only be given to those programs that receive at least a 90% on all the required work. It is much more important to do the required work well than to do the extra credit. Typically, extra credit work is also done on your own with limited (typically no) help from the instructor. The options are listed in order of importance. While you may implement any/all in any order, the order listed will focus you on the more important items first

1. Handle incorrect data for bad instructions nicely
2. Allow the user the option of a second file for multiple strings to run the same program on. It still must work with the specified input above, just allow for another option.
3. Have the file be specified at the command line
4. Use graphics