/* Turing Machine Simulation.    RJ Botting April 93 */
/* A Turing Machine is a good theoretical model of what a computer can do
     if there were no limits to its storage capacity.
 
   If a Turing Machine can't be programmed to do it, then it is certain that no
	normal computer can be programmed to handle it.
 
	From now on "TM" is an abreviation for "Turing Machine".
*/

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
typedef	char * string;

/*  A  TM has two parts - a finite processor and a unlimitted tape that is used
	for input, storage and output.  
	We define each in turn: First the tape and then the processor(CPU).
*/

/*	The tape is a large number of identical "cells"
	 and each cell has a value in a finite set of values
	- including a special blank value.   
	In theory the set of values can be any finite set
	 - like { 0,1, blank} or a record.
	I model each cell as a character since this is easy to print.
*/
typedef char	CELL;
#define	BLANK	' '
#define TAPE_LENGTH	70
CELL tape[TAPE_LENGTH];
	/* In theory TAPE_LENGTH is infinite.
	 This is a finite approximation therefore 
	*/
/* Stub function to request more tape if needed */
void	out_of_tape(void) 
{ 
	fprintf(stderr, "Simulation ran out of tape\n"); 
	exit(1);
}

/* The CPU is limitted to accessing one cell in the tape at a time - this 
	is thought as being the cell underneath a read/write head.
   I choose to always start the simulation at the middle of the tape
*/
int	head = TAPE_LENGTH / 2;

/*  The CPU is limited to four operations
	READ	returns the value of the cell underneath the head.
	WRITE	Change the value in the cell underneath the head.
	LEFT	move the head to the cell on the left of the current.
	RIGHT	move the head to the cell on the right of the current.
*/

#define	READ(value)	{if( 0<=head && head <TAPE_LENGTH ) value=tape[head];else out_of_tape();}
#define	WRITE(value)	{if( 0<=head && head <TAPE_LENGTH ) tape[head]=value;else out_of_tape();}
#define	LEFT	(head--)
#define	RIGHT	(++head)

/*  The CPU has a state that can be any one of a finite number of states.
	There is an initial state and a final state(HALT).
    This simulation uses characters to encode the states
	with '0' as the initial state and 'H' for HALT
*/
typedef char	STATE;
#define	INITIAL	'0'
#define	HALT	'H'
STATE state = INITIAL;
/*  The CPU has a simple cycle that runs until the state is equal to HALT.
  A finite table that describes the possible actions and acts as the TM's
	program.  The table associates each STATE and CELL value with
	a new CELL value, a movement, and a new state.
*/
#define	WILD	'*'
#define DONOTHING	"**H**"
/* 
  To save typing I let WILD act as a wild card state of character.
  This simulation uses an array of 5 character strings so that they are easy to
	print and read.
*/
typedef char ROW[6];
/* Exercise: Redeclare the entry in the table to be a record.  */
#define NROWS	100
ROW table[NROWS];
/*
Each row in the table is coded is as follows:
	0	old state with WILD as a wild card
	1	cell value with WILD as a wild card
	2	new state with WILD meaning that is the old value
	3	new cell value with WILD meaning that is the old value
	4	movement ('R' = to the right, 'L' = to the left, else none)
*/
#define	OLDS(i)	(table[i][0])
#define	OLDV(i)	(table[i][1])
#define	NEWS(i)	(table[i][2])
#define	NEWV(i)	(table[i][3])
#define	MOVE(i)	(table[i][4])

int	cycle(void) /*returns 0 when halted, else returns 1 */
{
	/* globals: state, head, tape, table.*/
	int	i; /* used to search table */
	CELL	c; /* current head's value */
	if (state == HALT)
		return(0);

	READ(c);
	for (i = 0; i < NROWS &&
			((OLDS(i) != state && OLDS(i) != WILD) ||
			 (OLDV(i) != c && OLDV(i) != WILD)
			); 
			i++)
		;
	if ( i == NROWS) { 
		fprintf(stderr, "state and cell value not in table"); 
		exit(2);
	}

	if(NEWS(i)!=WILD) state = NEWS(i); 
	if(NEWV(i)!=WILD) WRITE(NEWV(i));

	if (MOVE(i) == 'R') 
		RIGHT;
	else if (MOVE(i) == 'L') 
		LEFT;

	return (state != HALT);
}



