From BU Computer Science
Jump to navigation Jump to search

Turing Machine Project


  • Learn about the Turing machine. One resource can be found at:
  • You are to write at least two components of a Turning machine (in two phases). You don't need to write programs for the Turing machine to execute (except to test your own implementation). You don't need to be able to make the machine do something that is productive.


  • For this phase, go to canvas and download the classes from the shared drive. It will include interface .java files for the two classes you are to implement. Use the .class files for this phase. You will be shown in class how to have multiple classes in a project.
  • You are to write the Instructions and Instruction classes.
  • To have a Turing machine, the program needs to (most of which is already implemented)
    • gets the name of the turing machine program
    • build the machine
    • while the machine is in a running state (no error and not a terminating state)
      • get the current status of the machine (state, and what is under the read/write head of the tape)
      • find the appropriate instruction
      • update the machine based on that instruction
        • change the state
        • change what is under the read/write head
        • move the read/write head
      • Upon termination, report
        • termination status
        • current tape (along with the location of the read/write head)
  • A state of -1 is successful termination
  • A state of -2 is a failed termination
  • An instruction is of form: <current state>:<current character>:<direction>:<new state>:<new character>
  • While by definition, a tape is infinite on both ends, you may assume it will never grow more than 30000 on either direction (and never larger than 30000) to begin. The tape is made up of unicode characters
  • Direction for moving the tape:
    • -1 (one position to the left)
    • 0 (no movement)
    • 1 (one position to the right)
  • At least one sample input file has been provided

Extra Credit:

implement one or more of the other classes.

Submission details

Create a software development report that includes the following:

  • A problem summary (the big picture)
  • A list of requirements. (Things that this particular implementation of a solution must do)
  • A list of steps your program does
  • A testing report: What exact input you used and what output you got.
  • How long it took to write the program
  • Who you got help from (if you got help)
  • At least two things you learned while writing the program
  • Changes (if any) you would make if you had more time and/or skill
  • Create a zip folder with your software development report and your java files and submit that to canvas.

Due date can be found on canvas