//Universal Turing Machine_3 Tapes Operation
//Kwang J. Yi
//CIS 203
//Intro To Artificial Intelligence
//11/27/05
//Rough Draft


#include <stdio.h>
#include <stdlib.h>

#define MAX 100

char tape[3][MAX];
char temp[MAX];


int set(void);
int right_find(int tnum, int hloc, char key);
int left_find(int tnum, int hloc, char key);
int right_not_find(int tnum, int hloc, char key);
int left_not_find(int tnum, int hloc, char key);
int shift_right(int tnum, int hloc);
int shift_left(int tnum, int hloc);
int print_result(void);

int start(void);
int copydata(void);
int find_current_state(void);
int check_current_symbol(void);
int change_state(void);
int exe_transition(void); 
int write_symbol(void);
int check_halt(void);

int loc0, loc1, loc2;
FILE *fp;

void main(void) {

fp=fopen("turingout.txt","w");
printf("input binary code\n");
scanf("%s",temp);
fprintf(fp,"###############################################\n");
fprintf(fp,"            UNIVERSAL TURING MACHINE           \n");
fprintf(fp,"               Code by Kwang J. Yi             \n");
fprintf(fp,"                  2005.11.27                   \n");
fprintf(fp,"###############################################\n");
fprintf(fp,"\nTapes\n");
fprintf(fp,"\ntape0 inputed code\n");
fprintf(fp,"tape1 data code by tape0's data part\n");
fprintf(fp,"tape2 current state\n");
set();
start();
fclose(fp);
}


int set(void) {
//setting of tapes. 'd' is delta.

int i,j;

tape[0][0]='d';
//tape0's first blank is delta. this delta represent starting point of tape.
for(i=1; i<MAX ; i++) {
if(temp[i-1] != '\0') 
tape[0][i]=temp[i-1];
else 
break;
}


loc0=loc1=loc2=0;
//'locX' is current location of header on tape number X
for(i=0 ; i<3 ; i++) {
for( j=0 ; j<MAX ; j++) {
if(tape[i][j] == '\0' )
tape[i][j]='d';
}
}
return 0;
}

int start(void) {
//start() find data part
//if transition's start is 11, that is data part.
fprintf(fp,"\n\nfind data part\n");
while(1) {

loc0=right_find(0, loc0, '1');
loc0++;

if(tape[0][loc0]=='0') {
loc0=right_find(0,loc0,'1');
loc0=right_find(0,loc0,'1');
loc0=right_find(0,loc0,'1');
}
else if(tape[0][loc0]=='1') {
break;
}
else {
printf("error!!");
exit(0);
}
}
print_result();
copydata();
return 0;
}

int copydata(void) {
//copydata() copy data part of tape 0 to tape1
fprintf(fp,"\n\ncopy data to tape1\n");
loc0--;

while(1) {
loc0++;

if(tape[0][loc0]=='0') {
loc1++;
tape[1][loc1]='0';
}
else if(tape[0][loc0]=='1') {
loc1++;
tape[1][loc1]='1';
}
else if(tape[0][loc0]=='d') {
// if tape's symbol is 'd', end of binary code
loc0=left_find(0,loc0,'d');
loc1=left_find(1,loc1,'d');
loc1++;
loc2++;
tape[2][loc2]='0';
loc2--;
break;
}
}
print_result();
while(1) {
find_current_state();
}
return 0;
}

int find_current_state(void) {
//find the same state of tape 0 as current state of tape 2
fprintf(fp,"\n\nfind a trasition for the current state\n");
loc0=right_find(0,loc0,'1');
loc0++;

if(tape[0][loc0]=='0') {
while(1) {
loc2++;

if(tape[2][loc2] == '0' ) {
loc0++;
if(tape[0][loc0] == '1') {
break;
}
}
else if(tape[2][loc2] == 'd') {
loc2=left_find(2,loc2,'d');

loc0 = right_find(0,loc0,'1');
loc0 = right_find(0,loc0,'1');
loc0 = right_find(0,loc0,'1');

return 0;
}
}
loc2++;
if(tape[2][loc2] == '0') {
loc2=left_find(2,loc2,'d');
print_result();
loc0 = right_find(0,loc0,'1');
loc0 = right_find(0,loc0,'1');

return 0;
}
else if(tape[2][loc2] == 'd') {
loc2=left_find(2,loc2,'d');
print_result();
check_current_symbol();
return 0;
}
else {
printf("error1!!");
exit(0);
}
}
else {
printf("error2!!");
exit(0);
}
return 0;
}

int check_current_symbol(void) {
//check that transition is compatible with current symbol
fprintf(fp,"\n\ncheck transition's symbol with current symbol\n");

while(1) {

loc0++;

if(tape[0][loc0] == '0') {
loc1++;
if(tape[1][loc1] == '0') {
continue;
}
else {
//transition does not match current symbol
loc1=left_not_find(1,loc1,'0');
loc0=left_find(0,loc0,'1');
loc0 = right_find(0,loc0,'1');
loc0 = right_find(0,loc0,'1');

return 0;
}
}
else if(tape[0][loc0] == '1') {
loc1++;
if(tape[1][loc1] == '0') {
//transition does not match current symbol
loc1=left_not_find(1,loc1,'0');
loc0=left_find(0,loc0,'1');
loc0 = right_find(0,loc0,'1');
loc0 = right_find(0,loc0,'1');

return 0;
}
else {
//matched..
break;
}
}
else {
printf("error!!");
exit(0);
}
}
loc1=left_find(1,loc1,'1');
print_result();
change_state();

return 0;
}

