Turing machines are important models of computation. They are simple in structure
yet highly powerful. Turing machines comprise a fundamental class of automata and
are used in the study of formal languages, theory of computation and various other
topics in computer science.
Computer science educationists, however, observed that programming Turing machines
is not easy to teach or learn. So, they started developing languages in which Turing
machines can be modeled and simulated. Several researchers have worked till date
on the simulation of Turing machines for pedagogical purposes and quite a few of
them are worth mentioning. In an early study, Coffin et al. (1963) developed a simple
notational language for modeling Turing machines. Later, similar languages were
also developed by Harris (1998 and 2002), and Scott (2006). In these notational
languages, Turing machines are defined using formal symbols. The programs follow
a rigid structure and there are strict limitations on the choice of the symbols.
The notational languages are easy to learn and can be used efficiently to model
simple Turing machines. Using another approach, Curtis (1965) developed an assembly-like
language to model and simulate Turing machines. The language provides a basic set
of instructions to read and write the tape contents, move left and right on the
tape, jump conditionally and unconditionally, and invoke subroutines. This assembly-like
language is more powerful than the notational languages. However, these notational
and assembly-like languages need to be learnt explicitly. To circumvent this extra
effort, Chakraborty (2007) developed a Turing Machine Description Language (TMDL)
in which Turing machines are represented in a descriptive way, similar to that used
in textbooks. TMDL is capable of modeling any Turing machine and needs absolutely
no effort to learn. This paper reports the design, implementation and performance
of an optimizing compiler for TMDL.
|
