A C# Turing Machine

• Executable - 22 KB
• Download Source Code - 39 KB

Introduction 

Turing Machines are theoretical models of computation. They don’t have a practical application in the sense of what a usual computer everybody knows does. They are artifacts to study problems in the area of theoretical computation. The mathematician Alan Turing created them as a model to describe what computation is, so the mathematicians of the time could attack abstract problems which required a formal description of what is an algorithm, a notion not really clarified back then. Incidentally, he happened to help create what was to become known as the computer we know today. At the same time, another mathematician, Alonzo Church, independently also came up with an answer to the question “what we mean by computation?” but his formulation was in the form of a formal system called Lambda Calculus.  

Figure 1: Alan Turing and Alonzo Church 

Background 

Every computer is equivalent to a Turing Machine, and conversely any Turing Machine can compute anything any other computer can. Perhaps this is one of the more astonishing facts about them: being a really simple machine, a Turing Machine can theoretically, given enough time and resources, run anything you can run on a computer, any algorithm. A small mechanical Turing Machine, such as the one further described, can totally emulate the computer where you are reading this article right now, all the software, operational system etc down to the functionality of the silicon chips. To be more precise, usually Turing Machines are used as basic computational device to which other systems/machines are compare to, so if we say the former is compatible to a Turing Machine, then we mean it has the power to calculate or execute any computable function.

Figure 2: Screen shoot of the simulator 

Description of a Turing Machine 

Back in the 30s, the machine was usually conceived as, perhaps, an electrical/mechanical or even a purely mechanical one, since this was a time when electronics was not so ubiquitous. A Turing Machine could be a device composed of: 

1. A tape with some capability to store symbols. To start with, this tape can be thought as a 1 dimension tape, storing symbols side by side along the tape. The method to write a symbol in a position on the tape could be something like making use of a magnetic recording device (the HEAD). 
2. A finite set of symbols, that is, an alphabet of symbols, in our case the numbers {0,1,2...n} 
3. The HEAD: a device to read and write the symbols in a given position along the tape and capable to make a move one position left or right of the current position. 
4. A variable called state, which is an indication of the current state of the machine. The possible states form a finite set of symbols, in our case the letters {A, B, C etc}. The state and the symbol being read indicate the next move executed by the HEAD. Given some symbol being read and the current state, the machine prints another symbol in the current position of the tape, move the HEAD left or right and change its state. A special state called HALT, when eventually reached by the machine, effectively halts the machine and this is the end of the computation. The set of all those instructions can be arranged in a table. 

