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.

  • 1
    What does this have to do with formal systems?2011-03-18
  • 0
    This sounds like a homework problem (particularly given the command-like phrasing of the first sentence). What have you tried? What book are you using? What theorems might you have at your disposal?2011-03-18
  • 0
    @Carl: Equation $a*x+b*y=c$ is solvable in integers iff $GCD(a,b)=d|c$, solutions are given by: $x=x_0+\frac{b}{d}*n, y=y_0+\frac{a}{d}*n$, where $n$ is an integer. It's possible to compute $\#_{0}w mod \frac{b}{d}$ in linear time on single-tape machine (this gives $x_0$ from the equations for solutions) but that is helpful only to reject a word: having $x_0$ and $y_0$, we can check if $a*x_0+b*y_0=c$ and reject the word if it's not the case, but if it is, then we still don't know if the equation holds, since we don't have $n$ :(2011-03-18
  • 0
    You might want to ask this in http://cstheory.stackexchange.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
    -_-'. i wonder if i could squeeze something from the GCD thing.. dzieki :)2011-03-18
  • 0
    This does not actually construct a Turing machine.2011-03-18
  • 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.