Chris Pollett >
Students > [Bio] [Del1] [Del2] [Del3] [Del4] |
Del1: A Multiplication Machine1. Description of Deliverable #1: Turing MachineThe 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 BasicsViewed 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 machineThis 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:
The program repeats the above steps until the calculation ends. 1.3 Sample outputPlease 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"); } |