二进制加法图灵机的C语言实现

// Turing machines for computations.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 4 // the number of states
#define M 3 // the number of symbols
#define TAPE_SIZE 20 // the size of the tape
enum direction { LEFT, RIGHT, STAY };

/**
 * @brief encoding for binary addtion
 * 1. 4 states start:0 carry:1 back:2 halt:3
 * 2. 3 symbols 0->0 1->1 blank->2
 */
enum STATE { START, CARRY, BACK, HALT };
enum SYMBOL { SYMBOL_0, SYMBOL_1, BLANK };

int state_arr
    [N]; // state_arr[0] as start state, state_arr[N-2] as accept state, state_arr[N-1] as reject state

int symbol_arr[M]; // symbol_arr[0] as empty symbol

int tape[TAPE_SIZE];

typedef struct head {
    int location; // the location of the head
    int state_num; // the state of the head
} head_t;

typedef struct action {
    int head_state;
    int current_symbol;
    int next_symbol;
    enum direction dir;
    int next_state;
} action_t;

/**
 * @brief turing machine for binary addition
 * 1. start, blank->blank, RIGHT, carry
 * 2. carry, 1 -> 0, RIGHT, carry
 * 3. carry, blank->1, LEFT, back
 * 4. carry, 0->1, LEFT, back
 * 5. back, 0->0, LEFT, back
 * 6. back, blank->blank, halt
 */

action_t turing_machine(action_t act) {
    if (act.head_state == state_arr[START] && act.current_symbol == symbol_arr[BLANK]) {
        act.next_symbol = act.current_symbol;
        act.dir = RIGHT;
        act.next_state = state_arr[CARRY];
    } else if (act.head_state == state_arr[CARRY] && act.current_symbol == symbol_arr[SYMBOL_1]) {
        act.next_symbol = symbol_arr[SYMBOL_0];
        act.dir = RIGHT;
        act.next_state = act.head_state;
    } else if (act.head_state == state_arr[CARRY] && act.current_symbol == symbol_arr[BLANK]) {
        act.next_symbol = symbol_arr[SYMBOL_1];
        act.dir = LEFT;
        act.next_state = state_arr[BACK];
    } else if (act.head_state == state_arr[CARRY] && act.current_symbol == symbol_arr[SYMBOL_0]) {
        act.next_symbol = symbol_arr[SYMBOL_1];
        act.dir = LEFT;
        act.next_state = state_arr[BACK];
    } else if (act.head_state == state_arr[BACK] && act.current_symbol == symbol_arr[SYMBOL_0]) {
        act.next_symbol = act.current_symbol;
        act.dir = LEFT;
        act.next_state = state_arr[BACK];
    } else if (act.head_state == state_arr[BACK] && act.current_symbol == symbol_arr[BLANK]) {
        act.next_symbol = act.current_symbol;
        act.dir = STAY;
        act.next_state = state_arr[HALT];
    }
    return act;
}

void state_transition(char* s, int length) {
    // initiliaze the state array and symbol array
    for (int i = 0; i < N; i++) {
        state_arr[i] = i;
    }
    for (int i = 0; i < M; i++) {
        symbol_arr[i] = i;
    }
    // initialize the tape
    for (int i = 0; i < TAPE_SIZE; i++) {
        tape[i] = BLANK; // initialize all tape as blank
    }
    for (int i = 0; i < length; i++) {
        tape[i + 1] = s[i] - '0';
    }
    // initialize the head
    head_t h;
    h.location = 0;
    h.state_num = state_arr[START];
    // initialie the action
    action_t a;
    a.dir = STAY;
    // define the state transition
    while (h.state_num != 3) {
        a.head_state = h.state_num;
        a.current_symbol = tape[h.location];
        a = turing_machine(a);
        tape[h.location] = a.next_symbol;
        // update the head
        if (a.dir == RIGHT) {
            h.location += 1;
        } else if (a.dir == LEFT) {
            h.location -= 1;
        }
        h.state_num = a.next_state;
    }
    // print the added string
    for (int i = length; i >= 1; i--) {
        printf("%d", tape[i]);
    }
}

int main(void) {
    printf("Input the binary string: ");
    char* s = (char*)malloc(10 * sizeof(char));
    scanf("%s", s);
    // reverse the string, and enter it into turing machine
    int length = strlen(s);
    for (int i = 0; i < length / 2; i++) {
        char temp = s[length - 1 - i];
        s[length - 1 - i] = s[i];
        s[i] = temp;
    }
    state_transition(s, strlen(s));
    return 0;
}