int change_state(void) {
//change current state on tape2
fprintf(fp,"\n\nchange state on tape2\n");
print_result();
loc2=right_find(2,loc2,'d');

while(1) {
//erase tape 2
loc2--;

if(tape[2][loc2] == 'd') {
break;
}
else {
tape[2][loc2] = 'd';
continue;
}
}

while(1) {
//copy current state of tape0 to tape2
loc0++;

if(tape[0][loc0] == '1') {
break;
}
else if(tape[0][loc0] == '0') {
loc2++;
tape[2][loc2] = '0';
continue;
}
else{
printf("error!!");
exit(0);
}
}
loc2=left_find(2,loc2,'d');
exe_transition();

return 0;
}

int exe_transition(void) {
//execute one of that move left, move right, write a symbol
loc0++;
fprintf(fp,"\n\nexecute transition\n");
print_result();

if(tape[0][loc0] == '1') {
loc1=right_not_find(1,loc1,'0');
tape[1][loc1] = '1';
while(1) {
//if transition is '11', write a blank
loc1--;
if(tape[1][loc1] == '1') {
fprintf(fp,"\n\nwrite a blank\n");
break;
}
else if(tape[1][loc1] == '0') {
shift_left(1,loc1);
}
else {
printf("error3");
exit(0);
}
}
check_halt();
return 0;
}
else if(tape[0][loc0] == '0') {
loc0++;
if(tape[0][loc0] == '1') {
//if transition is '101', move left
fprintf(fp,"\n\nmove left\n");
loc1=left_not_find(1,loc1,'0');
if(tape[1][loc1] == '1') {
check_halt();
return 0;
}
else if(tape[1][loc1] == 'd') {
printf("L");
exit(0);
}
else{
printf("error6");
exit(0);
}
}
else if(tape[0][loc0] == '0') {
loc0++;
if(tape[0][loc0] == '1') {
//if transition is '1001', move right
fprintf(fp,"\n\nmove right\n");
loc1=right_not_find(1,loc1,'0');
tape[1][loc1] = '1';
check_halt();
return 0;
}
else if(tape[0][loc0] == '0') {
//if transition is '1000...1', write nonblank symbol
write_symbol();
return 0;
}
}else {
printf("error4");
exit(0);
}
}else {
printf("error5");
exit(0);
}
return 0;
}

int write_symbol(void) {
//write nonblank symbol
fprintf(fp,"\n\nwrite symbol\n");
print_result();
loc1=right_not_find(1,loc1,'0');
tape[1][loc1]='1';
while(1) {
//erase current symbol of tape1
loc1--;
if(tape[1][loc1] == '0') {
shift_left(1,loc1);
}
else if(tape[1][loc1] == '1') {
break;
}
else {
printf("error7");
exit(0);
}
}
//write '100d1' 
print_result();
tape[1][loc1] = 'd';
print_result();
loc1=right_find(1,loc1,'d');
print_result();
shift_right(1,loc1);
print_result();
loc1++;
print_result();
shift_right(1,loc1);
print_result();
loc1++;
print_result();
shift_right(1,loc1);
print_result();
loc1=left_find(1,loc1,'d');
print_result();
loc1--;
print_result();
tape[1][loc1] = '0';
loc1--;
tape[1][loc1] = '0';
print_result();
loc1--;
print_result();
tape[1][loc1] = '1';
print_result();
loc1=right_find(1,loc1,'d');
print_result();

while(1) {
//if symbol's next is 0, write 0 
//(ex. if tape0's current location is1010001000100^001, than write '00' to tape1's 'd')
loc0++;

if(tape[0][loc0] == '1'){
break;
}
else if(tape[0][loc0] == '0'){
loc1=right_find(1,loc1,'d');
shift_right(1,loc1);
loc1=left_find(1,loc1,'d');
loc1--;
tape[1][loc1] = '0';
loc1++;
}
}
tape[1][loc1]='0';
loc1=left_find(1,loc1,'1');

check_halt();
return 0;
}

