2
$\begingroup$

Like think of the function $f\colon \{ 0,1\}^* \rightarrow \{0,1\}^*$ which maps a binary string string $x$ to say a string of $0$s of length $\vert x \vert ^2$ whre $\vert x \vert$ is the length of the input string.

This to my mind looks like a work that can be done using only a linear amount of space on the work tape. All you really need to do is just have a counter to count the length of the input string in one pass and then you know what $\vert x \vert$ is and then squaring it is a constant time process and then just output those many $0$s.

Is my intutiion correct? How is one supposed to formally prove such a space-bound on the working of a (deterministic Turing Machine) DTM? Can someone kindly show how to write this up formally?

$\endgroup$
  • $\begingroup$ Squaring doesn't take constant time on a Turing machine. $\endgroup$ – Yuval Filmus Feb 2 '15 at 22:05
1
$\begingroup$

Perhaps the simplest way to show that a certain task can be done with small space is writing C-like pseudocode for it. If you are only using a constant number of variables, and each variable is exponentially bounded in terms of the input length (i.e. $|x| = O(k^n)$ for fixed $k$), then the resulting computation uses at most linear space. You can use the fact that addition, multiplication and division can be done in linear space ($O(n)$), as well as operations like determining the input length.

As an example, here is pseudocode for your algorithm:

f(x) {
  l = |x|;
  y = l * l;
  for i from 1 to y do:
    output 0;
}

The variables here are $l,y,i$ ($x$ is on the input tape so doesn't count). All operations are in linear space (as long as the inputs are small enough), $l \leq n$ and $y,i \leq n^2$, so the algorithm uses linear space.

If the bounds on the variables are polynomial ($O(n^k)$) rather than exponential ($O(k^n)$), then the resulting program is logspace (uses $O(\log n)$ space); all operations mentioned can be implemented in logspace. Indeed, since the bounds in your case are polynomial, your algorithm is logspace; the fact that the output is larger doesn't matter, since we only count space on the work tape.

$\endgroup$
  • $\begingroup$ I am not getting you. (1) What is $k$ and $n$ for you and what in the DTM corresponds to that? (2) As a pseudocode I can see how the space constraint is counted but I have no clue what is the DTM equivalent for what your pseudocode does! I can't see a way to go back and forth between algorithmic thinking and DTM implementation - and its there that the work-tape constraints have to be implemented (3) I am not familiar with this idea that addition, multiplication and division can be done in linear space. $\endgroup$ – user6818 Feb 3 '15 at 2:27
  • $\begingroup$ BTW, I am a complete newcomer to this theory! So kindly excuse my elementary questions. Its great that a renowned expert like you is helping me! $\endgroup$ – user6818 Feb 3 '15 at 2:28
  • $\begingroup$ (1) $n$ is the input size (in bits), and $k$ is an arbitrary constant. Any will do. (2) This is usually swept under the rug, though you're right that you can only do that after having been convinced that this conversion could potentially be done. Perhaps you can start with implementing simple algorithms like incrementing a counter. (3) This is not an idea but algorithms that use only linear space (or less) to add, multiply and divide. I think the "high school" algorithms are good enough for this purpose. $\endgroup$ – Yuval Filmus Feb 3 '15 at 3:32
  • $\begingroup$ How do you implement a "counter" in DTM? As in how do you count the length of the arbitrary string of 0,1s that is being given as entries on the input tape? [...I guess the write-up here is what explains how to add (and hence multiply and power-raise ?) two integers in log -space - jeapostrophe.github.io/2013-10-29-tmadd-post.html - right? ...] $\endgroup$ – user6818 Feb 3 '15 at 3:52
  • $\begingroup$ This is getting too specific. There must be some textbook with a "hands-on" approach for Turing machines, though I'm not aware of any. You're right to worry about these matters, but since the details are tedious, one usually just uses one's intuition on what can be done using which resources. $\endgroup$ – Yuval Filmus Feb 3 '15 at 3:54

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.