Del1: A Multiplication Machine

1. Description of Deliverable #1: Turing Machine

The purpose of my first deliverable is to write a C program which simulates a Turing Machine program which takes two numbers provided by user from the command line and outputs their product. Another purpose was to get practical experience with some concepts of the theory.

1.1 Turing Machine Basics

Viewed as a programming language, the Turing machine has a single data structure, and rather primitive one at that: A string of symbols. The head of the Turing machine is allowed to move to the left and right on the string, to write on the current position, and to branch depending on the value of the current symbol [Pap94]. Formally, a Turing machine is a quadruple M = (K, S, Delta, s). K is a finite set of states; s an element of K is the initial state. S is a finite set of symbols called the alphabet. S contains the special symbols which represents the blank and the first symbol respectively. Delta is a transition function which maps K x S to (K union {h, `yes', `no'}) x S x { L, R, -}.

Initially the state is s. The string is initialized to be all blank except the input over the input alphabet. Let X be the input of the Turing machine. Initially, the head is pointing to the first symbol of X. The machine takes every step according to the transition function, which can change the state, print a symbol, or move the head.

1.2 Simulation of the Turing machine

This C program simulates a Turing Machine which has two tapes. The first tape contains the two input numbers separated by a dollar sign, and the second tape is used to write the calculate result. The program takes two numbers which are provided by user from the command line, and translates them into unary format. Those unary numbers are saved in the first tape, separated by a dollar sign. At the end of the numbers, we put a `0'. to indicate the end of the input. For example, 3 * 2 will be represented in the tape as:

1 1 1 $ 1 1 0

This program simulates the Turing Machine calculating the products of the two numbers. The tape head reads the first symbol. If it is a dollar sign, that means one of numbers equals zero. If not, the tape head moves to the end of the input which signaled by a `0'., and moves to the left. It also means one of the numbers equals zero if the `0'. is followed immediately by a dollar sign. So the program give a blank output and terminates when meets those two conditions. If none of the two numbers is zero, the program begins to do the multiply. The steps are as follows:

1. Read the first `1', changes it into dollar sign.
2. Move to the end of the input which is a `0'.
3. Move to the left.
4. If reading a `1' write a `1' on the second tape. (output tape)
5. If it is a dollar sign, move to the left.
6. If it is a dollar sign again, the calculation ends.

The program repeats the above steps until the calculation ends.

1.3 Sample output

Please give two integers: 4, 6
The symbols on the input tape are:
1 1 1 1 $ 1 1 1 1 1 1 

The symbols on the output tape are (total number of '1' is 24):
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

My Code

/*************************************************************************************** 
* Project:         CS 297 Del 1
* Purpose:         Simulating a turing machine to calculate the product of
two integers 
* Date:			   09/17/2002
* Student:         Yan Yao
**************************************************************************************** 
*/

#include <stdio.h>
#include <malloc.h>

int unary_add(int number_1, int number_2);
int unary_multiply(int number_1, int number_2);
char* turing_input(int number_1, int number_2, int unary_count);
void print_input(int unary_count, char *tape_1);
int check_zero(char *tape_1); 
char* turing_output(int unary_count,char *tape_1);
void print_output(int unary_count,char *tape_2); 

int main()
{
	int x, y, flag, unary_input, unary_output;
	char *input_tape;
	char *output_tape;

	printf("Please give two integers:\n");
	scanf("%d %d", &x, &y);
	unary_input=unary_add(x, y);
	unary_output=unary_multiply(x,y);
	input_tape=turing_input(x,y, unary_input);
	print_input(unary_input,input_tape);
	flag = check_zero(input_tape);
	if(!flag)
		{
			output_tape
=turing_output(unary_output,input_tape);
			print_output(unary_output, output_tape);
		}
	return 0;
}

/*--------------------------------------------------------------------*/

int unary_add(int number_1, int number_2)
/* PURPOSE:      calculate the size of input numbers 
RECEIVES:   number_1, number_2 - two integers provided by user 
RETURNS:      an integer represents the size of the tape to save the input
numbers 
*/
{	
	int temp;
	temp= number_1 + number_2 ;
	return temp;
}

/*--------------------------------------------------------------------*/

int unary_multiply(int number_1, int number_2)
/* PURPOSE:      calculate the size of the output 
RECEIVES:   number_1, number_2 - two integers provided by user 
RETURNS:      the size needed to save the product of the two integers 
*/
{	
	int temp;
	temp= number_1 * number_2 ;
	return temp;
}

/*---------------------------------------------------------------------*/

char* turing_input(int number_1, int number_2, int unary_count)
/* PURPOSE:      save two integers on the first tape in unary format,
				 separated by a dollar sign.
RECEIVES:   number_1, number_2 - two integers, 
			unary_count - the size of the tape to save the two
integers in unary format 
RETURNS:      the char array represents the input tape. 
*/
{	
	int i,j;
	char *temp;

	temp = (char *)malloc(unary_count*sizeof(char));
	/*save first number in unary format*/
	for(i = 0; i < number_1; i++)
	{
		*(temp + i) = '1';

	}
	/*seperate symbol between the two numbers*/
	*(temp+i) = '$';
	i++;
	/*save second number in unary format*/
	for( j = i ; j < i + number_2; j++)
	{
		*(temp + j) = '1';
	}
	/*use '0' to signal the end of the input*/
	*(temp + j) = '0';
	return temp;

}

/*-------------------------------------------------------------------------*/

void print_input(int unary_count, char *tape_1)
/* PURPOSE:      print out the symbols on the input tape. 
RECEIVES:   unary_count - the number of symbols on the tape. 
			*tape_1 - a char pointer represents the input
tape.
*/
{
	int i;
	printf("The symbols on the input tape are:\n");
	for (i = 0; i <= unary_count; i++)
	{
	    printf("%c ", *(tape_1 + i));
	}
	printf ("\n");
}

/*-------------------------------------------------------------------------*/

int check_zero(char *tape_1)
/* PURPOSE:      checks if one of the two numbers equals zero
RECEIVES:   *tape_1 - a char pointer  
RETURNS:		zero, if none of the two numbers equals zero,
				one, if one of them equals zero.
*/
{	
	char *temp;
	int i = 0;
	int flag_zero = 0;
	/*Check if the first number equals zero*/
	if (tape_1[i] == '$')
	{
		printf("\nOutput tape is blank, multiply by 0. \n");
		flag_zero = 1;
	} 
	/* Check if the second number equals zero*/
	while (tape_1[i] != '0') i++;
	i--;
	if (tape_1[i] == '$')
	{
		printf("\nOutput tape is blank, multiply by 0.
\n");//second nubmer equals zero
		flag_zero = 1 ;
	}
	return flag_zero;
}

/*--------------------------------------------------------------------------------*/

char* turing_output(int unary_count,char *tape_1)
/* PURPOSE:      calcualte the product of two interger, write the answer
on the second tape.
RECEIVES:   unary_count - an integer represents size of the second tape,
			*tape_1 - a char pointer represents the input
numbers in unary format.
RETURNS:      a char pointer represents the product of two integers in
unary format. 
*/
{	
	int flag_end = 0;
	char *temp;
	int i, j = 0;	
	temp = (char *)malloc(unary_count*sizeof(char));
	while(!flag_end )
	{
		i = 0;
		/*find the first '1', then change it into '$'*/
		while (tape_1[i] != '1')
			i++;
		tape_1[i] = '$';
		/*find the end of the input symbols*/
		while (tape_1[i] != '0')
			i++;
		i--;
		/*write '1's to the output tape*/
		while (tape_1[i] != '$')
		{
			*(temp + j) = '1';
			j++;
			i--;
		}
		i--;
		/*the end of calculation*/
		if(tape_1[i] == '$')
			flag_end = 1;
	}
	return temp;
}

/*--------------------------------------------------------------------------------------*/

void print_output(int unary_count, char *tape_2)
/* PURPOSE:      print out the result on the second tape.
RECEIVES:   unary_count - an integer represents the size of the tape.
*/
{
	int i;
	printf("\nThe symbols on the output tape are (total number of '1'
is %d):\n", unary_count);
	for (i = 0; i < unary_count; i++)
	{
	    printf("%c ", *(tape_2 + i));
	}
	printf("\n");
}