1
$\begingroup$

I'm reading side by side my class notes and Papadimitrious' Computational Complexity book. At this point they are talking about space complexity. They give rules for computing space employed in an algorithm that runs on a multi-tape Turing machine:

  1. We count the cells used.
  2. If we don't write in the input, this cells don't count.
  3. If the output cells are written from left to right, they don't count.

The final requirement is expressed differently in Papadimitrious' and my notes. In the books it is written:

The cursor of the input string does not wander off into the blank symbols after the end of the input. It is a useful technical requirement, but not necessary.

In my notes:

In an algorithm where space is counted, there can exist computations that never end, but one can always transform the algorithm into another that doesn't cycle.

So how does one measure the space complexity of an algorithm that may cycle forever? Are this statement equivalent to each other?

$\endgroup$
  • $\begingroup$ Could you give more info about the second statement "In an algorithm where ..."? What do you mean by "space is counted"? From which page in Papadimitrious' did you take this excerpt ? $\endgroup$ – fade2black Aug 11 '17 at 15:03
  • $\begingroup$ @fade2black this excerpt is from my class slides not from papadimitrious $\endgroup$ – Javier Aug 11 '17 at 15:17
  • $\begingroup$ where space is counted just means that space complexity is being analysed $\endgroup$ – Javier Aug 11 '17 at 15:18
  • $\begingroup$ Hey, Rodrigo. I just rejected two of your edits because they completely rewrote existing answers to say something different. If you want to post your own answer, post it as a new answer -- don't edit it on top of somebody else's. Thanks! $\endgroup$ – David Richerby Aug 18 '17 at 12:22
1
$\begingroup$

So how does one measure the space complexity of an algorithm that may cycle forever?

When we say that some language $L$ belongs to some complexity class it is assumed that a TM (algorithm) decides $x \in L$ in finite space and time amount. In other words, the TM/algorithm terminates, i.e. it may not cycle forever. However, an algorithm that loops forever may use finite space, but it still cannot decide.

But I don't understand the following statement

In an algorithm where space is counted, there can exist computations that never end, but one can always transform the algorithm into another that doesn't cycle.

$\endgroup$
  • 1
    $\begingroup$ Last statement means that cycles can be detected and you can make another that will halt in the same case instead of cycling. $\endgroup$ – rus9384 Aug 28 '17 at 13:08
  • $\begingroup$ @rus9384 In any case, I am curious how we are supposed to detect infinite loops (in general) excepting special cases like in case of TMs with bounded space. $\endgroup$ – fade2black Aug 28 '17 at 14:23
  • $\begingroup$ They only said that such algorithm exists. Of course finding it in general is undecidable. $\endgroup$ – rus9384 Aug 28 '17 at 14:36
  • $\begingroup$ Also if "counted" means that space complexity is finite then their statement is correct: any finite algorithm can be optimized etc (otherwise how codegolfing would exist?). $\endgroup$ – rus9384 Aug 28 '17 at 15:14

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.