2
$\begingroup$

Given integers $a, b, c$ construct a single-tape Turing machine recognizing the language $\{w \in \{0,1\}^{*}: a*\#_{0}w+b*\#_{1}w+c=0\}$ in time $O(n*logn)$, where $n=|w|$. $\#_{x}w$ denotes the number of occurrences of the symbol $x$ in $w$.

Updating counters somewhere on the tape would result in $O(n^2)$ complexity. I suspect extended euclidean algorithm has to be used during construction of this machine.

  • 0
    You might wa$n$t to ask this i$n$ http://cstheory.stackexcha$n$ge.com/2011-03-18

2 Answers 2

0

Make counter using bigger alphabet. In every step move your counter closer to data. So it might look like #•••{counter}{data}B in average step. Adding a or b is O(log n) as well as moving counter one field to the right.

If you want to have counter in one place without moving it every step solution will be O(n^2) like you said as you have to go back to counter every step and it costs O(n) then.

Pozdro ;)

  • 0
    @Carl: How so? The method works, don't you think?2011-03-18
0

I don't think that O(n * logn) is your friend here, since this is basically a counting problem. If the values for a, b and c result in a finite number of words in the language then this is probably possible; the counting can be accomplished with a (potentially large, but finite) number of states. But if the values for a, b and c result in an infinite number of words in the language then the counting will need to be done by traversing w multiple times.