Turing Machines

Question 1: Consider the following Turing Machine M which takes as input a string
. _ t
n p m and moves pm one cell to the left, producing output . t
n−1 p m ‘Cell Mover’ Turing Machine Simulator Input name: Cell Mover // Turing Machine takes input of the form: // >^{n}I^{m}
// where n,m > 1 and
// and produces output of the form
// >^{n-1}I^{m}. // Example: Given input >___IIII halts and returns >__IIII init: q0 accept: qAccept // scan over initial input in state q0 until we hit an I, // then go into shifting loop state. q0,I qloop,I,- q0,> q0,>,> q0,
q0, , > // Shifting loop state: loop through string moving it // one cell to the left. qloop, I writeI, I, < qloop,
qAccept,,- writeI, I connector, I, > writeI,
connector, I, >
connector, I
qloop, , > connector,
qloop, , > 1 Modify this Turing Machine so that it will take as input a string . t
n _p
m
and output the result of moving pm to the beginning of the tape, i.e.
. _p
m
and then halt.
Question 2: Design a Turing Machine that takes as input a finite sequence of As and
B’s, and outputs the result of rearranging them so that all the A’s are to the left of all
the B’s. (e.g., if the machine’s input in the sequence BABAA, it’s output should be the
sequence AAABB, and the if its input is the sequence ABBABB, its output should be
the sequence AABBBB).
Hint: You might find it useful in solving this problem to use an expanded alphabet that includes
additional characters other than just ., t, A, B.