Class Work 17: Turing Machines

Computer Science 416/685: Computability Theory
Lehman College, City University of New York
Fall 2016

Grading Notes:

• Submit one answer per group.
• Make sure that the answer is legible.
• Include the full names of all group members on your submitted work (so all get credit).

Write a program for Antony Morphett's Turing Machine Simulator:

http://morphett.info/turing/turing.html

that accepts all strings that have the same number of 0's and 1's.

Hint: There are many, many ways to do this. Write out some sample strings, and brainstorm about how you would do it by hand, then translate into pseudocode, then into a Turing Machine.