int check_halt(void) {
//if current state is halt state, than copy tape2 to tape1 and exit
//if current state isn't halt state, execute another transition
fprintf(fp,"\n\ncheck for halt state\n");
print_result();
loc0=left_find(0,loc0,'d');
loc2++;
if(tape[2][loc2]=='0') {
loc2++;
if(tape[2][loc2]=='d') {
loc2=left_find(2,loc2,'d');
loc1=right_find(1,loc1,'1');
fprintf(fp,"\n\nexecute another transition\n");
print_result();
return 0;
}
else if(tape[2][loc2]=='0') {
//current state is halt
loc2++;
if(tape[2][loc2]=='d'){
loc0=right_find(0,loc0,'d');
while(1) {
loc0--;
if(tape[0][loc0] !='d') {
tape[0][loc0]='d';
}
else {
break;
}
}
print_result();
tape[1][loc1]='*';
//current location of tape1 represent '*'
loc1=left_find(1,loc1,'d');
print_result();
while(1) {
loc0++;
loc1++;

if(tape[1][loc1] == '0')
tape[0][loc0]= '0';
else if(tape[1][loc1] == '1')
tape[0][loc0]= '1';
else if(tape[1][loc1] == '*')
tape[0][loc0]= '*';
else if(tape[1][loc1] == 'd') {
loc0=left_find(0,loc0,'*');
tape[0][loc0]= '1';
printf("halt!!");
print_result();
fprintf(fp,"\n\nhalt!!\n");
exit(0);
}
}
}else {
loc2=left_find(2,loc2,'d');
loc1=right_find(1,loc1,'1');
fprintf(fp,"\n\nexecute another transition\n");
print_result();
return 0;
}
}else {
fprintf(fp,"error9!!");
exit(0);
}
}else {
printf("error8");
exit(0);
}
return 0;
}



int right_find(int tnum, int hloc, char key) {
//serch its tape 'tnum' to the right of the current 
//location 'hloc' for a symbol 'key'
int n, find_loc = -1;

for( n=hloc+1 ; n<MAX ; n++) {
if(tape[tnum][n] == key) {
find_loc=n;
break;
}
}
if(find_loc == -1) {
printf("not found error!!\n");
exit(0);
}

return find_loc;
}

int right_not_find(int tnum, int hloc, char key) {
//serch its tape 'tnum' to the right of the current 
//location 'hloc' for a symbol other than 'key'

int n, find_loc = -1;

for( n=hloc+1 ; n<MAX ; n++) {
if(tape[tnum][n] != key) {
find_loc=n;
break;
}
}
if(find_loc == -1) {
printf("not found error!!\n");
exit(0);
}

return find_loc;
}

int left_find(int tnum, int hloc, char key) {
//search its tape 'tnum' to the left of the current 
//location 'hloc' for a symbol 'key'

int n, find_loc = -1;

for( n=hloc-1 ; n>=0 ; n--) {
if(tape[tnum][n] == key) {
find_loc=n;
break;
}
}

if(find_loc == -1) {
fprintf(fp,"right not found error!! \n");
exit(0);
}

return find_loc;
}

int left_not_find(int tnum, int hloc, char key) {
//search its tape 'tnum' to the right of the current 
//location 'hloc' for a symbol other than 'key'

int n, find_loc = -1;

for( n=hloc-1 ; n>=0 ; n--) {
if(tape[tnum][n] != key) {
find_loc=n;
break;
}
}

if(find_loc == -1) {
fprintf(fp,"left not found error!!\n");
exit(0);
}

return find_loc;
}

int shift_right(int tnum, int hloc) {
//shifts the string of nonblank symbols found at
//the left of the current cell one cell to the right.
char val1,val2;

tape[tnum][hloc]='d';
hloc--;

if(tape[tnum][hloc] == 'd') {
hloc++;
return hloc;
}
val1=tape[tnum][hloc];

while(1) {
hloc--;
if(hloc <0 ) {
hloc++;
tape[tnum][hloc]='d';
hloc=right_find(tnum,hloc,'d');
tape[tnum][hloc]=val1;
return hloc;
}

if(tape[tnum][hloc]=='d'){
hloc++;
tape[tnum][hloc]='d';
hloc=right_find(tnum,hloc,'d');
tape[tnum][hloc]=val1;
return hloc;
}

val2=tape[tnum][hloc];
hloc++;
tape[tnum][hloc]=val2;
hloc--;
}
}

int shift_left(int tnum, int hloc) {
//shifts the string of nonblank symbols found at
//the right of the current cell one cell to the left.

char val1,val2;

tape[tnum][hloc]='d';
hloc++;

if(tape[tnum][hloc] == 'd') {
hloc--;
return hloc;
}
val1=tape[tnum][hloc];

while(1) {
hloc++;
if(hloc==MAX ) {
hloc--;
tape[tnum][hloc]='d';
hloc=left_find(tnum,hloc,'d');
tape[tnum][hloc]=val1;
return hloc;
}

if(tape[tnum][hloc]=='d'){
hloc--;
tape[tnum][hloc]='d';
hloc=left_find(tnum,hloc,'d');
tape[tnum][hloc]=val1;
return hloc;
}

val2=tape[tnum][hloc];
hloc--;
tape[tnum][hloc]=val2;
hloc++;
}
}

int print_result(void) {
//prints current tapes, header's location
int m,n;
fprintf(fp,"\nloc0=%d loc1=%d loc2=%d\n",loc0,loc1,loc2);
for(m=0; m<3 ; m++) {
for(n=0; n<MAX ; n++) {
fprintf(fp,"%c",tape[m][n]);
}
fprintf(fp,"\n");
}
return 0;
}