2
$\begingroup$

We define the language

$$ L = \{a^nb^n : n\geq0 \} $$

and we want to prove the following

$$ L = \mathrm{DSPACE}(\log n)\,. $$

So we have to prove that by using $\log n$ space on the work tape of a Turing machine we can decide this language. In this case, do we have to describe the delta function in detail, or can we just use the Church Turing thesis and show an algorithm that uses $\log n$ space to decide this language, and thus claim that $L$ is indeed in $\mathrm{DSPACE}(\log n)$?

For example the pseudocode for the above language would be the following:

    number_of_as = 0
    number_of_bs = 0
    tmp = read()
    while(tmp == a)
          number_of_as++
          tmp = read()
    if(tmp == b) number_of_bs = 1
    tmp = read()
    while(tmp == b)
          number_of_bs++
          tmp = read()
    if(number_of_as == number_of_bs) "accept"
    else "reject"

we only use two counter and the tmp variable, for each variable we need $\log n$ space, so in total $3\log n$, so the problem is in $\mathrm{DSPACE}(\log n)$.

$\endgroup$
  • 1
    $\begingroup$ Where is the proof that the depicted algorithm indeed attains the stated bound? $\endgroup$ – Raphael Sep 20 '14 at 17:32
  • $\begingroup$ do we also have to prove that the algorithm is correct? $\endgroup$ – jsguy Sep 20 '14 at 17:33
  • 1
    $\begingroup$ Of course! (Otherwise, it's just a chunk of code.) $\endgroup$ – Raphael Sep 21 '14 at 7:55
4
$\begingroup$

To state the obvious, you need to prove that the language is decided by some Turing machine that uses a logarithmic amount of space on its work tape.

Anything beyond that is a question of how rigorous the proof should be. A proof should be rigorous enough to convince an appropriately skeptical reader. How much skepticism is appropriate in a given situation? Well, that's a largely social construct. If we were chatting during a coffee break at a complexity theory conference, I'd probably be convinced by "Oh, just use a couple of binary counters to remember how many $a$s and $b$s you've seen. The input has length $n$ so the counters only need $\log n$ bits each." If I was marking your undergrad complexity theory exam, I'd expect rather more detail. For example, our conference chat didn't include the fact that the machine should reject if it finds an $a$ after the first $b$ and your pseudocode also misses this, so it accepts the string $aba\notin L$.

Expecting a full definition of the Turing machine is probably unreasonable. First, it would take a long time to produce. Second, and more importantly, it would be sufficiently complicated that it would be hard to verify that the Turing machine really does what you claim it does. A proof that is too complicated for anyone to understand isn't really a lot of use. That being the case, you're pretty much going to have to use pseudocode. If I wanted to test that you could produce a formal description of a Turing machine, I'd use a simpler language, such as the strings with an even number of $a$s in them.

Is pseudocode on its own enough? Not quite. For example, you can't just invoke Church–Turing to convert your pseudocode into a Turing machine. Why not? Because Church–Turing preserves computability but not complexity. So, what does an answer need? I would say the following.

  1. Pseudocode for an algorithm.
  2. If it's not obvious, a proof (with an appropriate level of rigour) that the pseudocode actually solves the required problem.
  3. If it's not obvious, a proof (with an appropriate level of rigour) that the pseudocode can be converted into a Turing machine with the appropriate resource bounds.

Even if you think the two proofs are obvious, it's a good idea to write a sentence or two about them. Trying to explain as briefly as possibly why something is correct can often find bugs such as the $aba$ problem.

$\endgroup$

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.