When designing Turing machines using Turing's World, you can cut, copy and paste all or part of a machine for reuse in another, or even to incorporate into a word processing document describing your machine. When debugging a machine, you can run it on sample tapes at three different speeds (Graphic, Fast, Lightning), or even step through the computation--forward and backward--a single action at a time.
To make it easier to conceptualize a machine's underlying algorithm, Turing's World allows you to turn any state into a "submachine," a machine that executes when the main machine enters that state. For example in the following machine, states 1 and 4 are actually submachines that perform significant parts of the computation. In the state diagram, submachines are represented by square, rather than round, nodes.
When this machine is run at one of the slower speeds, the nodes representing submachines open up as soon as the computation "enters" them. Here is an illustration with submachine 4 open.
Since submachines can be nested within submachines, you can build highly complex machines that are still comprehensible. Users who work through the many exercises in the book will construct machines up through and including what is know as the Universal Turing Machine--in effect a "programmable" Turing machine.
A Turing machine is sometimes represented by what is known as a "tuple" description, instead of by its state diagram. Turing's World automatically generates the tuple description, which can be displayed at the right of the window. Below is a machine that computes the so-called "Ackermann" function, with its tuple description displayed.
[More]
Show me more.
Return to Logic Software from CSLI.