Visualizing Composed Turing Machines

In their first Formal Languages and Automata Theory course students find Turing machine composition challenging. In addition to the development of formal arguments, most students struggle with the idea that a Turing machine may use auxiliary Turing machines to solve a problem. This struggle is significant despite understanding that the use of auxiliary Turing machines is tantamount to using auxiliary functions in a program. This article presents two visualization tools developed to help students understand Turing machine composition. These tools are integrated into FSM--a domain-specific functional language for the Automata Theory classroom. The first is a static visualization tool that generates the transition diagram of a given composed Turing machine. The second is an interactive tool that simulates the execution of a given composed Turing machine. Empirical data collected from students is presented that suggests that the tools are well-received, easy to use, and useful.