Description
NOTE: THIS ASSIGNMENT BUILDS OFF OF THE PREVIOUS ASSIGNMENT. COMPLETE THAT ONE BEFORE STARTING THIS ONE.
For this assignment, you will complete the Turing machine you began to develop in the previous assignment. In that assignment, you developed code to represent the memory of the Turing Machine (the infinite tape) and the read head (the thing that selects the current square). Now you will implement the state table, and provide functions that allow your Turing machine to actually run. When finished your program will be as precisely as functional as the online turing machine simulator, although its user interface will be somewhat more primitive. (Links to an external site.)
Here’s what you need to do:
- Extend your previous program to include a new constructor: Turing_machine(string tape_file, string state_file). This constructor specifies the names of two files, one specifying the initial state of the tape, the other specifying the turing machine states.
- You will need to use some sort of data structure (a vector, an array, whatever) to store the states of the machine. I leave it to you to determine what this data structure should be.
- The format of the tape file is as follows:
2:-3,1,3
- There is exactly one number before :. This number specifies the initial position of the tape head (the initial value of currentSquare)
- The numbers after the : represent the currently marked square. In the line above, you should consider the squares -3, 1, and 3 as containing 1s, and everything else as containing 0s
- I recommend using the getline() function (discussed in lecture on day 10) for this.
- The format of the state file is as follows:
1,R,2:1,L,2
1,L,1:0,L,3
1,L,0:1,L,4
1,R,4:0,R,1
The state file above specifies the Turing machine pictured below. Each line represents one state. The portions before the colon on each line represent the command to be executed if the current square is unmarked. The portions after the colon represent the command to be executed if the current square is marked. The three components of a command indicate:
* Whether the current square should be marked (0 for no mark, 1 for mark)
* The direction the tape head should move (L for left, R for right)
* The state that should be active the next time the machine updates
Here is what the program above looks like on our online simulator (Links to an external site.). When run on an empty tape with theinitial position equal to 0, this program leaves 11 marks on the tape, at positions [-10, -8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3]
- Include a function in your TuringMachine called update(). This function executes the next instruction. For example, if we were using the program above, if the current square were 0 and the current state were 1, the update function would make a mark, move the head to the right, and then set the current state to 2.
- (notice that to implement this, you will need to include an instance variable in your TuringMachine to keep track of the current state)
- Include a function in your TuringMachine called run(). This function repeatedly calls update until the current state is 0.
I recommend testing your machine with the program given above and an empty tape. If your machine produces the following output:
[-10, -8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3]
Then your program is likely correct.
The details of how to implement your machine are up to you. My requirements are that you have the following public functions, and that they all work appropriately:
A constructor that initializes your machine from two files:
TuringMachine::Turing_machine(string tape_file, string state_file)
A function that makes your machine advance one step:
void TuringMachine::update()
A function that makes your machine run until it is set to state 0:
void TuringMachine::run()
