Crossroads - Spring 2012

if(DIR==’L’){
if(HEADER==0){
TAPE _ size++;

TAPE = (int *)recalloc(TAPE _ size, 2); for(i= 1;i<TAPE _ size;i++)

TAPE[i- 1] = TAPE[i];

}
else
HEADER– –;

}
if(DIR==’R’){
if(HEADER==MAX _ SIZE){
TAPE _ size++;
TAPE = (int *)recalloc(TAPE _ size, 2);
}
else
HEADER++;

}

Now, we can simulate the machine by browsing through the tape until it reaches to the end (the blank symbol “$”) and also the final most state belongs to the set of final states.

while(SYMBOL!=’$’)

TRANSITION _ rule(STATE, SYMBOL); for(i=0;i<FINAL _ size;i++)

if(STATE==FINAL[i]) printf(“INPUT accepted”);

Certainly, the allocated memories are required to be freed after the simulation. Finally to complete the code, include the declarations of the temporary variables and the header files for standard I/O functions (stdio.h) and for memory allocation functions (stdlib.h).

Several interesting resources are available on the Web for an adequate understanding of the TM model and its simulation. A couple of TM simulators with graphical interfaces are available online [ 2, 3, 4]. In fact, the TM model can be realized in many different ways [ 5]; those who are interested in the implementation of TM in different programming languages other than C (like C++, Haskell, Java, OCaml, Ruby, Scheme, and Unlambda) can delve deeper [ 6]. This wiki page also incorporates realizations of TM with La TeX, a document preparation system, and a stream editor Sed. There is also an online competition, managed by H. Zenil and J. Paul-Delahaye, for writing the shortest code for simulating a TM [ 7]. So, try and crack the game!

References

[ 1] Hopcroft, J. and J. Ullman. Introduction to Automata Theory, Languages and Computation (1st ed.). Addison– Wesley, Reading, Mass, 1979.

[ 2] Turing Machine Visualization
http://www.asethome.org/mathfoundations/ TuringMachine.swf
[ 3] Turing Machine Simulator
http://ironphoenix.org/tril/tm
[ 4] http://morphett.info/turing/turing.html
[ 5] Turing Machine Gallery
http://en.wikipedia.org/wiki/ Turing_machine_gallery
[ 6] Literate Programs Turing Machine Simulator (C)
http://en.literateprograms.org/ Turing_machine_simulator_(C)