Component selected is Turing machine

BASIC STRUCTURE OF TURING MACHINE

Turing machine:

•               The input tape is also used as the output tape.

•               The read/write head can move left and right, and thus a tape symbol may be read/written more than once.

•               The output string is left justified, and the read/write head is placed on first square.

Input = a1 a2×××am
	!			a1	a2	a3	×××  a j	×××	am
			read-write head
Control

Output = c1 c2×××cm
	!			c1	c2	c3	×××  c j	×××	×××	cn
			read-write head
control

•               it is possible that the tape was used beyond the the last ouput sym-bol c_n.

•               n may be < m, = m, or > m.

                                                                                                             

A TM FOR ERASING THE INPUT

•             Input alphabet = {a, b}

•              The tape symbol b is just like ’B’ = blank except that it is written by the TM.

Input = aaba:	!	a   a   b   a   B  B  B	×××
		Start
Output = l:	!	b   b   b   b   b   B  B	×××
		halt

	!		a	a	b	a	B	B	×××
			start
	!		a	a	b	a	B	B	×××
			erase
after many erasing steps	!		b  b  b  b  B  B						×××
			erase
	!		b  b  b  b  b  B						×××
			go-left
	!		b  b  b  b  b  B						×××
			go-left
	!		b  b  b  b  b  B						×××
			almost-done
	!		b  b  b  b  b  B						×××
			halt

2.3

		A FINITE-STATE DIAGRAM FOR THE ERASING -TM
		a/b/R,		b/b/L
		b/b/R
start	!/!/R	erase	B/b/L	go-left	!/!/R	almost-	b/b/L	halt
						done

Trasition-label:

Tape-symbol-read/Tape-symbol-written/Head-move-direction

				2.4
	A TM FOR RIGHT-SHIFTING
	A NON-EMPTY BINARY STRING
	Input:	1011	(no starting ’!’)
	Output:	!1011	(’!’ added to the left)

Key ideas:

·        Read  an  input  symbol  a _j ,  move  to  the  right,  write  that  a _j (in position  j  1), and at the same time remember the original symbol a _j1  in that position.  Repeat this for all symbols in the input. (Write ’!’ at the start-position in the start-state, when there is no previous input symbol).

·        When ’blank’ is read, drop the last symbol remembered (a_n), and then keep moving to the left to the first position.

Configuration: (x. y : state)

•               x = the tape content to the left of the read/write head

•               y = the remaining non-blank part of the tape

•              The state m0 (m1) means the most recent bit remembered from the position on the left is 0 (resp., 1).

•             The first symbol of y is the current symbol being read.

								x = a1 a2×××a j-1
a1	a2	×××	a j-1	a j	×××	ak
								y = a j a j+1×××ak	or B
		read/write head

2.5

PART OF THE

MOVE SEQUENCE FOR INPUT 1011

1

0

1

1

.1011  :  start

start

!

0

1

1

!.011  :  m1

m1

!

1

1

1

!1.11  :  m0

m0

!

1

0

1

!10.1  :  m1

m1

!         1   0   1   B !101.B   :  m1

m1

!         1   0   1   1 !10.11  :  go-left

go-left

"halt" = The final-state of a TM.

2.6

	THE STATE-DIAGRAM FOR Tright-shift
	0/0/R

s ₀   = start

s ₁   = go-left

s ₁   = almost-done

H  = halt

Source Code: simulate_turing_machine.c

#include <stdio.h>

#include <string.h>

#include <ctype.h>

#include "simulate_turing_machine.h"

struct turing_machine_state {

    int control_state;

    int head_position;

    int tape_size;

    symbol* tape;

}; /* This structure need not be public */

struct turing_machine_state

create_initial_state(int initial_control_state, int input_string_length, symbol* input_string) {

    struct turing_machine_state state;

    state.control_state = initial_control_state;

    state.head_position = 0; /* Initially at left end */

    state.tape_size = input_string_length;

    state.tape = malloc(sizeof(symbol)*input_string_length);

    if (state.tape == NULL) {

        printf("Out of memory");

        exit(-1);

    }

    memmove(state.tape, input_string, sizeof(symbol)*input_string_length);

    return state;

}

void free_state(struct turing_machine_state* state) {

    free(state->tape);

}

void update_state(struct turing_machine_state* state, int new_control_state,

                  enum direction dir, char write_symbol, char blank_symbol)

{

    state->control_state = new_control_state;

    state->tape[state->head_position] = write_symbol;

    if (dir == DIR_LEFT && state->head_position > 0) {

        state->head_position--;

    } else { /* dir == DIR_RIGHT */

        state->head_position++;

    }

    if (state->head_position >= state->tape_size) {

        int i, old_tape_size = state->tape_size;

        symbol* new_tape = realloc(state->tape, old_tape_size*2 + 10);

        if (new_tape == NULL) {

            printf("Out of memory");

            exit(-1);

        }

        state->tape = new_tape;

        state->tape_size *= 2;

        for (i=old_tape_size; i < state->tape_size; i++) {

            state->tape[i] = blank_symbol;

        }

    }

}

void trace_state(struct turing_machine_state* state, symbol blank_symbol) {

    int i;

    for(i=0; i < TRACE_TAPE_CHARS && i < state->head_position; i++) {

        printf(" ");

    }

    if (i < TRACE_TAPE_CHARS) {

        printf("v"); /* points down */

    }

    printf("\n");

    for(i=0; i < TRACE_TAPE_CHARS; i++) {

        printf("%c", i < state->tape_size ? state->tape[i] : blank_symbol);

    }

    printf("\n");

}