void	display(void) /* show current state */
{
	int	i;

	printf("Tape   >");
	for (i = 0; i <= TAPE_LENGTH-1; i++)
		printf("%c", tape[i]);
	printf("\n");
	printf("State= %*s%c\n",  head+1, "", state);
}



void	load( int argc, string argv[]); /* loads up the state table and tape */
void	initialise(void); /* Puts blanks on tape and sets table to Halts*/
int askfor(string prompt);/* prompt user for a character */

main( int argc, string argv[])
{
	initialise();
	load(argc, argv);
	do
		display();
	while ( cycle() );
	display();
	exit(0);
}



void	load( int argc, string argv[])
{	
	int	i, n;  int file; FILE * fp; 
	string fname="default_Turing_Machine.tm";
	
	printf("Turing Machine Simulation\n");
	printf("    Initial State\n");
	printf("Input the head\'s position (between 0 and %d): ",TAPE_LENGTH-1);
	fflush(stdout);
	scanf("%d", &head);
	printf("Content of tape(a string with no spaces): "); fflush(stdout);
	scanf("%s", tape+head);

	if(argc==2){
		fp=fopen(argv[1], "r");
		if(fp==NULL){
			fprintf(stderr,"Can not open %s\n", argv[1]);
			exit(1);
		}
		i=0;
		while( (fscanf(fp,"%s",table[i]))==1)i++;
		n=i-1;
	}
	else{

	do file=askfor("Is the program on file (Y/N)? ");
	while(file!='Y' && file!='y' && file!='N' && file!='n');

	if(toupper(file)=='Y')
	{ 
		do{
			printf("File name? ");fflush(stdout);scanf("%s",fname);
		}while((fp=fopen(fname, "r"))==NULL);
		i=0;
		while( (fscanf(fp,"%s",table[i]))==1)i++;
		n=i-1;
	}
	else{
		printf("Input up to %d rows for the Turing Machine Table.\n",NROWS+1);
		printf("The initial state is 0, and the Halting state is H\n");
		for(i=0; i<NROWS; i++){
			int temp;
			printf("Row %d. \nTap CTRL/D at end\n", i);
			temp=askfor("Old state: ");
			if(temp==EOF)break;
			table[i][0]=temp;
			table[i][1]=askfor("Old  head: ");
			table[i][2]=askfor("New state: ");
			table[i][3]=askfor("New head : ");
			table[i][4]=toupper(askfor("Movement : "));
			table[i][5]='\0';
			printf("                   %s\n",table[i]);
		}
		printf("\n");
		n=i-1;
 		printf("Save in file name? ");fflush(stdout);scanf("%s",fname);
		if((fp=fopen(fname, "w"))!=NULL){
			printf("Saving in %s\n",fname);
			for(i=0; i<=n; ++i) fprintf(fp,"%s\n", table[i]);
		}
	}
	}
	printf("\nListing of Table\n");
	for(i=0; i<=n; i++){
		if(strcmp(table[i], DONOTHING))
			printf("%s\n",table[i]);
	}
}
void	initialise(void)
{
	int	i;

	for(i=0; i<TAPE_LENGTH; ++i)
		tape[i]=BLANK;

	for(i=0; i<NROWS; ++i)
		strcpy(table[i],  DONOTHING);

}

int askfor(string prompt)
{
	int ch;
	printf(prompt);fflush(stdout); 
	do{
		ch=getchar();
	}while(ch!=EOF && isspace(ch));

	return ch;
}