title: Turing Machine Implementation in C
body: <p>I'm studying Turing machines for my course in formal languages ​​theory, the professor recommended a run on the following <a href="http://code.zhoubot.com/archives/52" rel="nofollow">algorithm</a> to see in detail the logic behind of a "TM", but doesn't work, when trying to compile tells me the following error.</p>
  
  <pre><code>C:\Documents and Settings\Melkhiah.EQUIPO01\Mis documentos\Downloads\Tarea3 Discretas\TM.c||In function `Tape* insert_tape(Tape*, Direction, char)':|
  C:\Documents and Settings\Melkhiah.EQUIPO01\Mis documentos\Downloads\Tarea3 Discretas\TM.c|44|error: invalid conversion from `void*' to `Tape*'|
  C:\Documents and Settings\Melkhiah.EQUIPO01\Mis documentos\Downloads\Tarea3 Discretas\TM.c||In function `Tape* create_tape(char*)':|
  C:\Documents and Settings\Melkhiah.EQUIPO01\Mis documentos\Downloads\Tarea3 Discretas\TM.c|68|error: invalid conversion from `void*' to `Tape*'|
  C:\Documents and Settings\Melkhiah.EQUIPO01\Mis documentos\Downloads\Tarea3 Discretas\TM.c||In function `Transition* get_transition(char*)':|
  C:\Documents and Settings\Melkhiah.EQUIPO01\Mis documentos\Downloads\Tarea3 Discretas\TM.c|80|error: invalid conversion from `void*' to `Transition*'|
  C:\Documents and Settings\Melkhiah.EQUIPO01\Mis documentos\Downloads\Tarea3 Discretas\TM.c||In function `List* insert_list(List*, char*)':|
  C:\Documents and Settings\Melkhiah.EQUIPO01\Mis documentos\Downloads\Tarea3 Discretas\TM.c|93|error: invalid conversion from `void*' to `List*'|
  C:\Documents and Settings\Melkhiah.EQUIPO01\Mis documentos\Downloads\Tarea3 Discretas\TM.c||In function `List* insert_list_transition(List*, Transition*)':|
  C:\Documents and Settings\Melkhiah.EQUIPO01\Mis documentos\Downloads\Tarea3 Discretas\TM.c|105|error: invalid conversion from `void*' to `List*'|
  C:\Documents and Settings\Melkhiah.EQUIPO01\Mis documentos\Downloads\Tarea3 Discretas\TM.c||In function `TM* createTM(char*)':|
  C:\Documents and Settings\Melkhiah.EQUIPO01\Mis documentos\Downloads\Tarea3 Discretas\TM.c|166|error: invalid conversion from `void*' to `TM*'|
  C:\Documents and Settings\Melkhiah.EQUIPO01\Mis documentos\Downloads\Tarea3 Discretas\TM.c|167|error: invalid conversion from `void*' to `List*'|
  ||=== Build finished: 7 errors, 0 warnings ===|
  </code></pre>
  
  <p>here's the code: </p>
  
  <pre><code>/* This C file implements a Non-determinitic Pushdown Automata
   * author: Kevin Zhou
   * Computer Science and Electronics
   * University of Bristol
   * Date: 21st April 2010
   */
  #include&lt;stdio.h&gt;
  #include&lt;stdlib.h&gt;
  #include&lt;string.h&gt;
  
  typedef struct tapes {
      struct tapes *left;
      struct tapes *right;
      char content;
  } Tape;
  
  typedef enum { LEFT,RIGHT } Direction;
  
  typedef struct transition {
      char current_state;
      char tape_symbol;
      char new_state;
      char new_tape_symbol;
      Direction dir;
  } Transition;
  
  typedef struct list {
      Transition *content;
      struct list *next;
  } List;
  
  typedef struct tm {
      char *input_alpha;
      char *input;
      char *tape_alpha;
      char start;
      char accept;
      char reject;
      List *transition;
  } TM;
  
  Tape *insert_tape(Tape *t, Direction dir, char c) {
      Tape *head = t;
      Tape *new1 = calloc(1,sizeof(Tape));;
      new1 -&gt; content = c;
      if(dir == LEFT) {
          while(t-&gt;left != NULL) {
              t = t-&gt;left;
          }
          new1-&gt;right = t;
          new1-&gt;left = NULL;
          t-&gt;left = new1;
          return new1;
      }
      if(dir == RIGHT) {
          while(t-&gt;right != NULL) {
              t = t-&gt;right;
          }
          new1-&gt;left = t;
          new1-&gt;right = NULL;
          t-&gt;right = new1;
      }
      return head;
  }
  
  Tape *create_tape(char *input) {
      int i=1;
      Tape *t = calloc(1,sizeof(Tape));
      t-&gt;content = input[0];
      while(1) {
          if(input[i] == '\0') break;
          t = insert_tape(t,RIGHT,input[i]);
          i++;
      }
      return t;
  }
  
  /* turn the input string into Transition fields */
  Transition *get_transition(char *s) {
      Transition *t = calloc(1,sizeof(Transition));
      Direction dir;
      t-&gt;current_state = s[0];
      t-&gt;tape_symbol = s[1];
      t-&gt;new_state = s[2];
      t-&gt;new_tape_symbol = s[3];
      dir = (s[4]=='R')? RIGHT:LEFT;
      t-&gt;dir = dir;
      return t;
  }
  
  /* turn the string into transitions and add into list */
  List *insert_list( List *l, char *elem ) {
      List *t = calloc(1,sizeof(List));
      List *head = l;
      while(l-&gt;next!=NULL)
          l = l-&gt;next;
      t-&gt;content = get_transition(elem);
      t-&gt;next = NULL;
      l-&gt;next = t;
      return head;
  }
  
  /* insert a transition into a list */
  List *insert_list_transition( List *l, Transition *tr) {
      List *t = calloc(1,sizeof(List));
      List *head = l;
      while(l-&gt;next!=NULL)
          l = l-&gt;next;
      t-&gt;content = tr;
      t-&gt;next = NULL;
      l-&gt;next = t;
      return head;
  }
  
  void print_tape( Tape *t,char blank) {
      char c;
      while(1) {
          if(t-&gt;content != blank) break;
          t= t-&gt;right;
      }
      while(1) {
          if(t==NULL) break;
          c = t-&gt;content;
          if(t-&gt;content != blank)
              putchar(c);
          t= t-&gt;right;
      }
      putchar('\n');
  }
  
  void print_transition (Transition *t) {
      char s1[] = "Left";
      char s2[] = "Right";
      if(t==NULL) {
          printf("NULL Transfer");
          return;
      }
      printf("current:%c tape:%c new state:%c new tape:%c direction %s\n",t-&gt;current_state,t-&gt;tape_symbol,t-&gt;new_state,t-&gt;new_tape_symbol,(t-&gt;dir == LEFT)?s1:s2);
  }
  
  /*test if the char c is in the string s */
  int contains ( char c, char *s ) {
      int i=0;
      while(1) {
          if(c== s[i]) return 1;
          if(s[i] == '\0') return 0;
          i++;
      }
  }
  
  /* test if the input is a valid input */
  int is_valid_input( char *input_alpha, char *input ) {
      int i=0;
      char c;
      while(1) {
          c = input[i];
          if(c == '\0') break;
          if(!contains(c,input_alpha)) return 0;
          i++;
      }
      return 1;
  }
  
  TM *createTM (char *input) {
  
      TM *m = calloc(1,sizeof(TM));
      List *tr = calloc(1,sizeof(List));
      char *buffer;
      /*read input alphabet of PDA*/
      buffer = strtok(input,":");
      if(buffer == NULL) {
          printf("Error in reading input alphabet!\n");
          exit(1);
      }
      m-&gt;input_alpha = buffer;
  
      /*read tape alphabet*/
      buffer = strtok(NULL,":");
  
      if(buffer == NULL) {
          printf("Error in reading tape alphabet!\n");
          exit(1);
      }
      m-&gt;tape_alpha = buffer;
  
      /*read input sequence*/
      buffer = strtok(NULL,":");
      if(buffer == NULL) {
          printf("Error in reading input sequence!\n");
          exit(1);
      }
  
      if(!is_valid_input(m-&gt;input_alpha,buffer)) {
          printf("Error! Input contains some invalid characters that don't match the input alphabet!\n");
          exit(1);
      }
  
      m-&gt;input = buffer;
      buffer = strtok(NULL,":");
      m-&gt;start = buffer[0];
      buffer = strtok(NULL,":");
      m-&gt;accept = buffer[0];
      buffer = strtok(NULL,":");
      m-&gt;reject = buffer[0];
  
      /*read tape transition*/
      while(1) {
          buffer = strtok(NULL,":");
          if(buffer == NULL) break;
          tr = insert_list(tr,buffer);
      }
  
      m-&gt;transition = tr-&gt;next;
      return m;
  }
  
  Transition *find_transition(List * list,char state, char tape_symbol) {
      Transition *t;
      while(1) {
          if(list==NULL) return NULL;
          t = list -&gt; content;
          if(t-&gt;current_state == state &amp;&amp; t-&gt;tape_symbol == tape_symbol)
              return t;
          list = list-&gt;next;
      }
  }
  
  Tape *move(Tape *t,Direction dir, char blank) {
      if(dir == LEFT) {
          if(t-&gt;left==NULL) {
              t = insert_tape(t,LEFT,blank);
          }
          return t-&gt;left;
      }
      if(dir == RIGHT) {
          if(t-&gt;right==NULL) {
              t = insert_tape(t,RIGHT,blank);
          }
          return t-&gt;right;
      }
      return NULL;
  }
  
  void simulate( TM *m ) {
      /* first symbol in input symbol used to represent the blank symbol */
      const char blank = m-&gt;tape_alpha[0];
      char current_state = m-&gt;start;
      Tape *tape = create_tape(m-&gt;input);
      Tape *current_tape = tape;
      char current_tape_symbol;
      Transition *current_transition;
      while(1) {
          if(current_state == m-&gt;accept) {
              printf("Accept\n");
              print_tape(tape,blank);
              break;
          }
          if(current_state == m-&gt;reject) {
              printf("Reject\n");
              print_tape(tape,blank);
              break;
          }
          current_tape_symbol = (current_tape==NULL||current_tape -&gt;content == '\0')?blank:current_tape-&gt;content;
          current_transition = find_transition(m-&gt;transition,current_state,current_tape_symbol);
          current_state = current_transition -&gt; new_state;
          current_tape -&gt; content = current_transition -&gt; new_tape_symbol;
          current_tape = move( current_tape, current_transition -&gt;dir, blank);
      }
  }
  
  int main(void) {
      char s[300];
      TM *p;
      scanf("%s",s);
      p = createTM(s);
      simulate(p);
      return 0;
  }
  </code></pre>
  
  <p>Why is this program not work?</p>