home *** CD-ROM | disk | FTP | other *** search
/ ProfitPress Mega CDROM2 …eeware (MSDOS)(1992)(Eng) / ProfitPress-MegaCDROM2.B6I / MISC / EDUCATIO / TURING10.ZIP / TURING.C < prev    next >
Encoding:
C/C++ Source or Header  |  1992-05-28  |  9.9 KB  |  343 lines
  1. /* Turing Machine V 1.0 (C) Copyright 1991 Kevin Dahlhausen */
  2.  
  3. #include <stdlib.h>
  4. #include <stdio.h>
  5. #include <string.h>
  6. #include <conio.h>
  7. #include <dos.h>
  8.  
  9. #define TAPESIZE 1000      /* number of positions on tape */
  10. #define MAXNUMSTATES 256   /* max number of internal states */
  11.  
  12. #define BLANK '0'          /* blank character on tape */
  13. #define UNDEFINED -1       /* 'next state' field of an undefined state */
  14. #define INITIALSTATE 0     /* tm begins execution in this state */
  15.  
  16. #define SCREENWIDTH 80
  17. #define TAPEY 5            /* tape y position on screen */
  18. #define TMXADJ 4           /* distance UL corner of tm picture to read head */
  19.  
  20. typedef struct {
  21.    int   state;
  22.    char  read;             /* mark on tape to match */
  23.    int   nextstate;        /* next state to goto */
  24.    char  write;            /* put this symbol on the tape */
  25.    char  command;          /* what to do here */
  26. } statedef;
  27.  
  28. /* function prototypes */
  29. char ReadTape(int);
  30. void WriteTape(int, char);
  31.  
  32. /* global variables */
  33. int TapeBase;              /* index of leftmost tape mark on screen */
  34. char tape[TAPESIZE];
  35.  
  36. /**************************************************************************/
  37. void SetCursor(char start, char end)
  38. /* requires: none
  39.  * ensures:  cursor start, end lines set as given
  40.  *
  41.  * Note: This routine is only used for aesthetic purposes
  42.  */
  43. {
  44.    struct REGPACK regs;
  45.    regs.r_ax=0x0100;
  46.    regs.r_cx=(start*256)+end;
  47.    intr(0x10, ®s);
  48. }
  49.  
  50. /**************************************************************************/
  51. void DrawTM(int x, int y, int state)
  52. /* requires: none
  53.  * ensures:  TM is drawn at x,y with state
  54.  */
  55. {
  56.   gotoxy(x,y+0);     printf("    ║  ");
  57.   gotoxy(x,y+1);     printf("╔═══╩═╗");
  58.   gotoxy(x,y+2);     printf("║     ║");
  59.   gotoxy(x,y+3);     printf("╚═════╝");
  60.   gotoxy(x+2,y+2);   printf("%-3d",state);
  61. }
  62.  
  63. /**************************************************************************/
  64. void EraseTM(int x, int y)
  65. /* requires: none
  66.  * ensures:  TM is erased
  67.  */
  68. {
  69.   gotoxy(x,y);       printf("       ");
  70.   gotoxy(x,y+1);     printf("       ");
  71.   gotoxy(x,y+2);     printf("       ");
  72.   gotoxy(x,y+3);     printf("       ");
  73. }
  74.  
  75.  
  76. /**************************************************************************/
  77. void DrawTape(int y, int start)
  78. /* requires: none
  79.  * ensures:  tape is drawn on screen at position y starting at index start
  80.  */
  81. {
  82.    int i;
  83.    gotoxy(1,y);
  84.    for (i=0;i<SCREENWIDTH;i++) printf("%c",ReadTape(start++));
  85. }
  86.  
  87.  
  88. /**************************************************************************/
  89. void InitTape(int *itp)
  90. /* requires: none
  91.  * ensures:  tape is initialized for use
  92.  */
  93. {
  94.  int i;
  95.  int index;
  96.  char string[255];
  97.  
  98.  for (i=0;i<TAPESIZE;i++) tape[i]=BLANK;
  99.  
  100.  printf("\nTape index at start of string (tape length is %d): ", TAPESIZE);
  101.  scanf("%d",&index);
  102.  printf("\nString to put at position %d:",index);
  103.  scanf("%s",&string);
  104.  strncpy(&tape[index],string,strlen(string));
  105.  printf("\nInitial read/write head position?");
  106.  scanf("%d",itp);
  107.  
  108. }
  109.  
  110.  
  111. /**************************************************************************/
  112. char ReadTape(int HeadPos)
  113. /* requiers: 0<=HeadPos<TAPESIZE
  114.  * ensures:  symbol at HeadPos is read
  115.  * returns:  BLANK or MARK
  116.  */
  117. {
  118.  if ( (0<=HeadPos)&&(HeadPos<TAPESIZE)) return tape[HeadPos];
  119.  else {
  120.    printf("\n Error: attempted read past end of tape");
  121.    exit(1);
  122.  }
  123. }
  124.  
  125.  
  126. /**************************************************************************/
  127. void WriteTape(int HeadPos, char value)
  128. /* requires: 0<=HeadPos<TAPESIZE
  129.  * ensures:  value is written to tape at position HeadPos
  130.  */
  131. {
  132.  if ( (0<=HeadPos)&&(HeadPos<TAPESIZE)) tape[HeadPos]=value;
  133.  else {
  134.    printf("\n Error: attempted write past end of tape");
  135.    exit(1);
  136.  }
  137.  DrawTape(TAPEY, TapeBase);
  138. }
  139.  
  140.  
  141. /**************************************************************************/
  142. void RightMove(int *HeadPos, int state)
  143. /* requires: HeadPos+1<TAPESIZE
  144.  * ensures:  machine moved one space to right on tape
  145.  */
  146. {
  147.   EraseTM(*HeadPos-TMXADJ+1-TapeBase,TAPEY+1);
  148.   (*HeadPos)++;
  149.   if (*HeadPos>=TAPESIZE) {
  150.    printf("\n Error: attempted move past right end of tape");
  151.    exit(1);
  152.   }
  153.   if ((*HeadPos-TMXADJ+1-TapeBase)>SCREENWIDTH-10) {
  154.      TapeBase=TapeBase+(SCREENWIDTH*0.5);
  155.      if (TapeBase>(TAPESIZE-SCREENWIDTH)) TapeBase=(TAPESIZE-SCREENWIDTH);
  156.      DrawTape(TAPEY, TapeBase);
  157.   }
  158.   DrawTM(*HeadPos-TMXADJ+1-TapeBase,TAPEY+1, state);
  159. }
  160.  
  161.  
  162. /**************************************************************************/
  163. void LeftMove(int *HeadPos, int state)
  164. /* requires: 0<HeadPos
  165.  * ensures:  machine moved one space to left on tape
  166.  */
  167. {
  168.   EraseTM(*HeadPos-TMXADJ+1-TapeBase,TAPEY+1);
  169.  (*HeadPos)--;
  170.  if (0>*HeadPos) {
  171.    printf("\n Error: attempted move past left end of tape");
  172.    exit(1);
  173.  }
  174.   if ((*HeadPos-TMXADJ+1-TapeBase)<5) {
  175.      TapeBase=TapeBase-(SCREENWIDTH*0.5);
  176.      if (TapeBase<0) TapeBase=0;
  177.      DrawTape(TAPEY, TapeBase);
  178.   }
  179.  
  180.  DrawTM(*HeadPos-TMXADJ+1-TapeBase,TAPEY+1, state);
  181. }
  182.  
  183.  
  184. /**************************************************************************/
  185. void Stop()
  186. /* requires: none
  187.  * ensures:  bell is rung, machine stopped, signals completion of calculation
  188.  */
  189. {
  190.    printf("\x07");
  191.    getch();
  192. }
  193.  
  194.  
  195. /**************************************************************************/
  196. void GetTM(char *filename, statedef *t, int *NumDefs)
  197. /* requires: filename is a valid TM definition file
  198.  * ensures:  turing machine definition is read from a file
  199.  */
  200. {
  201.   int i;
  202.   FILE *infile;
  203.   char nextline[81];
  204.   char result;
  205.  
  206.   for (i=0;i<MAXNUMSTATES;i++) t[i].nextstate=UNDEFINED;
  207.  
  208.    if ((infile=fopen(filename,"rt"))==NULL) {
  209.       printf("\nError: Unable to open file:%s",filename);
  210.       exit(1);
  211.    }
  212.  
  213.    i=0;
  214.    while((fgets(nextline,80,infile) != NULL)&&(i<MAXNUMSTATES)) {
  215.       if (nextline[0] != '#') {     /* ignore comments */
  216.          result=sscanf(nextline, "%d,%c->%d,%c,%c",
  217.              &t[i].state, &t[i].read, &t[i].nextstate,
  218.              &t[i].write, &t[i].command);
  219.          if (result != 5) {   /* sscanf should convert 5 fields */
  220.             printf("\nError: Bad state format, line %d: %s",i+1,nextline);
  221.             exit(1);
  222.          }
  223.          i++;
  224.       }
  225.   }
  226.   fclose(infile);
  227.   *NumDefs=i;
  228. }
  229.  
  230.  
  231. /**************************************************************************/
  232. void LookUp(statedef tm[], int NumDefs, int state, char sym,
  233.             int *nstate, char *wsym, char *command)
  234. /* requires: tm[0]..tm[NumDefs-1] are valid state definitions
  235.  * ensures:  nstate, wsym, commmand are set as required when
  236.  *           the tm is in state and has read sym from the tape
  237.  *
  238.  * NOTE: Presently this is just a a linear search of the tm definition
  239.  *       array. This action was made a separate funcion to ease any
  240.  *       future changes to the access method.
  241.  */
  242. {
  243.  int i=0, found=0;
  244.  
  245.  while( (!found)&&(i<NumDefs)) {
  246.    if ((tm[i].state==state)&&(tm[i].read==sym)) {
  247.       found=1;
  248.       *nstate=tm[i].nextstate;
  249.       *wsym=tm[i].write;
  250.       *command=tm[i].command;
  251.    }
  252.    i++;
  253.  }
  254.  
  255.  if (!found) {
  256.    printf("\nError: Unable to find definition for read of %c in state %d",
  257.     sym,state);
  258.    exit(1);
  259.  }
  260. }
  261.  
  262. /**************************************************************************/
  263. void InitScreen(int base, int HeadPos)
  264. /* requires: HeadPos - base < SCREENWIDTH + TMXADJ
  265.  * ensure:   screen is drawn with tape starting at base, tm at HeadPos
  266.  */
  267. {
  268.    clrscr();
  269.    printf("     Turing Machine Simulator (C) Copyright 1991 Kevin Dahlhausen");
  270.    TapeBase=base;
  271.    DrawTape(TAPEY, TapeBase);
  272.    DrawTM(HeadPos-TMXADJ+1-TapeBase,TAPEY+1, 0);
  273. }
  274.  
  275.  
  276. /**************************************************************************/
  277. void RunTM( statedef tm[], int NumDefs, int itp)
  278. /* requires:   tm[0]..tm[NumDefs-1] are valid state definitions
  279.  *             itp is the initial postion of the tm on the tape
  280.  * ensures:    turing machine computation is simulated
  281.  */
  282. {
  283.    int state=INITIALSTATE;          /* current state number */
  284.    char symbol;                     /* last symbol read from tape */
  285.    int notdone=1;
  286.    long int cycles=1;
  287.    int HeadPos;                     /* position of tm on tape */
  288.    int nextstate;                   /* next state to go to */
  289.    char writesym;                   /* symbol to write on tape */
  290.    char command;                    /* command to perform */
  291.  
  292.    HeadPos=itp;
  293.  
  294.  
  295.    InitScreen(HeadPos-20, HeadPos); /* draw initial screen */
  296.  
  297.    while (notdone) {
  298.       symbol=ReadTape(HeadPos);
  299.       LookUp(tm, NumDefs, state, symbol, &nextstate, &writesym, &command);
  300.       WriteTape(HeadPos, writesym);
  301.       gotoxy(1,20);
  302.       printf("Position:%3d  State:%-3d  Read:%c  Next state:%-3d Wrote:%c ",
  303.       HeadPos, state, symbol, nextstate, writesym);
  304.       printf(" Command:%c  Cycles:%d", command ,cycles);
  305.  
  306.       switch (command) {
  307.       case 'R':   RightMove(&HeadPos, state);
  308.                   break;
  309.       case 'L':   LeftMove(&HeadPos, state);
  310.                   break;
  311.       case 'S':   Stop();
  312.                   notdone=0;
  313.                   break;
  314.       default:    printf("\nError: illegal command in state %d read &c",
  315.                          state, symbol);
  316.                   exit(1);
  317.       }
  318.       state=nextstate;
  319.       cycles++;
  320.    }
  321. }
  322.  
  323.  
  324. /**************************************************************************/
  325. main()
  326. {
  327.    int NumDefs; /* number of state definitions */
  328.    int itp;     /* initial tape position */
  329.    char name[80];
  330.  
  331.    statedef tm[MAXNUMSTATES]; /* internal definition of Turing Machine (tm) */
  332.  
  333.    printf("\n     Turing Machine Simulator (C) Copyright 1991 Kevin Dahlhausen");
  334.    printf("\nMachine to run? ");
  335.    scanf("%s",name);
  336.  
  337.    GetTM(name, tm, &NumDefs);    /* input internal state definitions */
  338.    InitTape(&itp);                  /* setup the tape */
  339.  
  340.    SetCursor(32, 32);
  341.    RunTM(tm, NumDefs, itp);
  342.    SetCursor(6,7);
  343. }