int is_in_int_list(int value, int list_size, int list[]) {

    int i;

    for(i=0; i<list_size; i++) {

        if (list[i] == value) {

            return 1;

        }

    }

    return 0;

}

void simulate(struct turing_machine machine, int input_string_length, symbol* input_string) {

    struct turing_machine_state state =

        create_initial_state(machine.initial_control_state, input_string_length, input_string);

    trace_state(&state, machine.blank_symbol);

    while (!is_in_int_list(state.control_state, machine.num_accepting_states,

                           machine.accepting_states)) {

        struct transition_result next =

            machine.transition_table[state.control_state]

                                    [(int)state.tape[state.head_position]];

        update_state(&state, next.control_state, next.dir,

                     next.write_symbol, machine.blank_symbol);

        trace_state(&state, machine.blank_symbol);

    }

    free_state(&state);

}

Source code: simulate_turing_machine.h

#define _SIMULATE_TURING_MACHINE_H_

#define TAPE_ALPHABET_SIZE 256

#define TRACE_TAPE_CHARS   78

typedef char symbol;

enum direction { DIR_LEFT, DIR_RIGHT };

struct transition_result {

    int control_state;

    symbol write_symbol;

    enum direction dir;

};

struct turing_machine {

    int initial_control_state;

    char blank_symbol;

    int num_accepting_states;

    int* accepting_states;   

    struct transition_result** transition_table;

};

void simulate(struct turing_machine machine, int input_string_length, symbol* input_string);

#endif /* #ifndef _SIMULATE_TURING_MACHINE_H_ */

Source code: test_driver.c

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include "simulate_turing_machine.h"

struct turing_machine get_example_turing_machine(void) {

    struct turing_machine machine;

    int i, j;

    machine.initial_control_state = 0;

    machine.blank_symbol = '#';

    machine.num_accepting_states = 1;

    machine.accepting_states = malloc(sizeof(int)*machine.num_accepting_states);

    if (machine.accepting_states == NULL) {

        printf("Out of memory");

        exit(-1);

    }

    machine.accepting_states[0] = 5;

    #define NUM_STATES 7

    #define STATE_INVALID 6

    machine.transition_table = malloc(sizeof(struct transition_result *) * NUM_STATES);

    if (machine.transition_table == NULL) {

        printf("Out of memory");

        exit(-1);

    }

    for (i=0; i<NUM_STATES; i++) {

        machine.transition_table[i] =

            malloc(sizeof(struct transition_result)*TAPE_ALPHABET_SIZE);

        if (machine.transition_table[i] == NULL) {

            printf("Out of memory");

            exit(-1);

        }

        for (j=0; j<TAPE_ALPHABET_SIZE; j++) {

            machine.transition_table[i][j].control_state = STATE_INVALID;

            machine.transition_table[i][j].write_symbol = machine.blank_symbol;

            machine.transition_table[i][j].dir = DIR_LEFT;

        }

    }

    machine.transition_table[0]['#'].control_state = 4;

    machine.transition_table[0]['#'].write_symbol  = '#';

    machine.transition_table[0]['#'].dir           = DIR_RIGHT;

    machine.transition_table[0]['a'].control_state = 1;

    machine.transition_table[0]['a'].write_symbol  = '#';

    machine.transition_table[0]['a'].dir           = DIR_RIGHT;

    machine.transition_table[4]['#'].control_state = 5;

    machine.transition_table[4]['#'].write_symbol  = '#';

    machine.transition_table[4]['#'].dir           = DIR_RIGHT;

    machine.transition_table[1]['a'].control_state = 1;

    machine.transition_table[1]['a'].write_symbol  = 'a';

    machine.transition_table[1]['a'].dir           = DIR_RIGHT;

    machine.transition_table[1]['b'].control_state = 1;

    machine.transition_table[1]['b'].write_symbol  = 'b';

    machine.transition_table[1]['b'].dir           = DIR_RIGHT;

    machine.transition_table[1]['#'].control_state = 2;

    machine.transition_table[1]['#'].write_symbol  = '#';

    machine.transition_table[1]['#'].dir           = DIR_LEFT;

    machine.transition_table[2]['b'].control_state = 3;

    machine.transition_table[2]['b'].write_symbol  = '#';

    machine.transition_table[2]['b'].dir           = DIR_LEFT;

    machine.transition_table[3]['a'].control_state = 3;

    machine.transition_table[3]['a'].write_symbol  = 'a';

    machine.transition_table[3]['a'].dir           = DIR_LEFT;

    machine.transition_table[3]['b'].control_state = 3;

    machine.transition_table[3]['b'].write_symbol  = 'b';

    machine.transition_table[3]['b'].dir           = DIR_LEFT;

    machine.transition_table[3]['#'].control_state = 0;

    machine.transition_table[3]['#'].write_symbol  = '#';

    machine.transition_table[3]['#'].dir           = DIR_RIGHT;

    return machine;

}  

int main(int argc, char* argv[]) {

    if (argc < 1 + 1) {

        printf("Syntax: simulate_turing_machine <input string>\n");

        return -1;

    }

    simulate(get_example_turing_machine(), strlen(argv[1]), argv[1]);

    return 0;

}