2
$\begingroup$

How can I describe a Turing Machine recognizing the language $P=\{a^{2^n} | n \geq 0 \}$?

This Turing Machine is deterministic and uses two tapes, both bidirectional and R / W (read & write)

The computation should be done in linear time.

I've read Counters in Turing machines but it doesn't address my question. It can help but it doesn't answer my question. Turing Machines with $n$-tapes have the same computability that Turing Machines with one tape, but different behavior. Here I'm asking about the behavior of a two-tape TM.

My approach:

I think I may use the first tape as input tape and copy every character in the second tape. But I don't know how to keep track the exponential behavior.

$\endgroup$
  • $\begingroup$ I don't think that's possible, but well. $\endgroup$ – Raphael Oct 30 '17 at 13:41
2
$\begingroup$

A simple way is to scan the first (input) tape from left to right, and use the second tape to count the number of $a$s (you read) in binary format. Every time you read a single $a$ increase the counter (on the second tape) by $1$. When you reach the end of the input you check the second tape whether its content is of the form $100\dots000$. If it is then accept, otherwise reject.

$\endgroup$
  • $\begingroup$ I'm not convinced by your argument for the running time. Please elaborate why the binary counter on a TM (!) can count from $1$ to $k$ in $O(k)$ time. $\endgroup$ – Raphael Oct 30 '17 at 13:44
  • $\begingroup$ @Raphael Thanks for pointing that. Right, my bad. It is more than linear. I guess I omitted the part which moves the head to the MSB at the end of each increment. Secondly, it seems the question has been modified. Linear time requirement has been added. Originally it asked a TM recognizing this language. $\endgroup$ – fade2black Oct 30 '17 at 17:16
  • 1
    $\begingroup$ @fade2black: No, it's correct! Moving to the LSB simply doubles the running time: so you can binary count up to $k$ in $2k$ "steps" (plus some extra steps if at the LSB side you don't optimize the counter and the head moves on the blank). See an online example: morphett.info/turing/… $\endgroup$ – Vor Oct 31 '17 at 0:38
  • $\begingroup$ @Vor, Thanks. I came up with $O(n)$ too, a month ago, but I don't remember how. If I come up with a correct proof I'll edit my post and add a proof. In the meantime if you have a proof please edit the post. $\endgroup$ – fade2black Oct 31 '17 at 0:55
  • $\begingroup$ @Vor I tried this simulator for different input values $n$. The number of steps is something like $4n$. It's running time seems to be linear. $\endgroup$ – fade2black Oct 31 '17 at 1:08
2
$\begingroup$

To expand fade2black's answer; this is a simple proof by induction that the following TM

State    Symbol    Write  Move   Newstate
start    0         1      L      tolsb
start    1         0      R      carry

tolsb    _         _      R      start
tolsb    *         *      L      tolsb

carry    0         1      L      tolsb
carry    1         0      R      carry

performs a binary count from $0^n$ to $1^n$ in less than $2^{n} + n^3$ steps. Initially the head is placed on the LSB (which, we assume, is on the left part of the input string).

You can view a simulation of the Turing machine here.

We prove by induction that starting on the leftmost $0$, it counts up to $1^n$ and, at the end, the head is still placed on the LSB.

  • case $n = 1$:

Immediate

 _ 0    start
   ^ 
 _ 1    step 1
 ^
 _ 1    step 2
   ^
  • case $n$: suppose that it holds for $n-1$; i.e. it can count up from $0^{n-1}$ to $1^{n-1}$ in less than $2^{n-1} + (n-1)^3$ steps;

Then after less than $2^{n-1} + (n-1)^3$ steps the head is on LSB:

   1 2 3 ...   n 
 _ 1 1 1 ... 1 0 
   ^            

It will convert all $1$s to $0$ and propagate the carry to the MSB and convert the MSB to $1$ in $n$ steps:

   1 2 3 ...   n 
 _ 0 0 0 ... 0 1 
             ^            

Then it will go back to the LSB in $n$ steps

   1 2 3 ...   n 
 _ 0 0 0 ... 0 1 
   ^            

Then it will count up to $1^n$ using less than $2^{n-1} + (n-1)^3$ steps.

   1 2 3 ...   n 
 _ 1 1 1 ... 1 1 
   ^            

The total number of steps is less than:

$$2^{n-1} + 2^{n-1} + 2(n-1)^3 + 2n \leq 2^n + n^3$$

So if we have as input $w = a^{2^n}$; we can perform a binary count (on the second tape) in linear time $O( |w| )$.

$\endgroup$
  • $\begingroup$ @Raphael you may be interested in this post. $\endgroup$ – fade2black Oct 31 '17 at 9:38

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.