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:
- We count the cells used.
- If we don't write in the input, this cells don't count.
- 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?