1
$\begingroup$

I was tasked with finding a way to decide the language $A=\{0^k1^k \mid k\ge 0\}$ in $O(n\log n)$ time, and then to implement it on a deterministic Turing machine with one tape. Additionally, I was asked to check if it is possible to reduce the time from $O(n\log n)$ to $O(n)$ if using a determinstic Turing machine with two tapes (instead of one).

I am really stuck on it and don't know how to implement it. This is what I have so far:

First, we check that in the input word there are no zeros right of the ones. Then, for each zero in the input, we increase a binary counter and for the ones we do the same, creating a binary counter and increasing by one. if the counters are equal, accept, if not, reject. But i don't know how to implement it on a Turing machine, aside from the problem that if the counters of one and zero are far from the writing-reading head, then reaching it would take a lot of steps (time).

Regarding improving it to $O(n)$ time using a deterministic Turing machine with two heads: we go over with one head along the input string until we meet the first 1. then we count the number of one with one tape, and with the other the number of 0's. then we compare and accept if they are equal. So it is basically $k$ steps until the first 1, creating the counter, and counting each 1 $n$ times, then creating a counter with the second tape and comparing to the number of 0's in the beginning until the first one. So the total is $O(n)$. But how do I implement it on a Turing machine?

$\endgroup$
2
$\begingroup$

If you are allowed an auxiliary tape, then the algorithm is very simple:

  • Scan to the end of the input, while checking that the input belongs to $0^*1^*$.
  • Copy the input in reverse to the auxiliary tape, switching 0s and 1s.
  • Check that both tapes contain the same word.

If the input is $0^a 1^b$ then the second tape will contain $0^b 1^a$, so the algorithm will accept if and only if $a = b$. It clearly runs in linear time.

If you only have one tape, then the algorithm is more subtle. We scan the input from left-to-right, maintaining a counter just left of the current symbol being scanned. At each step, we do as follows:

  • Read the next symbol $\sigma$ and remember it.
  • Copy the counter one step to the right; this step takes $O(\log n)$ time.
  • Either increment the counter (if $\sigma = 0$) or decrement it (if $\sigma = 1$).

At the end, we accept if the input belongs to $0^*1^*$, and additionally the counter has the value zero.

Using crossing sequences, you should be able to show a matching $\Omega(n \log n)$ lower bound for one-tape Turing machines. The idea is to consider the set of inputs $0^m1^m,\ldots,0^{2m}1^{2m}$, and to consider the states that the Turing machine is when it crosses the window between the $m$th and $2m$th position. There must be $m+1$ different crossing sequences, hence there must exist a crossing sequence of length $\log m$, which corresponds to a running time of $\Omega(m\log m) = \Omega(n\log n)$.

$\endgroup$
  • $\begingroup$ thank you very much for your answer. my main question is: when implementing the turing machines based on the algorithm, will they remain the same or change? (the transition from algorithm to turing based implementation) $\endgroup$ – hps13 Apr 6 at 13:47
  • $\begingroup$ Hopefully the two will be closely related. $\endgroup$ – Yuval Filmus Apr 6 at 13:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.