Thread: Non-deterministic Turing machine simulator

  1. #1
    Registered User
    Join Date
    Jan 2019
    Posts
    5

    Non-deterministic Turing machine simulator

    So I've done for college purposes (months ago) this code that implements a non deterministic TM simulator.
    This is the first "difficult" program I had to do, and I was wondering: how is the code itself, is it understandable and well written? And does the git repo explain enough or not so much?

    Git link:
    GitHub - 0novanta/nondeterministic-turing-machine-simulator: This program implements a nondeterministic Turing machine simulator in C.

    Thanks.

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Some initial thoughts.

    1. 600 lines and only two functions.
    You need a lot more functions if you want something easy to read and be maintainable.

    2. There is no need to cast the return result of malloc/calloc/realloc.

    3. Too many magic numbers, like for(t=0; t<75; t++) and newArr[b-48]=newNode;

    4. This is a bug.
    > arr = (node_t***) realloc(arr, (a+1)*sizeof(node_t**));
    If realloc fails, you just leaked your only pointer to memory you still own.
    Code:
    void *temp = realloc(arr, (a+1)*sizeof(node_t**));
    if ( temp != NULL ) {
       // got the new memory
       arr = temp;
    } else {
      // do something with arr
    }
    Also, expanding by +1 each time can be very expensive in the long run.
    If you really have no idea what the upper limit will be, it's generally best to double the amount each time, and track how many free slots you have in the current block.

    5. fgets(s, 30, stdin);
    More magic numbers. Use sizeof(s) instead, and the code is always right if you change array size.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Registered User
    Join Date
    Jan 2019
    Posts
    5
    1. I ended up with only two functions because there were memory usage e time of execution limits, given that the TM would simulates thousands (or more) of different possibilities, I thought that with just two functions the program wouldn't spend much time to call other functions and would not spend memory on the stack. But I get that with more functions it would be more readable.

    2.Could you explain further?

    3.I get this, should I use defines?

    4.Realloc would fail if there is not enough memory?

  4. #4
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    > 1. I ended up with only two functions
    1. The function call overhead is minimal on modern machines.
    2. Your compiler might just inline small functions for you. You benefit from both cleaner code and faster performance.
    3. //QUEUE INIZIALIZATION
    Your inline for performance argument fails for things you only call once anyway.
    4. The aforementioned realloc(+1) will burn a hell of a lot of time invisibly when it has to physically move the block to another location.

    > I thought that with just two functions the program wouldn't spend much time to call other functions and would not spend memory on the stack
    Thinking about performance issues in advance of actually MEASURING performance issues leads to such erroneous conclusions.

    > 2.Could you explain further?
    FAQ > Casting malloc - Cprogramming.com

    > 3.I get this, should I use defines?
    Yes.

    > 4.Realloc would fail if there is not enough memory?
    Yes.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  5. #5
    Registered User
    Join Date
    Jan 2019
    Posts
    5
    Ok ,thank you , I'll keep these suggestions in mind.
    I'm curious about performances here, so this program passed every test and got me the highest grade, however I'm sure that there is a lot more to do about:
    -discovering loops and jumping them
    -managing the queue where I stack all the possible roads that the computation may take
    -storing the instructions from the .txt file to some sort of array structure

  6. #6
    Registered User
    Join Date
    Dec 2017
    Posts
    1,626
    Here is an example of how you might write your code with better structure and naming. I've only written the first part, reading in the transition table. I'm not saying it's perfect, but I hope you agree that it is much more readable.

    Note that this code makes the mistake that Salem pointed out in the use of realloc (saving the return value to the same pointer used as input). However, since it exits if the return value is NULL, it doesn't matter in this case as the OS will clean everything up. In general you should do as Salem has described.

    It also takes advantage of realloc acting like malloc if the input pointer (first parameter) is NULL.

    BTW, what language is "letto" and what does it mean? Google translate says it's Italian and means "bed"!
    Code:
    #include <stdio.h>
    #include <stdlib.h>
     
    #define LOW_CHAR  '0'
    #define HIGH_CHAR 'z'
    #define NUM_CHARS (HIGH_CHAR - LOW_CHAR + 1)
     
    typedef struct Instruction Instruction;
    struct Instruction {
        Instruction *next;
        char outSym;
        char direction;
        int newState;
    };
    typedef struct Instruction ***Table;
     
    Table read_transition_table(int *numStates);
    Table extend_table(Table table, int state, int *numStates);
    Instruction **new_table_row();
    Instruction *new_instruction(char outSym, char direction, int newState);
    void print_transition_table(Table table, int numStates);
    void free_transition_table(Table table, int numStates);
    void skip_line();
     
    int main() {
        int numStates = 0;
        skip_line();
        Table table = read_transition_table(&numStates);
        print_transition_table(table, numStates);
        free_transition_table(table, numStates);
        return 0;
    }
     
    void skip_line() {
        for (char ch; (ch = getchar()) != \n' && ch != EOF) ;
    }
     
    Table read_transition_table(int *numStates) {
        *numStates = 0;
        Table table = NULL;
        int state, newState;
        char inSym, outSym, direction;
        while (scanf("%d %c %c %c %d", &state, &inSym, &outSym, &direction,
                                       &newState) == 5) {
            if (state >= *numStates) table = extend_table(table, state, numStates);
            if (!table[state]) table[state] = new_table_row();
            Instruction *inst = new_instruction(outSym, direction, newState);
            inst->next = table[state][inSym - LOW_CHAR];
            table[state][inSym - LOW_CHAR] = inst;
        }
        return table;
    }
     
    Table extend_table(Table table, int state, int *numStates) {
        table = realloc(table, (state + 1) * sizeof *table);
        if (!table) {
            perror("extend_table");
            exit(EXIT_FAILURE);
        }
        while (*numStates <= state)
            table[(*numStates)++] = NULL;
        return table;
    }
     
    Instruction **new_table_row() {
        Instruction **tableRow = malloc(NUM_CHARS * sizeof *tableRow);
        if (!tableRow) {
            perror("new_table_row");
            exit(EXIT_FAILURE);
        }
        for (int i = 0; i < NUM_CHARS; i++)
            tableRow[i] = NULL;
        return tableRow;
    }
     
    Instruction *new_instruction(char outSym, char direction, int newState) {
        Instruction *inst = malloc(sizeof *inst);
        if (!inst) {
            perror("new_instruction");
            exit(EXIT_FAILURE);
        }
        inst->outSym = outSym;
        inst->direction = direction;
        inst->newState = newState;
        inst->next = NULL;
        return inst;
    }
     
    void print_transition_table(Table table, int numStates) {
        for (int row = 0; row < numStates; ++row)
            if (table[row])
                for (int col = 0; col < NUM_CHARS; ++col)
                    for (Instruction *p = table[row][col]; p; p = p->next)
                        printf("%d %c %c %c %d\n", row, col + LOW_CHAR,
                               p->outSym, p->direction, p->newState);
    }
     
    void free_transition_table(Table table, int numStates) {
        for (int row = 0; row < numStates; ++row)
            if (table[row]) {
                for (int col = 0; col < NUM_CHARS; ++col)
                    for (Instruction *p = table[row][col]; p; ) {
                        Instruction *next = p->next;
                        free(p);
                        p = next;
                    }
                free(table[row]);
            }
        free(table);
    }
    Last edited by john.c; 01-15-2019 at 01:28 PM.
    A little inaccuracy saves tons of explanation. - H.H. Munro

  7. #7
    Registered User
    Join Date
    Jan 2019
    Posts
    5
    Yep that's way better. "letto" means "read" as in "I've read a book". (it also means bed)
    What does 'perror' do? Just show an error message?
    Anyway, I though I did a good job but this stuff is from another world!
    Thanks.

  8. #8
    Registered User
    Join Date
    Dec 2017
    Posts
    1,626
    About your code, you obviously did a good job since it seems to work properly. It just doesn't have a lot of structure and is somewhat repetitive. As for my rewrite, it's mostly based on analyzing the task into functions. It's kind of an art so it takes a while to get good at it.

    perror prints an error message based on the current value of the library variable "errno", which is set to an error code by most library functions when they encounter an error.

    And note that I made a mistake in the above program in the skip_line function (I must've edited it at the last moment without testing it). It should be:
    Code:
    void skip_line() {
        for (int ch; (ch = getchar()) != '\n' && ch != EOF; ) ;
    }
    Here's a quick rewrite that stores the size of the table along with the table in a struct (TransitionTable). That way they don't have to be passed around separately. I also added reading in the accept states.
    Code:
    #include <stdio.h>
    #include <stdlib.h>
     
    #define LOW_CHAR  '0'
    #define HIGH_CHAR 'z'
    #define NUM_CHARS (HIGH_CHAR - LOW_CHAR + 1)
     
    typedef struct Instruction Instruction;
    struct Instruction {
        Instruction *next;
        char outSym;
        char direction;
        int newState;
    };
     
    typedef struct TransitionTable TransitionTable;
    struct TransitionTable {
        int size;
        Instruction ***table;
    };
     
    typedef struct AcceptStates AcceptStates;
    struct AcceptStates {
        int size;
        int *states;
    };
     
    TransitionTable *read_transition_table();
    void extend_table(TransitionTable *tt, int state);
    Instruction **new_table_row();
    Instruction *new_instruction(char outSym, char direction, int newState);
    void print_transition_table(TransitionTable *tt);
    void free_transition_table(TransitionTable *tt);
    AcceptStates *read_accept_states();
    void print_accept_states(AcceptStates *as);
    void free_accept_states(AcceptStates *as);
    void skip_line();
     
    int main() {
        TransitionTable *tt = read_transition_table();
        AcceptStates *as = read_accept_states();
     
        print_transition_table(tt);
        print_accept_states(as);
     
        free_accept_states(as);
        free_transition_table(tt);
        return 0;
    }
     
    void skip_line() {
        for (int ch; (ch = getchar()) != '\n' && ch != EOF; ) ;
    }
     
    AcceptStates *read_accept_states() {
        AcceptStates *as = malloc(sizeof *as);
        as->size = 0;
        as->states = NULL;
        skip_line();
        for (int acceptState; scanf("%d", &acceptState) == 1; ) {
            if (acceptState >= as->size) {
                as->states = realloc(as->states,
                                 (acceptState + 1) * sizeof *as->states);
                if (!as->states) {
                    perror("read_accept_states");
                    exit(EXIT_FAILURE);
                }
                while (as->size < acceptState)
                    as->states[as->size++] = 2;
                ++as->size;
            }
            as->states[acceptState] = 1;
        }
        return as;
    }
     
    void print_accept_states(AcceptStates *as) {
        for (int i = 0; i < as->size; ++i)
            printf("%2d: %2d\n", i, as->states[i]);
    }
     
    void free_accept_states(AcceptStates *as) {
        free(as->states);
        free(as);
    }
     
    TransitionTable *read_transition_table() {
        TransitionTable *tt = malloc(sizeof *tt);
        tt->size = 0;
        tt->table = NULL;
        int state, newState;
        char inSym, outSym, direction;
        skip_line();
        while (scanf("%d %c %c %c %d", &state, &inSym, &outSym, &direction,
                                       &newState) == 5) {
            if (state >= tt->size)
                extend_table(tt, state);
            if (!tt->table[state])
                tt->table[state] = new_table_row();
            Instruction *inst = new_instruction(outSym, direction, newState);
            inst->next = tt->table[state][inSym - LOW_CHAR];
            tt->table[state][inSym - LOW_CHAR] = inst;
        }
        return tt;
    }
     
    void extend_table(TransitionTable *tt, int state) {
        tt->table = realloc(tt->table, (state + 1) * sizeof *tt->table);
        if (!tt->table) {
            perror("extend_table");
            exit(EXIT_FAILURE);
        }
        while (tt->size <= state)
            tt->table[tt->size++] = NULL;
    }
     
    Instruction **new_table_row() {
        Instruction **tableRow = malloc(NUM_CHARS * sizeof *tableRow);
        if (!tableRow) {
            perror("new_table_row");
            exit(EXIT_FAILURE);
        }
        for (int i = 0; i < NUM_CHARS; i++)
            tableRow[i] = NULL;
        return tableRow;
    }
     
    Instruction *new_instruction(char outSym, char direction, int newState) {
        Instruction *inst = malloc(sizeof *inst);
        if (!inst) {
            perror("new_instruction");
            exit(EXIT_FAILURE);
        }
        inst->outSym = outSym;
        inst->direction = direction;
        inst->newState = newState;
        inst->next = NULL;
        return inst;
    }
     
    void print_transition_table(TransitionTable *tt) {
        for (int row = 0; row < tt->size; ++row)
            if (tt->table[row])
                for (int col = 0; col < NUM_CHARS; ++col)
                    for (Instruction *p = tt->table[row][col]; p; p = p->next)
                        printf("%2d %c %c %c %2d\n", row, col + LOW_CHAR,
                               p->outSym, p->direction, p->newState);
    }
     
    void free_transition_table(TransitionTable *tt) {
        for (int row = 0; row < tt->size; ++row)
            if (tt->table[row]) {
                for (int col = 0; col < NUM_CHARS; ++col)
                    for (Instruction *p = tt->table[row][col]; p; ) {
                        Instruction *next = p->next;
                        free(p);
                        p = next;
                    }
                free(tt->table[row]);
            }
        free(tt->table);
        free(tt);
    }
    Last edited by Salem; 01-15-2019 at 11:33 PM. Reason: typos fixed at request
    A little inaccuracy saves tons of explanation. - H.H. Munro

  9. #9
    Registered User
    Join Date
    Jan 2019
    Posts
    5
    Thank you!
    I was also interested in knowing what this could be useful to.
    Other than a Turing machine (that doesn't actually do something), could be modified to do something else?
    For example, could this be some sort of primitive scheduler?

  10. #10
    Registered User
    Join Date
    Dec 2017
    Posts
    1,626
    Absolutely it could be modified to do something else. It's basically just building a dynamically-sized table. That could be useful for a lot of things.
    A little inaccuracy saves tons of explanation. - H.H. Munro

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 4
    Last Post: 03-17-2014, 01:59 PM
  2. C++ Turing machine
    By Dante Wingates in forum General Discussions
    Replies: 5
    Last Post: 07-26-2010, 01:47 AM
  3. Turing Machine
    By Brad C in forum Tech Board
    Replies: 2
    Last Post: 08-05-2005, 08:22 PM
  4. Machine simulator
    By datainjector in forum C Programming
    Replies: 1
    Last Post: 11-05-2002, 02:15 PM
  5. IDEA: Turing Machine
    By ygfperson in forum Contests Board
    Replies: 0
    Last Post: 08-12-2002, 11:08 PM

Tags for this Thread