Turing also describe it, in his original paper [http://plms.oxfordjournals.org/content/s2-42/1/230], as if we manually write symbols on a paper (and them one could follow the rules describe in the state table, so he/she can compute the same thing manually). 

Figure 3: Turing Machine Description. 

For example, consider the following instruction “If the head reads symbols 1 in the current position P on the tape, and the current state is A, then write symbol 0, move HEAD left and go to state B”. This instruction can be represented in pseudo-code as:

If read(p)=1 and state=A Then {  
  Print(0,p);
  P=P-1; 
  state=B;
}

So instructions between {} above can be indexed by the symbol currently being read and the current state. If we build a table where rows indicate the symbols being read 0,1,2...n and the columns are the possible states A, B, C etc then we can store in each cell of the table the instructions to be performed in a coded form, for example, like “P0,L,B” (for the example above) or “P1,R,A” always meaning “Print, Move to..., Go to state...”. In the present simulator there is a table exactly like this in a DataGridView control, and the user can edit manually the table clicking in the cell, to modify/create a new machine. We reserved the letter Z to the HALT state, i.e., when the letter Z is encountered the machine stops. The machine can be summarized as being in a constant loop executing such instructions until the HALT instruction is encountered (or if it is never encountered the machine loops forever). 

Figure 4: A state table example (above) and how it was encoded in the DataGridView (below). 

And that’s all. Given a machine constructed to perform the instructions contained in the state table, the machine will start to run and some sets of symbols will be written on the tape. We can cleverly and carefully write a “program” (i.e., the state table) to write some desired string of symbols in the tape to some extent. The result can be some calculation, the resulting string representing some number. In other cases we can almost randomly choose a state table without any prior knowledge of what the machine will write on the tape, or even if the HALT state will be reached. 

So in computability theory, Turing Machines are used as abstract models of computation. There are fundamental problems related to computation, formal systems, metamathematics etc that can be formulated by means of a Turing Machine.  I pointed out a famous one, the “Halting Problem”:

[http://en.wikipedia.org/wiki/HALTing_problem] 

Another one is the intriguing “game” formulated originally by the Hungarian mathematician Tibor Radó in the 60s: the “Busy Beaver game” [http://en.wikipedia.org/wiki/Busy_beaver]. As explained in the Wikipedia article: 

“In computability theory, a Busy Beaver (from the colloquial expression for an industrious person) is a Turing machine that attains the maximum "operational busyness" (such as measured by the number of steps performed, or the number of nonblank symbols finally on the tape) among all the Turing machines in a certain class. The Turing machines in this class must meet certain design specifications and are required to eventually halt after being started with a blank tape. 

A Busy Beaver function quantifies these upper limits on a given type of "operational busyness", and is a noncomputable function. In fact, a Busy Beaver function can be shown to grow faster asymptotically than does any computable function. The concept was first introduced by Tibor Radó as the "Busy Beaver game" in his 1962 paper, "On Non-Computable Functions".” 

Usually one says that a Turing Machine with a specific state table and rules have a configuration mainly described by the number of states and number of symbols. For example, a configuration that runs a Busy Beaver function can appear as BB(4,2) meaning a Busy Beaver program (function) that have a state table with 4 states and 2 possible symbols to read/print. Note that many other state tables with different rules, but all with 4 states and 2 symbols, can be built. The Busy Beaver function is the function that in this class of configuration produces the maximal numbers of the shifts of the HEAD or the maximal numbers of symbols in the tape. The game proposed by Radó is to discover what is the configuration for each possible combination of number of states and symbols that gives the BB function for that class. 

Its worth to check the amusing essay from Scott Aaronson, “Who Can Name the Bigger Number?” [http://www.scottaaronson.com/writings/bignumbers.html] 

The Simulator  

This Turing Machine Simulator was developed for educational and didactics purposes only. It was not design for speed in mind, which by the way was reduced due to the screen drawing code execution. On the other hand, the simulator was developed in a manner to take advantages of some nice functionality of the .NET framework: the whole machine is contained in the class TuringMachine.cs. This class exposes properties about the configuration and state of the machine and then we use the propertyGrid control to bind the object TuringMachine to the control to show the properties on the screen. Additionally the TuringMachine.cs class has a set of events which are treated by handlers in the application Form to capture events related to the machine: Head Move, Halt, Process, Start, Tape Resize and an Exception Handler (for instance, if the machine reaches the end of the tape). The user can interactively change properties of the machine by modifying the values in the propertyGrid. 

The main Form has a toolbar with some useful functionality: a state table (effectively a “program” for a Turing Machine) can be saved and retrieved from disk. The state table DataGridView can be edited by the user, to modify/create a new machine. 

The TuringMachine class has a capability similar to some common “Debug Mode” found in compilers:  

1. Choose some example state table displayed in the ComboBox in the toolbar (ex: “Busy Beaver 4,2”). 
2. In the propertyGrid change the property “StepThrough” to “True”.  
3. Click the “Run” button. The Machine starts but every step should be fired by the user by clicking the “Step into” button. 
4. The “Pause/Continue” button can be clicked anytime to resume normal execution.  

This step through mode together with the graphic displays of the tape, head and the highlightings on the state table DataGridView helps give the user a good understanding of how a Turing Machine works. 

Every Turing machine has a state table. The class TuringMachine.cs holds a state table in an ArrayList object where each row has the instructions for actions in case the symbols 0,1,2,3 etc are read in the tape, the symbol being used as index for the row in the table. Figure 5 shows how some state table can be created with an ArrayList.  

Figure 6: TuringMachine Class. 

When the machine is running, the events fired by the TuringMachine object are intercepted by the handlers in the Form object. The drawing code involved then updates the machine drawing in the screen, i.e., the tape and head drawings, tape content etc. The drawing code takes longer to update longer tapes, but if the application is minimized, and the drawing is not being displayed on the screen, the speed is greatly improved. Additionally, a system tray icon is displayed to inform the user that the simulator is running, and a user click in this icon maximizes the application again. 

Creating a Machine 

The description given to create a new machine is a matter of a few lines of code: 

1. Instantiate a TuringMachine object (in the Form1.cs this is done in the frmMain_Load() method. Check the CreateEmptyMachine() method. This method also binds the TuringMachine object to the propertyGrid control).
2. Set the properties of the machine.
3. Add a state table
4. Bind the state table ArrayList to the DataGridView
5. Run the application and click the “Run” button. The machine is prepared and the method StartMachine() on the TuringMachine object is called. 

The code can be similar to the following excerpt (assume we already have an object named TM which is a instance of the TuringMachine.cs. The state table, in this example, is a form of the Busy Beaver game program for a Turing Machine)

TM.NumberOfstates = 6;
TM.Name = "Busy Beaver 6 states 2 symbols";
TM.FillSymbol = "0";
TM.Initialstate = "A";

ArrayList stateTableBB62 = new ArrayList();

stateTableBB62.Add(new stateTableRow(
                0,
                "P1,R,B",
                "P0,R,C",
                "P1,L,D",
                "P0,L,E",
                "P0,R,A",
                "P1,L,A",
                    "",
                    "",
                    "",
                    "",
                    "",
                    ""
                ));

            stateTableBB62.Add(new stateTableRow(
                1,
                "P0,L,F",
                "P0,R,D",
                "P1,R,E",
                "P0,L,D",
                "P1,R,C",
                "P1,R,Z",
                    "",
                    "",
                    "",
                    "",
                    "",
                    ""
                ));

dataGridView1.DataSource = stateTableBB62;
// This method reshapes the dataGridView to show the correct numbers of columns and rows
RedefineNumberOfstates(TM);


// Some possible code, on the Form1.cs class, to prepare and start the machine:

FillTape(TM.FillSymbol);
TM.Currentstate = TM.Initialstate;
TM.CurrentTapePosition = TM.TapeLength / 2;

// These two methods are part of the drawing methods group inside Form1.cs
MoveHeadOnScreenTo(TM.CurrentTapePosition);
MoveStartMarkerOnScreenTo(TM.CurrentTapePosition);

TM.stateTable = (ArrayList)dataGridView1.DataSource;
TM.StartMachine();