# Definition of space complexity when algorithm cycles.

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?

• 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 ? – fade2black Aug 11 '17 at 15:03
• @fade2black this excerpt is from my class slides not from papadimitrious – Rodrigo Aug 11 '17 at 15:17
• where space is counted just means that space complexity is being analysed – Rodrigo Aug 11 '17 at 15:18
• 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! – David Richerby Aug 18 '17 at 12:22

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.