Problem 5 - Turing Machine

Give a Turing machine program that accepts a language

and analyze its time and space complexity.

• We consider the Turing machine such that:

  1.

  the finite set of state is ;

  2.

  the finite set of allowable tape symbols is ;

  3.

  is the blank;

  4.

  the set of input symbols is ;

  5.

  the next move function is whose definition is given below;

  6.

  is the initial state;

  7.

  and is the final state.

  Informally, we see that state is entered initially. $M$ changes the 0 to an $X$, moves right and enters state $q_1$. As long as $M$ in state $q_1$ reads 0's or $Y$'s, it goes right and enters $q_2$ when seeing a first 1. Before moving right, it changes this 1 to a $Y$. In state $q_2$, $M$ checks if it reads a 1 and, if it is the case, it changes the 1 to a $Y$, moves left and enters state . In state , $M$ will go left as long as it reads $Y$'s or 0's. It changes the first $X$ encounters into an $X$, moves right and enters state , so that, in that state, the 0 can be changed into an $X$ and a whole cycle is repeated. If after changing a 1 to a $Y$, $M$ finds no more 0's, then it checks that no more 1's remain and accepts if there are none. Other cases leads the machine to halt without accepting.

• If for every input word of length $n$, $M$ scans at most cells, then $M$ is said to be a space-bounded Turing machine, or of space complexity . If for every input word of length $n$, $M$ makes at most moves before halting, then $M$ is said to be a time-bounded Turing machine, or of time complexity .

  Our Turing machine needs to scan only the $n$ cells that initially contain the input word. $M$ is therefore of space complexity $n$.

  Let us assume the input is . During the first cycle, $M$ needs to scan one cell to change a 0 to an $X$, cells to find the first 1, 2 cells to change two 1's to two $Y$'s and cells to go back. During the $i$th cycle, it scans cells. After cycles, $M$ notes all the 0's have been exhausted, and just needs to check that 1's remain on the right (plus one cell to be sure it is a blank). The total number of scanned cells is:

  Which the time complexity of $M$.