Definition of space complexity when algorithm cycles.

Question

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?

Answer 1

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.