Let $\Sigma := \{0,1,$#$\}$ be the input-alphabet and $L := \{bin(n)$#$w \in \Sigma^* | n \in \mathbb N \land w \in \{0,1\}^* \land |w| \le n\}$ the alphabet. $|w|$ means the length of the word $w$ and $bin(n)$ the binary representation of $n$.

I need to construct a 2-tape TM which has $O(n)$ complexity and accepts the words from $L$, i.e. the machine terminates in an acceptable state iff the input is contained in $L$ und for all other input words the machine terminates in a not acceptable state.

EDIT: I already constructed a 1-Tape TM which reduces a binary number by 1 and which is supposed to help me with solving this problem but I don't know how.

  • $\begingroup$ I don't see a question here. This is a question-and-answer site, so you need to articulate a question about your problem, not just copy the text of the problem statement. Also, what did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. $\endgroup$ – D.W. Jul 11 '17 at 23:13
  • $\begingroup$ If you already have constructed 1-Tape version, then you should be able to construct 2-Tape version too. The key is that the second tape must reduce the complexity to $O(n)$, since the head on the first tape scans input from left to right only once while you do all work on the second tape. $\endgroup$ – fade2black Jul 12 '17 at 0:02

Think over how to convert binary representation of $n$ into unary one using two tapes. The result should be stored on the second tape. For example, if $n=6$ then the unary representation could be $111111$. Then compare number of symbols of $w$ and number of $1$s of the unary representation of $n$. If the number of $1$s is less than or equal to $|w|$ then accept, otherwise reject.

Since number of bits in $bin(n)$ is no more than $log(n)$ number of unary bits is no more than $2^{log(n)} = n$, so writing down each bit on the tape should not take more than $O(n)$ time, and comparison $w$ with the unary $1$s also takes $O(n)$.

So you just need to design and algorithm for conversion from binary to unary representation of $bin(n)$ using two tapes that runs in $O(n)$ time.

| cite | improve this answer | |

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.