3 ms·
”This means we eventually end up either with an empty sequence (the set is empty) or with a sequence with only + operations in it” For valid starting points, t
by Someone 8y ago
”This means we eventually end up either with an empty sequence (the set is empty) or with a sequence with only + operations in it”
For valid starting points, that is true, but it doesn’t follow from the text. The loop has an error exit (”If the sequence starts with − then something has gone wrong”), and the text doesn’t show that you won’t get there for valid inputs, and showing that isn’t trivial.
For example, if the sequence is ++---+, the first iteration removes the second and third item, leaving +--+, and the second iteration removes the first and second item, yielding -+.
The ‘program’ crashes there because the input is invalid, but proving that it never will crash for valid inputs without resorting to “that’s how integers behave” isn’t trivial.