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 cn.
•
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 j1 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 (an), 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
start
m1
m0
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 0 = start
s 1 = go-left
s 1 = 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;
}
