Project 6

Constructing a Turing Machine Simulator

Project Overview

This project will get you acquainted with Turing Machines (TMs). You will write a Python program that simulates a TM.

What you need to do

Write a Python program (call it tm.py) by completing the following steps:

1. In whichever approach you wish, have your program read in a text file called tm.txt and construct a Turing machine. This file will contain data that encodes a Turing machine.
2. The structure of tm.txt will be as follows:
   • Line 1: the states of the Turing machine (separated by commas, and ‘accept’ and ‘reject’ will always be states)
   • Line 2: the input alphabet (separated by commas, if there is more than one symbol)
   • Line 3: the tape alphabet (separated by commas, if there is more than one symbol, and assume that ‘_’ represents a blank space on the tape)
   • Line 4: the starting state of the Turing machine
   • Line 5 and onward: the transition rules, where each rule takes the form a,b,c,d,e (where being in state ‘a’ and reading symbol ‘b’ on the tape will write a ‘c’ to that location, move to new state ‘d’, and move the read/write head in direction ‘e’)
3. After your program constructs a Turing machine, read in another file called input.txt, where each line in the file is a string that will be loaded onto the Turing machine tape.
4. Both tm.txt and input.txt should be assumed to be in the same directory as your Python program.
5. Simulate each string inside of input.txt within your Turing machine, and write the output (‘accept’ or ‘reject’) into a new file called output.txt (also in the same directory as your Python program, and each result on a new line).
6. Technically, Turing Machines can get stuck looping. You can assume that every Turing Machines I give you will always halt.

How to submit

To submit, save your Python program in a file named tm.py, and upload/submit it to Moodle by the due date.