Visualizing Turing Machines and Multitape Turing Machines

Abstract

An important computational model studied in Formal Languages and Automata Theory is the Turing machine and its extensions, including the multitape Turing machine. Designing such machines is challenging because they operate at a low level of abstraction, making it difficult to understand why words in an unrestricted language are accepted or rejected or why a function computes the correct value. Furthermore, many students may struggle to understand how to design such machines using nondeterminism or mutation. To address these problems, this article presents two new dynamic visualization tools for machine execution: one for Turing machines and one for multitape Turing machines, both of which are integrated into the domain-specific language FSM. These tools visually trace all computations that may be performed in a stepwise manner and support students in validating and verifying their designs. In addition to tracing an arbitrary machine designed by the programmer, the tools display when state invariant predicates hold or fail to hold. The results of a formative empirical study exploring student perceptions suggest that the tools are well received and help students understand, debug, validate, and verify their designs. In addition, the results suggest that students believe the tools help them understand nondeterminism.