HELLO WORLD

Simulating a Turing Machine By Malay Bhattacharyya The way we formalize the concept of computing today is greatly motivated from the design of “a(automatic)-machine” proposed long ago in 1936 by Alan Turing. This model, later known as a Turing machine ( TM), can be defined as a 6-tuple:

  where Q is a finite set of states, blank symbol, and

is the initial state,   is the set of final states, is a finite set of symbols,  is a transition function (for more details see Hopcroft and Ullman [ 1]).

 is a
A TM can be visualized as a collection of states (see Figure 1) with state transition rules ( ) over it. There is always a fixed initial
state (   ) and a set of final states (   ) specific to a pattern recognizable by the machine. The pattern recognized, which is
dependent on the transition function, distinguishes the TM models. In the example shown in Figure 1, the initial state is highlighted
with an incoming arrow while the final states are double circled. The transition rules are given in the format <Read Symbol, Write
Symbol, Direction> in brackets along the directed arrows. A TM model recognizes a pattern of symbols (e.g., the TM shown in Figure
1 recognizes the pattern xnyn- 1) if it reaches any of the final states after reading all the symbols.

Figure 1. Visualizing a Turing machine for the input pattern xnyn- 1.

This mathematical model can also be realized as a machine that
works on a tape as a tape-reader with symbols on it. The input
symbol is written over the tape ending with a blank symbol. It
uses a header pointer (marked with the states) for browsing
through the symbols on the tape. It initially points to the
leftmost end (the very first symbol) on the tape and is marked
with the initial state. At each step, the transition function
determines (based on the current symbol and current state) the
next state to be marked on the header pointer, the symbol to
write (replace) on the tape where it points, and the direction to
shift the header pointer—either left (L) or right (R). If the pointer
ever reaches a final state while reaching to the rightmost symbol (on the blank symbol), it is assumed that the machine recognizes
the symbols. The entire concept for the TM shown in Figure 1 is visualized in Figure 2.

Figure 2. Realizing the Turing machine as a tape reader. An intermediate situation is shown when the machine has already traversed through the states .

It is possible to design a TM simulator, which is capable of simulating any TM model, pursuing this simplification on a tape. For the sake of simplicity, let us assume that the states are represented as integers and input symbols as single characters. So, we require an integer array to define the final states (FINAL) and separate character arrays for denoting the tape ( TAPE) and the sequence of input symbols (INPU T).

int *FINAL; char *TAPE, *INPUT; int FINAL _ size, TAPE _ size, INPUT _ size;

// The set of final states // The tape and the sequence of input symbols // The dimensions of different arrays