Sign up ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|cite|improve this question
What does this have to do with formal systems? –  Carl Mummert Mar 18 '11 at 17:38
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? –  Carl Mummert Mar 18 '11 at 17:40
@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$ :( –  user8380 Mar 18 '11 at 17:50
You might want to ask this in –  uncle brad Mar 18 '11 at 20:10

2 Answers 2

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.

share|cite|improve this answer
up vote 0 down vote accepted

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 ;)

share|cite|improve this answer
-_-'. i wonder if i could squeeze something from the GCD thing.. dzieki :) –  user8380 Mar 18 '11 at 21:40
This does not actually construct a Turing machine. –  Carl Mummert Mar 18 '11 at 21:51
@Carl: How so? The method works, don't you think? –  user8380 Mar 18 '11 at 22:03

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.